Combinatorics Seminar
When: Sunday, April 29, 10am
Where: Schreiber 309
Speaker: Dan Hefetz, Tel Aviv University
Title: Fast and slow winning strategies in Positional Games
Abstract:
The theory of Positional Games is a relatively young area of
Combinatorics, though its origins can be traced back to Classical
Game Theory. Its goal is to give a mathematical framework for
analyzing games of thought.It is strongly related to mainstream
areas of Combinatorics, such as Ramsey Theory and the theory of
Random Graphs.
Formally, a positional game is a four-tuple (p,q,X,F), where the
set X is called the ``board'', F is a family of "target" subsets
of X, and the positive integers p and q are the ``biases'' of the
players. During the game, two players take turns selecting
previously unclaimed elements of the board. The first player
selects p elements per move, and the second player selects q
elements per move. There are several types of positional games with
different rules for determining the winner. We focus on the following
two:
In a Maker/Breaker-type positional game, the two players are
called Maker and Breaker and F is referred to as the family of
``winning sets''. Maker wins the game if the set he has claimed by
the end of the game (that is, when every element of the board has
been claimed by one of the players) is a winning set, that is, an
element of F; otherwise Breaker wins. A classical example of the
Maker-Breaker setting is the popular board-game HEX. Putting aside
a few scattered results, the theory of Maker-Breaker games started
with a general criterion of Erdos and Selfridge for Breaker's win
in the (1,1) game. Subsequently, Beck started a systematic study of
Maker-Breaker games with a bias.
In an Avoider/Enforcer-type positional game, the players are called
Avoider and Enforcer and F is called the family of ``losing sets''.
Avoider wins the game if the set he has claimed by the end of the
game is not a losing set, that is, not an element of F; otherwise
Enforcer wins. These games are considered less natural than their
Maker-Breaker analog, as Avoider's goal is not to claim a winning
set. However, they prove to be very interesting in their own right
as well as useful for analyzing Maker-Breaker games.
I will overview some of the results of the thesis, focusing on "fast"
winning strategies in Maker-Breaker and Avoider-Enforcer games.