5
$\begingroup$

Suppose that several agents need to place points (one per agent) on the interval $[0,1]$. An agent's goal is to maximize the volume of the Voronoi cell that contains his point. When $n$ agents must place their points sequentially, is an optimal strategy known?

From what I was able to glean from the literature so far, it appears I am asking for the Stackelberg solution to an $n$-player Hotelling's game on a segment.

$\endgroup$
  • $\begingroup$ I am not asking people to solve this question for me, just wondering what is known about it -- and the obvious extension to 2 dimensions. $\endgroup$ – Aryeh Mar 20 '15 at 11:17
  • 1
    $\begingroup$ I think these are usually called Voronoi games. I don't know much about them, but I think by searching that keyword you can find out what is known. $\endgroup$ – usul Mar 20 '15 at 13:15
  • $\begingroup$ Thanks! I was only able to find references for 2-player Voronoi games. $\endgroup$ – Aryeh Mar 20 '15 at 13:32
  • $\begingroup$ There may only be research for the 2-player case (don't know).... $\endgroup$ – usul Mar 20 '15 at 13:36
4
$\begingroup$

This game has been studied in

Hee-Kap Ahn, Siu-Wing Cheng, Otfried Cheong, Mordecai Golin, René van Oostrum:
"Competitive facility location: the Voronoi game"
Theoretical Computer Science 310, 2004, pp 457-467

There also are lots of follow-up works, as for instance

Sayan Bandyapadhyay, Aritra Banik, Sandip Das, Hirak Sarkar:
"Voronoi game on graphs"
Theoretical Computer Science 562, 2015, pp 270-282

$\endgroup$
  • $\begingroup$ Still wondering -- has it been studied for $> 2$ players? $\endgroup$ – usul Mar 22 '15 at 1:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.