{{Short description|Game where players avoid making losing-sets}} An '''Avoider-Enforcer game<ref name="pg14">{{Cite Positional Games 2014}}</ref>'''{{Rp|43-60}} (also called '''Avoider-Forcer game<ref>{{Cite journal|last=Bednarska-Bzdęga|first=Małgorzata|date=2014-01-12|title=Avoider-Forcer Games on Hypergraphs with Small Rank|url=http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p2|journal=The Electronic Journal of Combinatorics|language=en-US|volume=21|issue=1|pages=1–2|issn=1077-8926}}</ref> ''' or '''Antimaker-Antibreaker game<ref name="Lu 1991">{{Cite journal|last=Lu|first=Xiaoyun|date=1991-11-29|title=A matching game|journal=Discrete Mathematics|language=en|volume=94|issue=3|pages=199–207|doi=10.1016/0012-365X(91)90025-W|issn=0012-365X|doi-access=free}}</ref>'''{{Rp|sec.5}}) is a kind of positional game. Like most positional games, it is described by a set of ''positions/points/elements'' (<math>X</math>) and a family of subsets (<math>\mathcal{F}</math>), 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.
thumb|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 == The winning condition of an Avoider-Enforcer game is exactly the opposite of the winning condition of the Maker-Breaker game on the same <math>\mathcal{F}</math>. 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 ''dis''advantage. 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.'''<ref name="pg14" />'''{{Rp|45-46}}
== Partial avoidance == 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: <math>c_t := (2t)^t \cdot (2-2t)^{1-t} = 2 \cdot t^t \cdot (1-t)^{1-t}</math>(in the standard variant, <math>t=1, c_t\to 2</math>).
* ''If <math>\sum_{E\in \mathcal{F}} {c_t}^{-|E|} < 1</math>, '''and the total number of elements is even''', then Avoider has a winning strategy'' ''when'' ''playing first''.'''<ref name="Lu 1991" />'''{{Rp|thm A5}}
== See also == Biased positional game#A winning condition for Avoider
== References == {{Reflist}} Category:Positional games