Constrained heterogeneous two-facility location games with max-variant cost

DOI10.1007/978-3-031-20796-9_3MaRDI QIDQ6166872zbMATH OpenFDO

Authors Qi Zhao, Wenjing Liu, Qizhi Fang, Qingqin Nong

Publication date 3 August 2023

Published in Frontiers of Algorithmic Wisdom (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2207.03026

zbMATH Keywords

facility locationmechanism designconstrainedstrategyproof

Mathematics Subject Classification ID

Applications of game theory (91A80) Discrete location and assignment (90B80) Mechanism design theory (91B03)

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 location is limited. Supposing that a set of agents on the real line can strategically report their locations and each agent's cost is her distance to the further facility that she is interested in, we study deterministic mechanism design without money for constrained heterogeneous two-facility location games. Depending on whether agents have optional preference, the problem is considered in two settings: the compulsory setting and the optional setting. In the compulsory setting where each agent is served by the two heterogeneous facilities, we provide a 3-approximate deterministic group strategyproof mechanism for the sum/maximum cost objective respectively, which is also the best deterministic strategyproof mechanism under the corresponding social objective. In the optional setting where each agent can be interested in one of the two facilities or both, we propose a deterministic group strategyproof mechanism with approximation ratio of at most $2n+1$ for the sum cost objective and a deterministic group strategyproof mechanism with approximation ratio of at most 9 for the maximum cost objective.

Recommendations

• Constrained heterogeneous facility location games with max-variant cost
• Constrained heterogeneous two-facility location games with sum-variant
• Two-facility location games with minimum distance requirement
• Facility location games with optional preference
• Heterogeneous facility location without money

Cites work

• Approximately Optimal Mechanisms for Strategyproof Facility Location: Minimizing L_p Norm of Costs
• Facility location games with distinct desires
• Facility location games with optional preference
• Heterogeneous facility location without money
• Mechanism design for facility location games with candidate locations
• Multiple facility location games with envy ratio
• Multiple facility location games with envy ratio
• On the power of deterministic mechanisms for facility location games
• Strategy-proof approximation mechanisms for an obnoxious facility game on networks
• Strategy-proof location on a network
• Strategyproof mechanism design for facility location games with weighted agents on a line
• Strategyproof mechanisms for 2-facility location games with minimax envy
• The capacity constrained facility location problem
• Tight efficiency lower bounds for strategy-proof mechanisms in two-opposite-facility location game
• Two-facility location games with minimum distance requirement

Cited in

(5)

• Two-facility-location games with mixed types of agents
• Constrained heterogeneous two-facility location games with sum-variant
• Constrained heterogeneous facility location games with max-variant cost
• A cross-monotonic cost-sharing scheme for the concave facility location game
• Bounding quality of pure Nash equilibria in dual-role facility location games

This page was built for publication: Constrained heterogeneous two-facility location games with max-variant cost

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6166872)