The one-round Voronoi game (Q1424320)

The authors study a geometric model for competetive facility location, described in the form of a one-round \(d\)-dimensional Voronoi game (\(d\geq 2\)) with the following structure: There are two players, White and Black. At first White arbitrarily choses an \(n\)-element set \(W\) in the \(d\)-dimensional hypercube \(Q\) of volume \(n\), and next Black choses an \(n\)-element set \(B\) in \(Q\setminus W\) (here \(W\) and \(B\) are the players' strategies). The goal of both players is to capture as much of the area of \(Q\) as possible, where the region captured by White is \(R(W,B) = \{x \in Q: \text{dist}(x,W) < \text{dist}(B)\}\), and the region captured by Black is \(R(B,W)\). It leads to the two-person game \(\Gamma\) (of constant sum 1) with the payoff functions \(f_1(W,B) = \text{vol}(\)R(W,B))/ \text{vol}(Q) and \(f_2(W,B) = \text{vol}(R(B,W))/ \text{vol}(Q)\) for the players White and Black, respectively, where \(\text{vol}(\cdot)\) is the Lebesgue measure. The main result of the paper says that for any \(d\geq 2\) there exist an \(\alpha >0\) and \(n_0\) such that for every \(n>n_0\), Black has a winning strategy which ensures him the payoff at least \(\frac{1}{2} +\alpha\). The paper ends with an interesting review of open problems in this topic.