Linear Voronoi game

[mehrj]

Here i want to discuss about Linear Voronoi game. The game consists of two players, and a finite set of users placed along a line. Each player has 2m facilities, where m>0 is a fixed integer. The game starts by the first player, placing 2 facilities on the line, followed by which the second player places 2 facilities, and this continues for multiple rounds. Assuming that each user is served by a facility closest to it, the payoff of each player is defined as the number of users served by the facilities of that player. The goal of each player is to maximize his payoff. I try to find an optimal strategies for last move of both players to find their best placements in the game.

 

 

I have searched for related works. Recently, Banik et. al. studied the discrete one-round Voronoi game in R, and introduced algorithms for finding both players' optimal strategies. The authors showed finding the optimal placement for the first player can be done in linear time and the optimal placement for the second player can also be found in O(n^(a-b)), where a is the number of facilities and 0<b<1 depends only on a. After this result, they studied the two-round Voronoi game and gave algorithms for finding the optimal placements of all the moves. They also showed P2 always has a winning strategy in such a game. The discrete Voronoi game in a polygonal domain was studied in their article. In another work Banik et. al. studied another variation of the game in R^2. They considered the one-round discrete Voronoi game in R^2 where both players have already placed k facilities on the plane. In a sense they tried to solve the last round of a (k+1)-round game. The authors provided algorithms for both of the players to find their optimal placements.