Discrepancy games

Noga Alon ; Michael Krivelevich ; Joel Spencer ; Tibor Szabó

The electronic journal of combinatorics, Tome 12 (2005)

Résumé

We investigate a game played on a hypergraph $H=(V,E)$ by two players, Balancer and Unbalancer. They select one element of the vertex set $V$ alternately until all vertices are selected. Balancer wins if at the end of the game all edges $e\in E$ are roughly equally distributed between the two players. We give a polynomial time algorithm for Balancer to win provided the allowed deviation is large enough. In particular, it follows from our result that if $H$ is $n$-uniform and has $m$ edges, then Balancer can achieve having between $n/2-\sqrt{\ln(2m)n/2}$ and $n/2+\sqrt{\ln(2m)n/2}$ of his vertices on every edge $e$ of $H$. We also discuss applications in positional game theory.

Détail

DOI : 10.37236/1948

Classification : 91A24, 05C65, 91A43
Mots-clés : Maker/Breaker-type games, game played on a hypergraph, Balancer and Unbalancer