Facility location games with optional preference

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

14 Scopus Citations
View graph of relations

Author(s)

  • Zhihuai Chen
  • Kai Wang
  • Hongning Yuan
  • Yong Zhang

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)185-197
Journal / PublicationTheoretical Computer Science
Volume847
Online published13 Oct 2020
Publication statusPublished - 22 Dec 2020

Abstract

In this paper, we study the optional preference model of the facility location game problem with two heterogeneous facilities on a line. The preference of each agent is one of the two facilities or both facilities, and the cost of each agent is a function of the distances to the facilities that the agent prefers. We consider two cost functions: Minimum Distance and Maximum Distance functions. Aiming at minimizing the maximum cost or the social cost of agents, we propose different strategyproof mechanisms without monetary transfers and derive both lower and upper bounds of the approximation ratios with respect to strategyproof mechanisms. In the variant of Minimum Distance, we propose a 2-approximation deterministic strategyproof mechanism for the maximum cost objective, and prove a lower bound of 4/3, while for the social cost objective we propose a (n/2+1)-approximation deterministic strategyproof mechanism and prove a lower bound of 2, also a lower bound of 3/2 for randomized mechanisms. In the variant of Maximum Distance, we propose an optimal deterministic strategyproof mechanism for the maximum cost objective and a 2-approximation deterministic strategyproof mechanism for the social cost objective.

Research Area(s)

  • Algorithmic mechanism design, Approximation, Facility location game, Game theory

Citation Format(s)

Facility location games with optional preference. / Chen, Zhihuai; Fong, Ken C.K.; Li, Minming et al.
In: Theoretical Computer Science, Vol. 847, 22.12.2020, p. 185-197.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review