Mechanism Design for Two-Opposite-Facility Location Games with Penalties on Distance

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

Related Research Unit(s)

Detail(s)

Original languageEnglish
Title of host publicationAlgorithmic Game Theory
Subtitle of host publication11th International Symposium, SAGT 2018, Proceedings
EditorsXiaotie Deng
PublisherSpringer, Cham
Pages256-260
ISBN (Electronic)9783319996608
ISBN (Print)9783319996592
Publication statusPublished - Sep 2018

Publication series

NameLecture Notes in Computer Science (including subseries Information Systems and Applications, incl. Internet/Web, and HCI)
PublisherSpringer, Cham
VolumeLNCS 11059
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Title11th International Symposium on Algorithmic Game Theory, SAGT 2018
PlaceChina
CityBeijing
Period11 - 14 September 2018

Abstract

This paper is devoted to the two-opposite-facility location games with a penalty whose amount depends on the distance between the two facilities to be opened by an authority. The two facilities are “opposite” in that one is popular and the other is obnoxious. Every selfish agent in the game wishes to stay close to the popular facility and stay away from the obnoxious one; its utility is measured by the difference between its distances to the obnoxious facility and the popular one. The authority determines the locations of the two facilities on a line segment where all agents are located. Each agent has its location information as private, and is required to report its location to the authority. Using the reported agent locations as input, an algorithmic mechanism run by the authority outputs the locations of the two facilities with an aim to maximize certain social welfare. The sum-type social welfare concerns with the penalized total utility of all agents, for which we design both randomized and deterministic group strategy-proof mechanisms with provable approximation ratios, and establish a lower bound on the approximation ratio of any deterministic strategy-proof mechanism. The bottleneck-type social welfare concerns with the penalized minimum utility among all agents, for which we propose a deterministic group strategy-proof mechanism that ensures optimality.

Research Area(s)

  • Facility location game, Strategy-proof mechanism design

Citation Format(s)

Mechanism Design for Two-Opposite-Facility Location Games with Penalties on Distance. / Chen, Xujin; Hu, Xiaodong; Jia, Xiaohua; Li, Minming; Tang, Zhongzheng; Wang, Chenhao.

Algorithmic Game Theory: 11th International Symposium, SAGT 2018, Proceedings. ed. / Xiaotie Deng. Springer, Cham, 2018. p. 256-260 (Lecture Notes in Computer Science (including subseries Information Systems and Applications, incl. Internet/Web, and HCI); Vol. LNCS 11059).

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