Facility Location Game with Envy Ratio
2026-07-02 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors study a game where a single facility is placed on a line, and people want to be close to it. They introduce a new fairness measure called the envy ratio, which compares how satisfied people are relative to each other. The authors explore rules for placing the facility that prevent people from lying about their location to gain advantage, called strategyproof mechanisms. They analyze two scenarios about where people and the facility can be placed and find the best possible fair rules in each. They also provide limits on how well random rules can perform in these scenarios.
one-facility location gamereal lineenvy ratiostrategyproof mechanismgroup strategyproofegalitarianismfacility locationrandomized mechanismslower and upper bounds
Authors
Yuan Ding, Wenjing Liu, Xin Chen, Qizhi Fang, Qingqin Nong
Abstract
We study the one-facility location game on a real line with a new objective called envy ratio. The envy ratio, which is adopted from fair division and represents the egalitarianism, is defined as the maximum over the ratios between any two agents' utilities. We are interested in strategyproof or group strategyproof mechanisms that can minimize the envy ratio objective. We consider the model in two settings that can capture natural scenarios: the facility location and all the agents' locations are restricted on a fixed interval; every agent's location can be any point on the real line but the facility location is restricted on a relative interval. In both settings, we obtain the optimal solution and the best deterministic strategyproof mechanism which is also group strategyproof. In the first setting, we provide a lower bound for randomized strategyproof mechanisms. In the second setting, we give a lower bound and two upper bounds for randomized strategyproof mechanisms.