Discrepancy games

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 ∈ 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 - √ln(2m)n/2 and n/2 + √ln(2m)n/2 of his vertices on every edge e of H. We also discuss applications in positional game theory.