Avoider-Enforcer: The rules of the game

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:117

Article

Hefetz, Dan^1,2  Krivelevich, Michael³  Stojakovic, Milos⁴  Szabo, Tibor⁵ 

[1] ETH, Inst Theoret Comp Sci, CH-8092 Zurich, Switzerland

[2] Tel Aviv Univ, Sch Comp Sci, Raymond & Beverly Sackler Fac Exact Sci, IL-69978 Tel Aviv, Israel

[3] Tel Aviv Univ, Sch Math Sci, Raymond & Beverly Sackler Fac Exact Sci, IL-69978 Tel Aviv, Israel

[4] Univ Novi Sad, Dept Math & Informat, Novi Sad 21000, Serbia

[5] McGill Univ, Dept Math & Stat, Montreal, PQ H9X 3B3, Canada

关键词: Positional games;    Misere;    Avoider-Enforcer;    Connectivity;    Hamiltonicity;   

DOI  :  10.1016/j.jcta.2009.05.001

来源: Elsevier

【 摘 要 】

An Avoider-Enforcer game is played by two players, called Avoider and Enforcer, on a hypergraph F subset of 2(x). The players claim previously unoccupied elements of the board X in turns. Enforcer wins if Avoider claims all vertices of some element of F otherwise Avoider wins. In a more general version of the game a bias b is introduced to level up the players' chances of winning; Avoider claims one element of the board in each of his moves. while Enforcer responds by claiming b elements. This traditional set of rules for Avoider-Enforcer games is known to have a shortcoming: it is not bias monotone. We relax the traditional rules in a rather natural way to obtain bias monotonicity. We analyze this new set of rules and compare it with the traditional ones to conclude some surprising results. In particular, we show that under the new rules the threshold bias for both the connectivity and Hamiltonicity games, played on the edge set of the complete graph K-n, is asymptotically equal to n/log n. This coincides with the asymptotic threshold bias of the same game played by two random players. (C) 2009 Elsevier Inc. All rights reserved.

【 授权许可】

Free