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 c₁ &isin {0,1} Bob picks c₂ &isin {0,1} Alice picks c₃ &isin {0,1} Bob picks c₄ &isin {0,1} etc. If c₁c₂c₃ ... 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 x₁. Bob picks x₂ < x₁. Alice picks x₃ < x₂. Bob picks x₄ < x₃. etc. If &sum x_i &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.