Facility location games with optional preference

Zhihuai CHEN, Ken C.K. FONG, Minming LI, Kai WANG*, Hongning YUAN, Yong ZHANG

*Corresponding author for this work

Research output: Journal PublicationsJournal Article (refereed)peer-review

6 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)185-197
Number of pages13
JournalTheoretical Computer Science
Volume847
DOIs
Publication statusPublished - 22 Dec 2020
Externally publishedYes

Bibliographical note

Funding Information:
We would like to thank the anonymous reviewers for their pertinent and insightful comments. This research was partially supported by the National Natural Science Foundation of China Grants No. 12071460 , No. 61832003 , 61761136014 , 61872334 , the 973 Program of China Grant No. 2016YFB1000201 and K. C. Wong Education Foundation . Minming Li is also from City University of Hong Kong Shenzhen Research Institute , Shenzhen, P. R. China. The work described in this paper was supported by a grant from Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. CityU 11200518 ) and was partially sponsored by Project 11771365 supported by NSFC .

Keywords

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

Fingerprint

Dive into the research topics of 'Facility location games with optional preference'. Together they form a unique fingerprint.

Cite this