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

DOI10.1007/978-3-031-20796-9_3zbMATH Open1529.90050arXiv2207.03026MaRDI QIDQ6166872FDOQ6166872

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)

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.

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

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

zbMATH Keywords

facility locationmechanism designconstrainedstrategyproof

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

• 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
• Two-facility-location games with mixed types of agents

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)