Facility placing strategies improve voter control on a line
The Facility Advantage in the One-Round Discrete Voronoi Game on a Line
Data Structures and AlgorithmsComputational GeometryComputer Science and Game Theory
Summary
This paper studies a game where two players place facilities along a line to win voters based on distance. The first player tries to secure at least half of all voters by placing a number of facilities before the second player responds. The researchers found a way to quickly calculate the best strategy when the second player places only one facility and analyzed how many facilities the first player needs to guarantee a win against multiple responding facilities. Their results also show some surprising details about when equal resources suffice or when the first player must have more facilities.
What this means in practice
- •For logistics planners: Use fast algorithms to optimally position service centers along a geographic corridor to maximize customer coverage against competitor responses.
- •For network infrastructure teams: Design placement strategies for network nodes along linear topologies that maintain majority user coverage under adversarial node placements.
A theory result. No direct application yet.
Authors
Tamal Maharaj
Abstract
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, $Γ_{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^*(\ell)$, the least $k$ for which P wins every instance against $\ell$ facilities. We prove $k^*(\ell)\le 2\ell-1$, exhibit instances proving $k^*(\ell)\ge\ell+1$ for $2\le\ell\le6$ (an exact, computer-assisted proof resting on a half-integer discretisation), determine $k^*(1)=1$ and $k^*(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^*(\ell)=\ell+1$ for all $\ell\ge2$.