Facility location games with optional preference

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

Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review

20 Citations (Scopus)

Abstract

In this paper, we propose the optional preference model for the facility location game with two heterogeneous facilities on a line. Agents in this new model are allowed to have optional preference, which gives more flexibility for agents to report. Aiming at minimizing maximum cost or sum cost of agents, we propose different deterministic strategy-proof mechanisms without monetary transfers. Depending on which facility the agent with optional preference cares for, we consider two variants of the optional preference model: Min (caring for the closer one) and Max (caring for the further one). For the Min variant, we propose a 2-approximation mechanism for the maximum cost objective, as well as a lower bound of 4/3, and a (n/2+1)-approximation mechanism for the sum cost objective, as well as a lower bound of 2. For Max variant, we propose an optimal mechanism for the maximum cost objective and a 2-approximation mechanism for the sum cost objective.

Original languageEnglish
Title of host publicationECAI 2016
EditorsGal A. KAMINKA, Frank DIGNUM, Eyke HÜLLERMEIER, Paolo BOUQUET, Virginia DIGNUM, Maria FOX, Frank VAN HARMELEN
Place of PublicationNetherlands
PublisherIOS Press
Pages1520-1527
Number of pages8
ISBN (Electronic)9781614996729
ISBN (Print)9781614996712
DOIs
Publication statusPublished - 2016
Externally publishedYes
Event22nd European Conference on Artificial Intelligence, ECAI 2016 - The Hague, Netherlands
Duration: 29 Aug 20162 Sep 2016

Publication series

NameFrontiers in Artificial Intelligence and Applications
Volume285
ISSN (Print)0922-6389

Conference

Conference22nd European Conference on Artificial Intelligence, ECAI 2016
Country/TerritoryNetherlands
CityThe Hague
Period29/08/162/09/16

Bibliographical note

This research was partially supported by NSFC 61433012 and a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China [Project No. CityU 117913].

Fingerprint

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

Cite this