Metraipolis › archive › dc_fa9a283edfac

Search and Verification for Strategyproof Facility Location on Metric Graphs — arXiv:2611.05092

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.05092
License (as archived): CC0-1.0
Archived: 2026-11-04T12:36:45.181Z
SHA-256 of the archived text: d0f2cbaca8d73cfe5c1180fa71e5139eb0c82db6297f25802ce2f9a769a57a41
Stable URL of this page: https://metraipolis.com/documento/dc_fa9a283edfac

How to cite

Search and Verification for Strategyproof Facility Location on Metric Graphs — arXiv:2611.05092 — arXiv (en), https://arxiv.org/abs/2611.05092 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fa9a283edfac (Metraipolis archive dc_fa9a283edfac, sha256 d0f2cbaca8d73cfe5c1180fa71e5139eb0c82db6297f25802ce2f9a769a57a41)

BibTeX

@misc{dcfa9a283edfac,
  title = {Search and Verification for Strategyproof Facility Location on Metric Graphs — arXiv:2611.05092},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.05092},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fa9a283edfac; sha256 d0f2cbaca8d73cfe5c1180fa71e5139eb0c82db6297f25802ce2f9a769a57a41},
  year = {2026}
}

Archived text

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

We study automated design of strategyproof (SP) mechanisms for randomized facility location on continuous metric graphs, with the objective of minimizing total distance. We develop methods for computing upper and lower bounds on the optimal approximation ratio achievable by SP mechanisms for a given graph and number of agents. For the lower bound, we propose a cost-preserving reduction to a finite domain that yields lower bounds for unrestricted SP mechanisms through linear programming dual certificates. For the upper bound, we introduce finite representations of mechanisms, called piecewise-linear attributions (PL attributions), that mix piecewise-linear deterministic mechanisms using affine weights on a triangulation of the report space. We show that for mechanisms represented by PL attributions, checking SP and an approximation guarantee reduces to finitely many quadratic nonnegativity tests over compact polytopes. With exact arithmetic and comparisons, each verification certifies the proposed property or returns locations where it fails. In addition, we introduce a strengthening of the incentive notion called strong strategyproofness. We show that for fixed component mechanisms and regions of a PL attribution, the strong strategyproofness requirement can be expressed by a finite number of linear constraints on the attribution coefficients. Using these theoretical results, we propose a heuristic procedure for computing an upper bound on the approximation ratio. We compute certified upper and lower bounds on several metric graphs and numerically evaluate the proposed search procedure. Lastly, we show that deterministic SP onto mechanisms on graphs are strongly strategyproof and admit PL attributions. Thus restricting attention to strongly strategyproof mechanisms admitting PL attributions loses no deterministic SP onto mechanisms.

Tema degli esploratori: economia dei servizi IA (elenco arXiv cs.GT, nuovi lavori del giorno).
Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Theoretical Economics (econ.TH).
Pagina del lavoro: https://arxiv.org/abs/2611.05092 — 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-11-04T12:28:17.119Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).