Discrepancy Games

Abstract

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.