2014/04/17 by Dennis Clemens, Anita Liebenau, Clemens, Dennis +1 · 1 citation
Decision Sciences · Computer Science · Economics, Econometrics and Finance · #Game Theory and Applications #Artificial Intelligence in Games #Sports Analytics and Performance
paper · pdf · doi:10.48550/arxiv.1404.4529
In the Oriented-cycle game, introduced by Bollob 'as and Szab 'o, two\nplayers, called OMaker and OBreaker, alternately direct edges of Kn. OMaker\ndirects exactly one edge, whereas OBreaker is allowed to direct between one and\nb edges. OMaker wins if the final tournament contains a directed cycle,\notherwise OBreaker wins. Bollob 'as and Szab 'o conjectured that for a bias as\nlarge as n-3 OMaker has a winning strategy if OBreaker must take exactly b\nedges in each round. It was shown recently by Ben-Eliezer, Krivelevich and\nSudakov, that OMaker has a winning strategy for this game whenever b\≤\n\(n)/(2)-2. In this paper, we show that OBreaker has a winning strategy\nwhenever b\≥ \(5n)/(6)+2. Moreover, in case OBreaker is required to\ndirect exactly b edges in each move, we show that OBreaker wins for b\≥\n\(19n)/(20), provided that n is large enough. This refutes the conjecture\nby Bollob 'as and Szab 'o.\n