Mechanism design for two-opposite-facility location games with penalties on distance
From MaRDI portal
Publication:1617675
DOI10.1007/978-3-319-99660-8_24zbMATH Open1415.91066arXiv1806.08057OpenAlexW2809588553MaRDI QIDQ1617675FDOQ1617675
Authors: Xiaodong Hu, Minming Li, Zhongzheng Tang, Xujin Chen, X.-H. Jia, Chenhao Wang 
Publication date: 8 November 2018
Abstract: This paper is devoted to the two-opposite-facility location games with a penalty whose amount depends on the distance between the two facilities to be opened by an authority. The two facilities are "opposite" in that one is popular and the other is obnoxious. Every selfish agent in the game wishes to stay close to the popular facility and stay away from the obnoxious one; its utility is measured by the difference between its distances to the obnoxious facility and the popular one. The authority determines the locations of the two facilities on a line segment where all agents are located. Each agent has its location information as private, and is required to report its location to the authority. Using the reported agent locations as input, an algorithmic mechanism run by the authority outputs the locations of the two facilities with an aim to maximize certain social welfare. The sum-type social welfare concerns with the penalized total utility of all agents, for which we design both randomized and deterministic group strategy-proof mechanisms with provable approximation ratios, and establish a lower bound on the approximation ratio of any deterministic strategy-proof mechanism. The bottleneck-type social welfare concerns with the penalized minimum utility among all agents, for which we propose a deterministic group strategy-proof mechanism that ensures optimality.
Full work available at URL: https://arxiv.org/abs/1806.08057
Recommendations
- Two-facility location games with minimum distance requirement
- Tight efficiency lower bounds for strategy-proof mechanisms in two-opposite-facility location game
- Mechanism Design for One-Facility Location Game with Obnoxious Effects
- Mechanism design for one-facility location game with obnoxious effects on a line
- Mechanisms for obnoxious facility game on a path
Cited In (15)
- Multiple facility location games with envy ratio
- Tight efficiency lower bounds for strategy-proof mechanisms in two-opposite-facility location game
- Constrained heterogeneous two-facility location games with sum-variant
- Strategyproof facility location with limited locations
- Multiple facility location games with envy ratio
- Two-facility location games with distance requirement
- Two-facility location games with a minimum distance requirement on a circle
- Strategyproof mechanisms for \(2\)-facility location games with minimax envy
- A cost-sharing scheme for the \(k\)-level facility location game with penalties
- Approximation algorithms for the capacitated correlation clustering problem with penalties
- Mechanism design for facility location with fractional preferences and minimum distance
- Approximation algorithm for the capacitated correlation clustering problem with penalties
- Two-facility location games with minimum distance requirement
- Two homogeneous facility location games with a minimum distance requirement on a circle
- Facility location games with optional preference
This page was built for publication: Mechanism design for two-opposite-facility location games with penalties on distance
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1617675)
