Discrete facility location games with different preferences

Ling Gai (), Mengpei Liang () and Chenhao Wang ()
Additional contact information
Ling Gai: University of Shanghai for Science and Technology
Mengpei Liang: Donghua University
Chenhao Wang: Beijing Normal University

Journal of Combinatorial Optimization, 2023, vol. 46, issue 2, No 8, 17 pages

Abstract: Abstract We study the mechanism design for discrete facility location games with different preferences, where the facilities can only be built at a finite set of candidate locations, and a mechanism maps the agent locations to candidate locations for building facilities. We consider both the obnoxious preferences, where the agents want to stay as far away as possible from the facilities, and the dual preferences, where each agent may either like or dislike a facility. When the preferences are obnoxious, for two heterogeneous facilities, we present a group strategy-proof mechanism which has an approximation ratio of 2 for both social utility objective and minimum utility objective. Both objectives are proven to have a lower bound of $$\frac{3}{2}$$ 3 2 . For two homogeneous facilities, we prove there is no deterministic strategy-proof mechanism with bounded approximation ratio. When the preferences are dual, we consider the single facility location games under the social utility objective, and propose a group strategy-proof mechanism with approximation ratio of 4.

Keywords: Facility location game; Mechanism design; Strategyproofness; Approximation ratio; 91A68; 91B03; 68W25 (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-023-01082-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:46:y:2023:i:2:d:10.1007_s10878-023-01082-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-023-01082-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().