Metraipolis › archive › dc_41cdad552bf1

The Facility Advantage in the One-Round Discrete Voronoi Game on a Line — arXiv:2609.24936

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.24936
License (as archived): CC0-1.0
Archived: 2026-10-09T06:58:08.914Z
SHA-256 of the archived text: 3b3419c55bef5732987cd5f83fc5e716f5107a86074b37a814639a721275806e
Stable URL of this page: https://metraipolis.com/documento/dc_41cdad552bf1

How to cite

The Facility Advantage in the One-Round Discrete Voronoi Game on a Line — arXiv:2609.24936 — arXiv (en), https://arxiv.org/abs/2609.24936 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_41cdad552bf1 (Metraipolis archive dc_41cdad552bf1, sha256 3b3419c55bef5732987cd5f83fc5e716f5107a86074b37a814639a721275806e)

BibTeX

@misc{dc41cdad552bf1,
  title = {The Facility Advantage in the One-Round Discrete Voronoi Game on a Line — arXiv:2609.24936},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.24936},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_41cdad552bf1; sha256 3b3419c55bef5732987cd5f83fc5e716f5107a86074b37a814639a721275806e},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.24936. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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^*(\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$.

Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-22 in cs.GT).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Computational Geometry (cs.CG); Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2609.24936 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-09T06:52:12.770Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-22?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).