# Facility Location Games Beyond Single-Peakedness: the Entrance Fee Model

arXiv: https://arxiv.org/abs/2204.11282 · HTML: https://mlsanity.com/paper/2204.11282/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 29 references that are in the map.
- First posted on arXiv 24 Apr 2022.

## Builds on (most cited first, 9 of 9)

- [Mechanism Design for Facility Location Problems: A Survey](https://mlsanity.com/paper/2106.03457/) (2021)
- [Facility Location Problem with Capacity Constraints: Algorithmic and Mechanism Design Perspectives](https://mlsanity.com/paper/1911.09813/) (2019)
- [The Capacity Constrained Facility Location problem](https://mlsanity.com/paper/1806.00960/) (2018)
- [Strategyproof Mechanisms For Group-Fair Facility Location Problems](https://mlsanity.com/paper/2107.05175/) (2021)
- [Strategyproof Mechanisms for One-Dimensional Hybrid and Obnoxious Facility Location](https://mlsanity.com/paper/1412.3414/) (2014)
- [Strategy Proof Mechanisms for Facility Location with Capacity Limits](https://mlsanity.com/paper/2009.07986/) (2020)
- [Heterogeneous Facility Location with Limited Resources](https://mlsanity.com/paper/2105.02712/) (2021)
- [On Discrete Truthful Heterogeneous Two-Facility Location](https://mlsanity.com/paper/2109.04234/) (2021)
- [Strategyproof Mechanism for Two Heterogeneous Facilities with Constant Approximation Ratio](https://mlsanity.com/paper/1907.08918/) (2019)

## Abstract (arXiv)

The facility location game has been studied extensively in mechanism design. In the classical model, each agent's cost is solely determined by her distance to the nearest facility. In this paper, we introduce a novel model where each facility charges an entrance fee. Thus, the cost of each agent is determined by both the distance to the facility and the entrance fee of the facility. In our model, the entrance fee function is allowed to be an arbitrary function, causing agents' preferences may no longer be single-peaked anymore: This departure from the classical model introduces additional challenges. We systematically delve into the intricacies of the model, designing strategyproof mechanisms with favorable approximation ratios. Additionally, we complement these ratios with nearly-tight impossibility results. Specifically, for one-facility and two-facility games, we provide upper and lower bounds for the approximation ratios given by deterministic and randomized mechanisms with respect to utilitarian and egalitarian objectives.