The Facility Advantage in the One-Round Discrete Voronoi Game on a Line

In the one-round discrete Voronoi game a multiset $V$ of $n$ voters on a line is given; player P places $k$ facilities, player Q then places $\ell$, and each voter is won by the nearer facility, ties going to P. P wins if it keeps at least $n/2$ voters. In the vocabulary of competitive location this is the absolute $(\ell |k)$-centroid problem on a path with unit demands, and the responder's problem is the $(\ell |X_k)$-medianoid, whose closed form on a path -- the sum of the $\ell$ largest of at most $2k$ explicit marginals -- is due to Spoerhase and Wirth. We record this structure, with complete proofs, and draw two consequences that we believe are new. First, we compute the value of the game against a single responding facility, ${\Gamma }_{k,1}(V)$, together with an optimal strategy for P, in $O(n\log n)$ time for arbitrary positive real demands and every $k$. This improves the $O(kn{\log }^{2}n)$ bound of Lazar and Tamir for the absolute $(1|k)$-centroid on a path. Second, we study the facility advantage $k^{\ast }(\ell )$, the least $k$ for which P wins every instance against $\ell$ facilities. We prove $k^{\ast }(\ell )\le 2\ell -1$, exhibit instances proving $k^{\ast }(\ell )\ge \ell +1$ for $2\le \ell \le 6$ (an exact, computer-assisted proof resting on a half-integer discretisation), determine $k^{\ast }(1)=1$ and $k^{\ast }(2)=3$, and show that on uniform instances $k=\ell$ already suffices, so the extremal instances are weighted and Q wins them by a single voter. We conjecture $k^{\ast }(\ell )=\ell +1$ for all $\ell \ge 2$.