Heterogeneous Two-facility Location Games with Minimum Distance Requirement

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

View graph of relations

Author(s)

Related Research Unit(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)
Pages1461-1469
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

We study the mechanism design problem of a social planner for locating two heterogeneous facilities on a line interval [0, 1], where a set of n strategic agents report their locations and a mechanism determines the locations of the two facilities.Unlike prior work on two-facility location games, we consider the requirement of the minimum distance d between the two facilities. As the two facilities are heterogeneous and have additive effects on agents, we model that the cost of an agent is the sum of his distances to both facilities and the social cost is the total cost of all agents. In the two facility location game to minimize the social cost, we show that the optimal solution can be computed in polynomial time and prove that carefully choosing one optimal solution as output is strategyproof. In the obnoxious two-facility location game for maximizing the social utility, a mechanism outputting the optimal solution is not strategyproof and we propose new deterministic group strategyproof mechanisms with provable approximation ratios. Moreover, we establish a lower bound 7−d/6 for the approximation ratio achievable by deterministic strategyproof mechanisms. Finally, we study the two-facility location game with triple-preference, where each of the two facilities may be favorable, obnoxious, in different for any agent. We further allow each agent to misreport his location and preference towards the two facilities and design a deterministic group strategyproof mechanism with approximation ratio 4. 

Bibliographic Note

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

Citation Format(s)

Heterogeneous Two-facility Location Games with Minimum Distance Requirement. / Duan, Lingjie; Li, Bo; Li, Minming; Xu, Xinping.

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. 1461-1469.

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