Positional Games

Tibor Szabó

Institute of Mathematics
Freie Universität Berlin

After scattered results, the theory of positional games originates from an important paper of Erdős and Selfridge. Later the theory was greatly developed by József Beck. Besides being an interesting field on its own, positional games inspired the technique of derandomization from theoretical computer science, most notably the algorithmization of the Local Lemma.
In the usual setup two players, Maker and Breaker, play against each other by alternately occupying one previously unoccupied element of a given finite set (the board). Maker wins if he succeeds in completely occupying one of the members of a given setsystem F (the family of winning sets), otherwise Breaker wins. There is a large literature on graph games, i.e., when the board is the edgeset of some graph, say the complete graph. Often the game is won by Maker and thus Chvatal and Erdős suggested to give Breaker a break in the form of a bias: at every move he is allowed to take b elements of the board instead of just one (which is called the (1:b) biased game).

Valid HTML 4.0! Last modified: Sun Jun 30 23:04:55 CEST 2013