Minmax for facility location game with optional preference under minimum distance requirement

Xinping Xu (), Jingwen Zhang () and Lihua Xie ()
Additional contact information
Xinping Xu: Nanyang Technological University
Jingwen Zhang: City University of Hong Kong
Lihua Xie: Nanyang Technological University

Journal of Combinatorial Optimization, 2023, vol. 46, issue 4, No 1, 24 pages

Abstract: Abstract In this paper, we study the optional preference model for the facility location game with two heterogeneous facilities on a line interval [0, 1], by further enforcing the requirement of a minimum distance $$0\le d\le 1$$ 0 ≤ d ≤ 1 between the two facilities. Each agent has one of three favorable preferences towards the two facilities, i.e., facility 1, facility 2, or optional preference. Here, we consider two variants of the optional preference model: Min (caring for the closer one) and Max (caring for the further one). In both variants, each agent wishes to get close to his preferred facilities, and thus his cost is his distance to his preferred facility. In this game, we consider agents’ locations as public information and agents’ preferences as private information which needs to be reported by agents. The objective is to design a mechanism for the two facilities’ locations such as to minimize the maximum cost of agents (MinMax) and achieve truthful report of agents’ preferences. Given any value of d, for both variants, we propose a strategyproof mechanism with an approximation ratio of 2. We also establish lower bounds of any deterministic strategyproof mechanism for both variants and show that the gaps between the lower bounds and the upper bounds are relatively small.

Keywords: Maximum cost; Minimum distance requirement; Strategyproof mechanism; Approximation ratio; Facility Location Game (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-023-01087-6 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:4:d:10.1007_s10878-023-01087-6

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

DOI: 10.1007/s10878-023-01087-6

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