Kavli Affiliate: Cheng Peng
| First 5 Authors: Cheng Peng, Cheng Peng, , ,
| Summary:
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.
| Search Query: ArXiv Query: search_query=au:”Cheng Peng”&id_list=&start=0&max_results=3