Biased positional games for which random strategies are nearly optimal

Citation
M. Bednarska et T. Luczak, Biased positional games for which random strategies are nearly optimal, COMBINATORI, 20(4), 2000, pp. 477-488
Citations number
8
Categorie Soggetti
Mathematics,"Computer Science & Engineering
Journal title
COMBINATORICA
ISSN journal
02099683 → ACNP
Volume
20
Issue
4
Year of publication
2000
Pages
477 - 488
Database
ISI
SICI code
0209-9683(2000)20:4<477:BPGFWR>2.0.ZU;2-1
Abstract
For a graph G and natural numbers n and q let G(G; n, q) be the game on the complete graph K-n in which two players, Maker and Breaker, alternately cl aim 1 and q edges respectively. Maker's aim is to build a copy of G while B reaker tries to prevent it. Let m(G)= max {e(H)-1/v(H)-2 : H subset of or e qual to G, v(H) greater than or equal to 3}. It Is shown that there exist c onstants c(0) and C-0 such that Maker has a winning strategy in G(G;n,q) if q less than or equal to c0n(1/m(G)), while for q greater than or equal to Con(1/m(G)) the game can be won by Breaker.