Constrained heterogeneous two-facility location games with sum-variant

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, 2024, vol. 47, issue 4, No 12, 21 pages

Abstract: Abstract We study deterministic mechanism design for constrained heterogeneous two-facility location games. The constraint here means that the feasible locations of facilities are specified and the number of facilities that can be built at each feasible location is limited. Given that a set of agents can strategically report their locations on the real line, the authority wants to design strategyproof mechanisms (i.e., mechanisms that can incentivize agents to report truthful private information) to construct two heterogeneous facilities under constraint, while optimizing the corresponding social objectives. Assuming that each agent’s individual objective depends on the sum of her distance to facilities, we consider locating desirable and obnoxious facilities respectively. For the former, we give a deterministic group strategyproof mechanism, which guarantees 3-approximation under the objectives of minimizing the sum cost and the maximum cost. We show that no deterministic strategyproof mechanism can have an approximation ratio of less than 2 under the sum/maximum cost objective. For the latter, we give a deterministic group strategyproof mechanism with 2-approximation under the objectives of maximizing the sum utility and the minimum utility. We show that no deterministic strategyproof mechanism can have an approximation ratio of less than 3/2 under the sum utility objective and 2 under the minimum utility objective, respectively.

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

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01163-5 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:47:y:2024:i:4:d:10.1007_s10878-024-01163-5

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

DOI: 10.1007/s10878-024-01163-5

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