Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2409.20396 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918126868758528 |
|---|---|
| author | Peng, Cheng Zhou, Houyu |
| author_facet | Peng, Cheng Zhou, Houyu |
| contents | This paper investigates mechanism design for congested facility location problems, where agents are partitioned into groups with conflicting interests (e.g., competition for booking a basketball court in a gymnasium), and each agent's cost increases when the facility is located closer to their competitors. We analyze three types of misreporting: location-only, group-membership-only, and combined misreporting. To minimize social cost, we propose a strategyproof mechanism that achieves optimality under location-only misreporting. For group membership and combined misreporting, we show that the median mechanism attains tight approximation bounds. For the objective of minimizing maximum cost, we introduce novel strategyproof mechanisms for location-only and group-membership-only misreporting, while employing the leftmost mechanism under combined misreporting. We prove that all proposed mechanisms achieve nearly tight performance guarantees. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_20396 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Mechanism Design for Congested Facility Location Peng, Cheng Zhou, Houyu Computer Science and Game Theory This paper investigates mechanism design for congested facility location problems, where agents are partitioned into groups with conflicting interests (e.g., competition for booking a basketball court in a gymnasium), and each agent's cost increases when the facility is located closer to their competitors. We analyze three types of misreporting: location-only, group-membership-only, and combined misreporting. To minimize social cost, we propose a strategyproof mechanism that achieves optimality under location-only misreporting. For group membership and combined misreporting, we show that the median mechanism attains tight approximation bounds. For the objective of minimizing maximum cost, we introduce novel strategyproof mechanisms for location-only and group-membership-only misreporting, while employing the leftmost mechanism under combined misreporting. We prove that all proposed mechanisms achieve nearly tight performance guarantees. |
| title | Mechanism Design for Congested Facility Location |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2409.20396 |