# Multiplayer one-round one-move voronoi game on graphs

I'm trying to solve a variant of Voronoi Game.

Given a Graph $$G=(V, E)$$, with uniform distance $$d(E)=1$$, a subset of the vertices $$\hat{V} \subseteq V$$ are vertices of interests. $$k$$ players take turns to place their facilities $$V^*_i$$ on graph $$G$$. We define a subgraph $$G_i = \{ V_i, E : \forall V_i, d(V_i, V^*_i) \leq d(V_i, V^*_j) \}$$, that is in plain words, every vertex in the subgraph is closer to the player $$i$$'s facility than other facilities.

Each player will take turns to place their facilities. Each player will place at most 1 facility. The goal for player $$i$$ is to maximize the verticies of interest in his subgraph, or $$|\hat{V}| \in G_i$$.

My research points me to several papers, such as Nash equilibria in Voronoi games on graphs, but most of them simply states that the problem is NP-hard. Also, I am not even sure if I need Nash equilibrium, since I am just trying to find the optimal placement for each player.

As this is a practical problem, and the space is small, think $$k=5$$, $$|V|=25$$, I'm wondering if there are any greedy, approximation, randomized algorithms that are efficient for this task?

I would also appreciate any hints, or places to further my search.