Strategy-proof mechanisms for maximizing social satisfaction in the facility location game

Xiaowei Li and Xiwen Lu ()
Additional contact information
Xiaowei Li: Changsha University of Science and Technology
Xiwen Lu: East China University of Science and Technology

Journal of Combinatorial Optimization, 2025, vol. 50, issue 2, No 1, 20 pages

Abstract: Abstract The facility location game, where the agents’ locations are on a line, is considered in this paper. The input consists of the reported locations of agents, which are collected as part of the game setup. We introduce the concept of a fairness baseline and define a function to characterize each agent’s satisfaction with the facility location. Our objective is to establish a mechanism that obtains the true information of agents and outputs a single facility location so that the sum of all agents’ satisfaction with the location is maximized. For the game with two agents, we propose a $$\frac{5}{4}$$ -approximate strategy-proof mechanism, which is the best possible. In the general case, we demonstrate that the median mechanism achieves an approximation ratio of $$\frac{3}{2}$$ . In particular, the median mechanism is an optimal group strategy-proof mechanism for the game with three agents. Additionally, we devise a $$\frac{1+\sqrt{3}}{2}$$ -approximation group strategy-proof mechanism by modifying the median mechanism. We also consider social satisfaction in the obnoxious facility location game and design a mechanism based on the median of the input.

Keywords: Facility location game; Algorithmic mechanism design; Strategyproofness; Approximation ratio (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-025-01341-z 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:50:y:2025:i:2:d:10.1007_s10878-025-01341-z

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

DOI: 10.1007/s10878-025-01341-z

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 ().