Metraipolis › archive › dc_64607a58d5cf
Mechanism Design for Bridge Location with Optional Preferences — arXiv:2609.39097
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.39097
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T13:16:30.961Z
- SHA-256 of the archived text
22f6277b52225f80910f517db7f4b2f73e52dc8889167c4e9315cdb1fe96622d- Stable URL of this page
https://metraipolis.com/documento/dc_64607a58d5cf
How to cite
Mechanism Design for Bridge Location with Optional Preferences — arXiv:2609.39097 — arXiv (en), https://arxiv.org/abs/2609.39097 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_64607a58d5cf (Metraipolis archive dc_64607a58d5cf, sha256 22f6277b52225f80910f517db7f4b2f73e52dc8889167c4e9315cdb1fe96622d)
BibTeX
@misc{dc64607a58d5cf,
title = {Mechanism Design for Bridge Location with Optional Preferences — arXiv:2609.39097},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.39097},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_64607a58d5cf; sha256 22f6277b52225f80910f517db7f4b2f73e52dc8889167c4e9315cdb1fe96622d},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.39097. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the bridge location problem with optional preferences, where two separated regions each contain one prelocated facility. Each agent has a private location and a private preference specifying a nonempty subset of the two facilities in which she is interested. Her individual cost is measured by one of three natural variants: the maximum, the sum, or the minimum of her distances to the facilities in which she is interested. The social planner must design deterministic strategyproof mechanisms that elicit truthful reports, choose the location of a connecting bridge, and approximately minimize either the social cost or the maximum cost. Our main results are as follows. For the social cost objective, we design optimal mechanisms for the max-variant and sum-variant costs, and provide a 3-approximation mechanism for the min-variant cost, and establish a lower bound of 2 for the min-variant. For the maximum cost objective, we give 5/3-approximation mechanisms for the max-variant and sum-variant costs, and a 3-approximation mechanism for the min-variant cost; we also prove a common lower bound of 5/3 that applies to all three cost variants under the maximum cost objective. Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-10-01 in cs.GT). Categorie arXiv: Computer Science and Game Theory (cs.GT). Pagina del lavoro: https://arxiv.org/abs/2609.39097 — 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-07T12:48:01.873Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).