2025/03/21 by Anita Liebenau, Abdallah Saffidine, Liebenau, Anita +3
Computer Science · Mathematics · #Artificial Intelligence in Games #Complexity and Algorithms in Graphs #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.2503.16770
openalex publication_date 2025/03/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the b-biased Oriented-cycle game where two players, OMaker and OBreaker, take turns directing the edges of Kn (the complete graph on n vertices). In each round, OMaker directs one previously undirected edge followed by OBreaker directing between one and b previously undirected edges. The game ends once all edges have been directed, and OMaker wins if and only if the resulting tournament contains a directed cycle. Bollobás and Szabó asked the following question: what is the largest value of the bias b for which OMaker has a winning strategy? Ben-Eliezer, Krivelevich and Sudakov proved that OMaker has a winning strategy for b ≤ n/2 - 2. In the other direction, Clemens and Liebenau proved that OBreaker has a winning strategy for b ≥ 5n/6+2. Inspired by their approach, we propose a significantly stronger strategy for OBreaker which we prove to be winning for b ≥ 0.7841n + O(1).