Advantage in the discrete Voronoi game

DOI10.7155/JGAA.00331MaRDI QIDQ2929591zbMATH OpenOpenAlexFDO

Authors Dániel Gerbner, Viola Mészáros, Dömötör Pálvölgyi, Alexey Pokrovskiy, Günter Rote

Publication date 13 November 2014

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1303.0523

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Abstract: We study the discrete Voronoi game, where two players alternately claim vertices of a graph for t rounds. In the end, the remaining vertices are divided such that each player receives the vertices that are closer to his or her claimed vertices. We prove that there are graphs for which the second player gets almost all vertices in this game, but this is not possible for bounded-degree graphs. For trees, the first player can get at least one quarter of the vertices, and we give examples where she can get only little more than one third of them. We make some general observations, relating the result with many rounds to the result for the one-round game on the same graph.

Recommendations

• The Voronoi game on graphs and its complexity
• The one-round Voronoi game
• Two-round discrete Voronoi game along a line
• The one-round multi-player discrete Voronoi game on grids and trees
• The one-round multi-player discrete Voronoi game on grids and trees

Cited in

(9)

• The one-round multi-player discrete Voronoi game on grids and trees
• Nash equilibria in reverse temporal Voronoi games
• The discrete Voronoi game in \(\mathbb{R}^2\)
• The Voronoi game on graphs and its complexity
• The one-round multi-player discrete Voronoi game on grids and trees
• The one-round Voronoi game replayed
• The inverse Voronoi problem in graphs. I: Hardness
• Competitive location problems: balanced facility location and the one-round Manhattan Voronoi game
• Competitive location problems: balanced facility location and the one-round Manhattan Voronoi game

Describes a project that uses

Uses Software

• MathOverflow

This page was built for publication: Advantage in the discrete Voronoi game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2929591)