On weight function methods in Chooser–Picker games
2013; Elsevier BV; Volume: 475; Linguagem: Inglês
10.1016/j.tcs.2012.12.037
ISSN1879-2294
Autores Tópico(s)Consumer Market Behavior and Pricing
ResumoWe study NP-hard Chooser–Picker biased games on hypergraphs and their connections to classic Maker–Breaker games. We prove two weight-function-based winning criteria for Picker and show that the Erdős–Selfridge winning criterion for Breaker's win is also the winning criterion for Picker in (1:1) games. Thereby we improve previous results by Beck and by Csernenszky, Mándity and Pluhár. Moreover we estimate the critical bias for Picker in Chooser–Picker (1:q) games in which the aim of Chooser is to build a copy of a fixed size graph G in Kn.
Referência(s)