Truthful Mechanisms for Location Games of Dual-Role Facilities

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)

View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Title of host publicationProceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2019)
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages1470-1478
Number of pages9
ISBN (Print)978-1-4503-6309-9
Publication statusPublished - May 2019

Conference

Title18th International Conference on Autonomous Agents and MultiAgent Systems
Location
PlaceCanada
CityMontreal
Period13 - 17 May 2019

Abstract

This paper is devoted to the facility location games withpayments, where every agent plays a dual role of facility andcustomer. In this game, each selfish agent is located on apublicly known location in a metric space, and can allow afacility to be opened at his place. But the opening cost ishis private information and he may strategically report thisopening cost. Besides, each agent also bears a service costequal to the distance to his nearest open facility. We areconcerned with designing truthful mechanisms for the game,which, given agents’ reports, output a set of agents whosefacilities could be opened, and a payment to each of theseagents who opens a facility. The objective is to minimize(exactly or approximately) the social cost (the total openingand service costs) or the maximum agent cost of the outcome. 

We characterize the normalized truthful mechanisms forthis game. Concerning the minimum social-cost objective, wegive an optimal truthful mechanism without regard to timecomplexity, and show a small gap between the best knownapproximation ratio of polynomial-time truthful mechanismsfor the game and that of polynomial-time approximationalgorithms for the counterpart of pure optimization. For theminimum maximum-cost objective, we provide an optimaltruthful mechanism which runs in polynomial time. We alsoinvestigate mechanism design for the game under a budgeton the total payment.

Research Area(s)

  • Truthful mechanism design, Facility location game, Payments

Bibliographic Note

Research Unit(s) information for this publication is provided by the author(s) concerned.

Citation Format(s)

Truthful Mechanisms for Location Games of Dual-Role Facilities. / Chen, Xujin; Li, Minming; Wang, Changjun; Wang, Chenhao; Zhao, Yingchao.

Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2019). International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2019. p. 1470-1478.

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)