Constrained heterogeneous facility location games with max-variant cost

Qi Zhao (), Wenjing Liu (), Qingqin Nong () and Qizhi Fang ()
Additional contact information
Qi Zhao: Ocean University of China
Wenjing Liu: Ocean University of China
Qingqin Nong: Ocean University of China
Qizhi Fang: Ocean University of China

Journal of Combinatorial Optimization, 2023, vol. 45, issue 3, No 8, 20 pages

Abstract: Abstract In this paper, we propose a constrained heterogeneous facility location model where a set of alternative locations are feasible for building facilities and the number of facilities built at each feasible location is limited. Assuming that a set of agents on the real line can strategically report their locations, and the cost of each agent is her distance to the farthest one that she is interested in, we study deterministic mechanism design without money for constrained heterogeneous K-facility location games. Depending on whether agents have optional preference, the problem is considered in two settings: the compulsory setting and the optional setting. For the compulsory setting where all agents are served by K heterogeneous facilities, we provide a 3-approximate deterministic group strategyproof mechanism for the objective of minimizing the sum/maximum cost respectively, which is also the best deterministic strategyproof mechanism under the corresponding social objective. For the optional setting where each agent may be only interested in some of the facilities, we study heterogeneous two-facility location games. We propose a deterministic group strategyproof mechanism with approximation ratio of at most $$2n+1$$ 2 n + 1 for the sum cost objective and a deterministic group strategyproof mechanism with approximation ratio of at most 9 for the maximum cost objective.

Keywords: Mechanism design; Facility location; Strategyproof; Constrained (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-023-01017-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:45:y:2023:i:3:d:10.1007_s10878-023-01017-6

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

DOI: 10.1007/s10878-023-01017-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 ().