Strategyproof mechanisms for 2-facility location games with minimax envy

Xin Chen (), Qizhi Fang (), Wenjing Liu (), Yuan Ding () and Qingqin Nong ()
Additional contact information
Xin Chen: Ocean University of China
Qizhi Fang: Ocean University of China
Wenjing Liu: Ocean University of China
Yuan Ding: Ocean University of China
Qingqin Nong: Ocean University of China

Journal of Combinatorial Optimization, 2022, vol. 43, issue 5, No 33, 1628-1644

Abstract: Abstract We study a fairness-based model for 2-facility location games on the real line where the social objective is to minimize the maximum envy over all agents. All the agents seek to minimize their personal costs, and the envy between any two of them is the difference in their personal costs. We consider two cases of personal costs, called min-dist cost and sum-dist cost. We are interested in pursuing strategyproof mechanisms for 2-facility location games in both cases. For the min-dist personal cost, we first show that a lower bound of the additive approximation for any deterministic strategyproof mechanism is 1/4, then devise a deterministic group strategyproof mechanism with additive approximation of 1/2 and two randomized strategyproof mechanisms with additive approximation of 1/4. For the sum-dist personal cost, we devise a group strategyproof deterministic mechanism which is also optimal.

Keywords: Facility location game; Mechanism design; Maximum envy; Fairness (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-021-00711-7 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:43:y:2022:i:5:d:10.1007_s10878-021-00711-7

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

DOI: 10.1007/s10878-021-00711-7

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