Monday, June 14, 2010

Whats your Game Mr. Bond- The sequel!

(I will post about CCC 2010 later in the week.)

The word Game is used in many different contexts within math and computer science. I list out all that a group of us at last years Dagstuhl thought of:
  1. Duplicator-Spoiler Games are used in Descriptive Complexity theory and Logic. They are also called Ehrenfeucht-Fraisse games. (The pointer, a Wikipedia entry, has a pointer to EXCELLENT slides on these games.) Example result: wellfoundness for linear orders is not first order definable.
  2. Every A &sub {0,1}&omega gives rise to the following game: Alice picks c1 &isin {0,1} Bob picks c2 &isin {0,1} Alice picks c3 &isin {0,1} Bob picks c4 &isin {0,1} etc. If c1c2c3 ... is in A then Alice wins. If not then Bob wins. The Axiom of Determinacy states that, for every A, one of the two players has a winning strategy. This has been proven for Borel sets A. Full AD contradicts Full AC. See here. I have posted on it before here.
  3. Banach Games. Let A be a subset of R. All numbers picked are in R. Alice picks x1. Bob picks x2 < x1. Alice picks x3 < x2. Bob picks x4 < x3. etc. If &sum xi &isin A then Alice wins, otherwise Bob Wins. For more on these see here.
  4. Banach Mazur Games. (I am not quite sure of this one since I could not find stuff on the web and it looks too much like the games for AD. If this is incorrect please comment.) Similar to the games under AD; however, instead of picking an element of {0,1} the players pick an element of {0,1}+. This has been used to define when a set is meager and has been extended to poly-time settings. Also has been extended to graphs: see here
  5. Martingales. Let A &sub {0,1}&omega. x is in A, but the player does not know what it is. The player starts out with one dollar (wow!). When the player sees the first n bits of x he bids on the (n+1)st bit. Can he win? Depends on A. Has been used to define measure 0 and has been adapted to the poly time setting. Jack Lutz has worked a lot on this stuff.
  6. Complexity Classes have been defined via games. Usually a prover wins if he can convince a verifier that x &isin A. Many parameters can be changed to get many classes (number of rounds, number of provers, strength of verifier, strength of prover(s), prob of error allowed). I would include the Unique Game Conjecture in this use of the word game.
  7. Pebble Games have been used to get time-space trade offs on simple models of computation. More recently they have been used to get lower bounds on resolution theorem provers. For a survey see the first paper on this page. Warning- the survey is 200 pages!
  8. Games have been used to prove theories decidable. Originally S2S (Second order theory with two successors, essentially the theory of infinite strings of 0's and 1's) was proven decidable by Michael Rabin. Later Gurevich and Harrington had a simpler proof using games. See this paper. Another excellent article on this, which alas is not on line, is Infinite Games played on Finite Graphs by Robert McNaughton, Annals of Pure and Applied logic, Volume 65, Issue 2, Pages 149-184.
  9. Combinatorial Games like NIM have been well studied.
  10. Game Theory needs no commentary here.
  11. Richman Games are a way to combine Combinatorial Games with Game Theory. See this paper.
  12. In adversary arguments in lower bounds we picture an adversary who is playing a game with the algorithm or with any possible algorithms.
  13. Communication Complexity Games. Not sure these are really games, but the term is used.
  14. Surreal numbers are actually games. See Conways book On Numbers and Games.
  15. A lot of computer science and graphics go into video games.
  16. There has been some study of strategies on real games like monopoly and chess. I gave one classification of games in this post. Note that GO and Chess are EXPTIME complete.
Note that most of these games are not fun.


  1. Chip-firing games are a kind of solitaire game. They have a stunningly beautiful, surprising theory, explained by this paper:

  2. if it is not fun, is it a game?

  3. "Bill's post" game:

    Read Bill's posts and find some typos in them, like "bit" which should be "bid" in this post. Some people call the players grammar trolls. This game is fun for some players and not so fun for others.

  4. I think Bill is dyssssllexic when it comes down to typos. bbbut nott that it maters, ani one of us makes dese mistakes when tipyng 542 words per hour.

    nice post, tough.