
doi: 10.37236/1948
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.
Maker/Breaker-type games, Balancer and Unbalancer, Games involving graphs, Hypergraphs, game played on a hypergraph, Positional games (pursuit and evasion, etc.)
Maker/Breaker-type games, Balancer and Unbalancer, Games involving graphs, Hypergraphs, game played on a hypergraph, Positional games (pursuit and evasion, etc.)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 5 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
