Jump to content

Avoider-Enforcer game

From Wikipedia, the free encyclopedia

An Avoider-Enforcer game[1]: 43–60  (also called Avoider-Forcer game[2] or Antimaker-Antibreaker game[3]: sec.5 ) is a kind of positional game. Like most positional games, it is described by a set of positions/points/elements () and a family of subsets (), which are called here the losing-sets. It is played by two players, called Avoider and Enforcer, who take turns picking elements until all elements are taken. Avoider wins if he manages to avoid taking a losing set; Enforcer wins if he manages to make Avoider take a losing set.

The board for the game of Sim, an Avoider-Enforcer game

A classic example of such a game is Sim. There, the positions are all the edges of the complete graph on 6 vertices. Players take turns to shade a line in their color, and lose when they form a full triangle of their own color: the losing sets are all the triangles.

Comparison to Maker-Breaker games

[edit]

The winning condition of an Avoider-Enforcer game is exactly the opposite of the winning condition of the Maker-Breaker game on the same . Thus, the Avoider-Enforcer game is the Misère game variant of the Maker-Breaker game. However, there are counter-intuitive differences between these game-types.

For example, consider the biased version of the games, in which the first player takes p elements each turn and the second player takes q elements each turn (in the standard version p=1 and q=1). Maker-Breaker games are bias-monotonic: taking more elements is always an advantage. Formally, if Maker wins the (p:q) Maker-Breaker game, then he also wins the (p+1:q) game and the (p:q-1) game. Avoider-Enforcer games are not bias-monotonic: taking more elements is not always a disadvantage. For example, consider a very simple Avoider-Enforcer game where the losing sets are {w,x} and {y,z}. Then, Avoider wins the (1:1) game, Enforcer wins the (1:2) game and Avoider wins the (2:2) game.

There is a monotone variant of the (p:q) Avoider-Enforcer game-rules, in which Avoider has to pick at least p elements each turn and Enforcer has to pick at least q elements each turn; this variant is bias-monotonic.[1]: 45–46 

Partial avoidance

[edit]

Similarly to Maker-Breaker games, Avoider-Enforcer games also have fractional generalizations.

Suppose Avoider needs to avoid taking at least a fraction t of the elements in any winning-set (i.e., take at most 1-t of the elements in any set), and Enforcer needs to prevent this, i.e., Enforcer needs to take less than a fraction t of the elements in some winning-set. Define the constant: (in the standard variant, ).

  • If , and the total number of elements is even, then Avoider has a winning strategy when playing first.[3]: thm A5 

See also

[edit]

Biased positional game#A winning condition for Avoider

References

[edit]
  1. ^ a b Hefetz, Dan; Krivelevich, Michael; Stojaković, Miloš; Szabó, Tibor (2014). Positional Games. Oberwolfach Seminars. Vol. 44. Basel: Birkhäuser Verlag GmbH. ISBN 978-3-0348-0824-8.
  2. ^ Bednarska-Bzdęga, Małgorzata (2014-01-12). "Avoider-Forcer Games on Hypergraphs with Small Rank". The Electronic Journal of Combinatorics. 21 (1): 1–2. ISSN 1077-8926.
  3. ^ a b Lu, Xiaoyun (1991-11-29). "A matching game". Discrete Mathematics. 94 (3): 199–207. doi:10.1016/0012-365X(91)90025-W. ISSN 0012-365X.