TY - JOUR

T1 - Avoider-Enforcer

T2 - The Rules of the Game

AU - Hefetz, Dan

AU - Krivelevich, Michael

AU - Stojaković, Miloš

AU - Szabó, Tibor

PY - 2009/8/1

Y1 - 2009/8/1

N2 - An Avoider-Enforcer game is played by two players, called Avoider and Enforcer, on a hypergraph F ⊆ 2X. 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 Kn, is asymptotically equal to n / log n.

AB - An Avoider-Enforcer game is played by two players, called Avoider and Enforcer, on a hypergraph F ⊆ 2X. 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 Kn, is asymptotically equal to n / log n.

KW - Hamiltonicity

KW - Positional games

KW - connectivity

UR - http://www.scopus.com/inward/record.url?scp=67651238365&partnerID=8YFLogxK

U2 - 10.1016/j.endm.2009.07.100

DO - 10.1016/j.endm.2009.07.100

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:67651238365

SN - 1571-0653

VL - 34

SP - 261

EP - 265

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -