MIT Combinatorics Seminar

Positional Games

Michael Krivelevich (Tel Aviv University)

Wednesday, March 8, 2006   4:30 pm    Room 2-105


A positional game is a played on a finite board V, where a family of subsets (a hypergraph) H, whose members are usually called winning sets, is specified. The game is played by two players, taking turns in claiming previously unoccupied elements of V, and ends whenever there are no unoccupied elements. In general, there are two additional parameters, p and q, the first player takes p elements in his turn, while the second one claims q elements.

There are several types of positional games. In the so called Strong Game, a player completing a winning set A of H first wins, otherwise the game ends in a draw. In a Weak Game, the first player (Maker) wins if he completes a winning set by the end of the game, otherwise the game is won by the second player (Breaker). In the Avoider-Enforcer version, the first player (Avoider) aims to avoid occupying a winning set completely, while the second player (Enforcer) tries to force Avoider to do just so. There are also hybrid versions, where, for example, the first player acts both as Breaker and Avoider.

There is an amazing variety of recreational and mathematical games that can be casted into the above described framework. Examples include Tic-Tac-Toe and its multi-dimensional generalizations, the game of Hex played and studied by John Nash, and various achievement games played on the edges of the complete graph K^n, where for example Maker tries to create a Hamilton cycle, while Breaker aims to prevent Maker from fulfilling his goal.

In this survey-type talk I will introduce the subject of positional games, and will define and discuss a variety of types of positional games. I will indicate some typical approaches and tools available. Some recent results will be discussed too. I will stress a perhaps surprising yet quite ubiquitous role of probabilistic intuition in analyzing these deterministic games.

No experience (theoretical at least) with positional games will be assumed.