Proportionality-based fairness and strategyproofness in the facility location problem

Abstract

We focus on a simple, one-dimensional collective decision problem (often referred to as the facility location problem) and explore issues of strategyproofness and proportionality-based fairness. Our focus is on the Unanimous Fair Share (UFS) axiom—a strengthening of the proportionality axiom (as in Freeman et al., 2021) We characterize the family of strategyproof and UFS mechanisms and also strategyproof and proportional mechanisms. We show that imposing strategyproofness renders the combination of proportionality and unanimity to be equivalent to UFS. Furthermore, there is a unique mechanism that satisfies strategyproofness and UFS (or, equivalently, proportionality and unanimity): the Uniform Phantom mechanism, which is studied in Freeman et al. (2021). This result strengthens known characterizations in the literature. We also provide an alternative characterization of the outcomes of the Uniform Phantom mechanism as the unique (pure) Nash equilibrium outcome for any mechanism that satisfies continuity, strict monotonicity, and UFS. Finally, we analyze the approximation guarantees, in terms of optimal social welfare, obtained by mechanisms that are strategyproof and satisfy the UFS (and proportionality) axiom. We show that the Uniform Phantom mechanism provides the best approximation of the optimal social welfare among all mechanisms that satisfy UFS (or proportionality).