# Randomized Social Choice Functions Under Metric Preferences

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Dec 2015.

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

- [Plurality Veto: A Simple Voting Rule Achieving Optimal Metric Distortion](https://mlsanity.com/paper/2206.07098/) (2022)
- [Best of Both Distortion Worlds](https://mlsanity.com/paper/2305.19453/) (2023)
- [Breaking the Metric Voting Distortion Barrier](https://mlsanity.com/paper/2306.17838/) (2023)
- [Optimizing Multiple Simultaneous Objectives for Voting and Facility Location](https://mlsanity.com/paper/2212.03467/) (2022)
- [The Distortion of Binomial Voting Defies Expectation](https://mlsanity.com/paper/2306.15657/) (2023)

## Abstract (arXiv)

We determine the quality of randomized social choice mechanisms in a setting in which the agents have metric preferences: every agent has a cost for each alternative, and these costs form a metric. We assume that these costs are unknown to the mechanisms (and possibly even to the agents themselves), which means we cannot simply select the optimal alternative, i.e. the alternative that minimizes the total agent cost (or median agent cost). However, we do assume that the agents know their ordinal preferences that are induced by the metric space. We examine randomized social choice functions that require only this ordinal information and select an alternative that is good in expectation with respect to the costs from the metric. To quantify how good a randomized social choice function is, we bound the distortion, which is the worst-case ratio between expected cost of the alternative selected and the cost of the optimal alternative. We provide new distortion bounds for a variety of randomized mechanisms, for both general metrics and for important special cases. Our results show a sizable improvement in distortion over deterministic mechanisms.