Optimal strategies for the one-round discrete Voronoi game on a line (Q386423)

The paper under review establishes that if the points in an \(n\)-point user set are located along a line, then the optimal strategy of the second player, given any placement of facilities by the first player, can be computed in \(O(n)\) time. The paper shows that the optimal strategy of the first player for \(m\) facilities in the one-round discrete Voronoi game with the users on a line can be computed in \(O(n^{m-\lambda_m})\) time for a constant \(\lambda_m \in (0, 1)\) depending only on \(m\). The main objective in any facility location problem is to judiciously place a set of facilities serving a set of users such that certain optimal criteria are satisfied. The set of users is either discrete consisting of finitely many points or continuous where every point in a region is considered to be a user. Each facility has its service zero consisting of the set of users served by it. \textit{H. A. Eiselt} and \textit{G. Laporte} [Eur. J. Oper. Res. 39, No. 3, 231--242 (1989; Zbl 0661.90009)], \textit{H. A. Eiselt} et al. [Transp. Sci. 27, No. 1, 44--54 (1993; Zbl 0767.90006)] and \textit{T. L. Friesz} et al. [Ann. Oper. Res. 18, No. 1--4, 267--276 (1989; Zbl 0707.90065)] studied competitive facility location with favorable placements of facilities by competing market players. \textit{F. Dehne} et al. [Int. J. Comput. Geom. Appl. 15, No. 5, 463--475 (2005; Zbl 1093.68654)] addressed the problem of finding a new point \(q\) amid a set of \(n\) existing points such that the Voronoi region of \(q\) is maximized. For the same problem, \textit{O. Cheong} et al. [Discrete Comput. Geom. 37, No. 4, 545--563 (2007; Zbl 1118.52011)] gave a near-linear time algorithm that locates the new optimal point approximately when points are in general position. \textit{B. B. Bhattacharya} [J. Math. Model. Algorithms 9, No. 4, 375--392 (2010; Zbl 1229.68076)] considered the maximization of the area of the Voronoi region of a set of points placed inside a circle. In the discrete user case, \textit{S. Cabello} et al. [Eur. J. Oper. Res. 202, No. 1, 99--106 (2010; Zbl 1173.90446)] addressed the analogous problems to maximize the number of users served by the new facilities, and referred to it as the MaxCov problem. They showed that the MaxCov problem can be solved in \(O(n \log n)\) time in the \(l_1\) and \(l_{\infty}\) metrics; the MaxCov problem is 3SUM hard if the number of existing facilities \(m\geq 2\) in the \(l_2\) metric, with an \(O(n^2)\) time algorithm; the MaxCov problem can be solved in \(O(n \log n)\) time for \(m=1\) in the \(l_2\) metric. A game-theoretic analogue of such competitive problems for continuous demand regions is a situation where the two players place two disjoint sets of facilities in the demand region. The area a player owns at the end of the game is called the payoff of the player. In the one-round game, the first player places \(m\) facilities followed by the second player placing another \(m\) facilities in the demand region; in the \(m\)-round game, the two players place one facility each alternately for \(m\) rounds in the demand region. \textit{H.-K. Ahn} et al. [Theor. Comput. Sci. 310, No. 1--3, 457--467 (2004; Zbl 1098.91003)] showed that when the one-dimensional Voronoi game takes \(m\) rounds, the second player always has a winning strategy that guarantees a payoff of \(\frac{1}{2} + \varepsilon\) for \(\varepsilon > 0\), where the first player can force \(\varepsilon\) arbitrary small. On the other hand, in the one-round game with \(m\) facilities, the first player always has a winning strategy. \textit{S. P. Fekete} and \textit{H. Meijer} [Comput. Geom. 30, No. 2, 81--94 (2005; Zbl 1068.65035)] studied the two-dimensional one-round game played on a rectangular demand region with aspect ratio \(\rho\), and proved that the second player has a winning strategy if and only if \(m\geq 3\) and \(\rho > \frac{\sqrt{2}}{n}\) or \(m=2\) and \(\rho > \frac{\sqrt{3}}{2}\). The authors of the reviewed paper study the one-round Voronoi game in \(\mathbb R\) (1-dimensional case) for a discrete demand set and devise algorithms for obtaining the optimal strategies of the two players. The one-round \((m, n)\) discrete Voronoi game where the users are located along a single straight line and the two players are restricted to place their facilities along the same line, is also considered in this paper. Section 2 gives an algorithm for determining the optimal strategy for the second player given any placement by the first player. Theorem 1 on the \(O(n)\) time optimal placement by the second player in the \(G(m, n)\) game shows that unlike in the continuous case, the one-round \((m ,n)\) discrete Voronoi game with users on a line may be won by either player. This motivates the design of algorithms for obtaining the optimal placement of the players. Section 3 provides an algorithm for determining the optimal placement by the first player. Theorem 2 states that the optimal placement by the first player in the game \(G(m,n)\) can be obtained in \(O(n^{m+1})\) time. Section 4 improves the algorithm for the optimal strategy of the first player and shows in Theorem 3 that the optimal placement by the first player in the game \(G(2, n)\) can be obtained in \(O(n^{1.59})\) time, and can be obtained in \(O(n^{m-\lambda_m})\) time in the general game \(G(m, n)\) for a constant \(\lambda_m \in (0, 1)\) depending only on \(m\).