Discrepancy games

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

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

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 ∈ 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.

Original languageEnglish (US)
JournalElectronic Journal of Combinatorics
Volume12
Issue number1 R
StatePublished - Sep 29 2005
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Discrepancy games'. Together they form a unique fingerprint.

Cite this