AI summaryⓘ
The authors study how to fairly place a single facility based on where people (agents) say they are located, aiming to minimize the worst distance anyone has to travel, while making sure agents have no incentive to lie. They find that in one dimension, a simple randomized method can perfectly minimize the expected worst distance, better than any fixed choice. In two dimensions, they design a new mechanism that improves fairness when looking at expected costs before knowing random outcomes, but such improvement is impossible when evaluating costs after outcomes. For many dimensions, no randomized method beats a simple dictator approach for fairness, meaning the best known methods for average cost also work best for fairness in high dimensions. Their work highlights differences between evaluating fairness before and after randomness and shows limits of improvement with more dimensions.
facility location problemstrategyproofnessegalitarian costapproximation ratiorandomized mechanismsex-ante evaluationex-post evaluationhigh-dimensional geometrydictator mechanismcoordinate-wise median
Abstract
We study the facility location mechanism design problem where $n$ strategic agents report locations in Euclidean space and the mechanism outputs a single facility location. Each agent's cost is its distance from the facility, and our objective is to minimize the egalitarian cost, i.e., the maximum agent cost, in a strategyproof way. The optimal deterministic approximation ratio is $2$, achieved by any dictator mechanism. We study the power of randomized strategyproof-in-expectation mechanisms. Prior work has focused on ex-post evaluation, defined as the expected maximum agent cost. We instead study ex-ante evaluation, defined as the maximum expected agent cost, which is naturally aligned with strategyproofness in expectation. We establish the following results: (1) Low dimensions: Strict ex-ante vs. ex-post separation. In $\mathbb{R}$, we give a simple strategyproof mechanism achieving the optimal ex-ante approximation ratio of $1$. In $\mathbb{R}^2$, we design the "Random Rotated Corner" mechanism, with ex-ante approximation ratio at most $1.598$, breaking the deterministic barrier. For the ex-post objective, we prove a lower bound of $1.605$, yielding a strict separation in $\mathbb{R}^2$. (2) High dimensions: Impossibility. In $\mathbb{R}^d$ for $d \gg 1$, we show that no strategyproof-in-expectation mechanism improves on the deterministic dictator mechanism beyond $o_d(1)$. Thus neither ex-post nor ex-ante evaluation yields improved fairness guarantees in high dimensions. An implication is that the "Random Rotation Coordinate-Wise Median" (RRCWM), currently the best known mechanism for the utilitarian objective, is also best possible for the egalitarian objective in high dimension: we show it achieves an approximation ratio of $2$ for both ex-post and ex-ante objectives in $\mathbb{R}^d$ for every $d \ge 1$.