# Optimizing Multiple Simultaneous Objectives for Voting and Facility Location

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 31 references that are in the map.
- First posted on arXiv 7 Dec 2022.

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

- [Distortion in Social Choice Problems: The First 15 Years and Beyond](https://mlsanity.com/paper/2103.00911/) (2021)
- [Mechanism Design for Facility Location Problems: A Survey](https://mlsanity.com/paper/2106.03457/) (2021)
- [Approximation Algorithms for Minimum Norm and Ordered Optimization Problems](https://mlsanity.com/paper/1811.05022/) (2018)
- [On Voting and Facility Location](https://mlsanity.com/paper/1512.05868/) (2015)
- [Resolving the Optimal Metric Distortion Conjecture](https://mlsanity.com/paper/2004.07447/) (2020)
- [Constant-Factor Approximation for Ordered k-Median](https://mlsanity.com/paper/1711.01972/) (2017)
- [Interpolating between k-Median and k-Center: Approximation Algorithms for Ordered k-Median](https://mlsanity.com/paper/1711.08715/) (2017)
- [Strategyproof and Proportionally Fair Facility Location](https://mlsanity.com/paper/2111.01566/) (2021)
- [Randomized Social Choice Functions Under Metric Preferences](https://mlsanity.com/paper/1512.07590/) (2015)
- [Relating Metric Distortion and Fairness of Social Choice Rules](https://mlsanity.com/paper/1810.01092/) (2018)
- [Strategy Proof Mechanisms for Facility Location at Limited Locations](https://mlsanity.com/paper/2009.07982/) (2020)
- [Mechanism Design for Facility Location Games with Candidate Locations](https://mlsanity.com/paper/2010.09640/) (2020)

## Built on by (most cited first, 2 of 2)

- [Compatibility of Max and Sum Objectives for Committee Selection and k-Facility Location](https://mlsanity.com/paper/2507.17063/) (2025)
- [Mechanism Design for Facility Location using Predictions](https://mlsanity.com/paper/2508.03818/) (2025)

## Abstract (arXiv)

We study the classic facility location setting, where we are given n clients and m possible facility locations in some arbitrary metric space, and want to choose a location to build a facility. The exact same setting also arises in spatial social choice, where voters are the clients and the goal is to choose a candidate or outcome, with the distance from a voter to an outcome representing the cost of this outcome for the voter (e.g., based on their ideological differences). Unlike most previous work, we do not focus on a single objective to optimize (e.g., the total distance from clients to the facility, or the maximum distance, etc.), but instead attempt to optimize several different objectives simultaneously. More specifically, we consider the l-centrum family of objectives, which includes the total distance, max distance, and many others. We present tight bounds on how well any pair of such objectives (e.g., max and sum) can be simultaneously approximated compared to their optimum outcomes. In particular, we show that for any such pair of objectives, it is always possible to choose an outcome which simultaneously approximates both objectives within a factor of 1+√2, and give a precise characterization of how this factor improves as the two objectives being optimized become more similar. For q>2 different centrum objectives, we show that it is always possible to approximate all q of these objectives within a small constant, and that this constant approaches 3 as qrightarrow ∞. Our results show that when optimizing only a few simultaneous objectives, it is always possible to form an outcome which is a significantly better than 3 approximation for all of these objectives.