Metraipolis › archive › dc_abeddd75fdee

Ex-ante versus Ex-post: Egalitarian Facility Location Mechanism Design — arXiv:2608.14499

Source: arXiv (en)
Original: https://arxiv.org/abs/2608.14499
License (as archived): CC0-1.0
Archived: 2026-10-19T02:28:15.850Z
SHA-256 of the archived text: 85ca4c0e2a5b1833b42485c9ca9322a98292ae9b3af7fc895b5e459d9ad23394
Stable URL of this page: https://metraipolis.com/documento/dc_abeddd75fdee

How to cite

Ex-ante versus Ex-post: Egalitarian Facility Location Mechanism Design — arXiv:2608.14499 — arXiv (en), https://arxiv.org/abs/2608.14499 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_abeddd75fdee (Metraipolis archive dc_abeddd75fdee, sha256 85ca4c0e2a5b1833b42485c9ca9322a98292ae9b3af7fc895b5e459d9ad23394)

BibTeX

@misc{dcabeddd75fdee,
  title = {Ex-ante versus Ex-post: Egalitarian Facility Location Mechanism Design — arXiv:2608.14499},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.14499},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_abeddd75fdee; sha256 85ca4c0e2a5b1833b42485c9ca9322a98292ae9b3af7fc895b5e459d9ad23394},
  year = {2026}
}

Archived text

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

We study the facility location mechanism design problem where $n$ strategic agents report locations in Euclidean space and the mechanism outputs a single facility location. Each agent's cost is its distance from the facility, and our objective is to minimize the egalitarian cost, i.e., the maximum agent cost, in a strategyproof way. The optimal deterministic approximation ratio is $2$, achieved by any dictator mechanism. We study the power of randomized strategyproof-in-expectation mechanisms. Prior work has focused on ex-post evaluation, defined as the expected maximum agent cost. We instead study ex-ante evaluation, defined as the maximum expected agent cost, which is naturally aligned with strategyproofness in expectation. We establish the following results: (1) Low dimensions: Strict ex-ante vs. ex-post separation. In $\mathbb{R}$, we give a simple strategyproof mechanism achieving the optimal ex-ante approximation ratio of $1$. In $\mathbb{R}^2$, we design the "Random Rotated Corner" mechanism, with ex-ante approximation ratio at most $1.598$, breaking the deterministic barrier. For the ex-post objective, we prove a lower bound of $1.605$, yielding a strict separation in $\mathbb{R}^2$. (2) High dimensions: Impossibility. In $\mathbb{R}^d$ for $d \gg 1$, we show that no strategyproof-in-expectation mechanism improves on the deterministic dictator mechanism beyond $o_d(1)$. Thus neither ex-post nor ex-ante evaluation yields improved fairness guarantees in high dimensions. An implication is that the "Random Rotation Coordinate-Wise Median" (RRCWM), currently the best known mechanism for the utilitarian objective, is also best possible for the egalitarian objective in high dimension: we show it achieves an approximation ratio of $2$ for both ex-post and ex-ante objectives in $\mathbb{R}^d$ for every $d \ge 1$.

Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-08-17 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2608.14499 — 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-19T02:21:49.074Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-08-17?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).