# Sampling-Based Winner Prediction in District-Based Elections

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 29 references that are in the map.
- First posted on arXiv 28 Feb 2022.

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

- [Eliciting Single-Peaked Preferences Using Comparison Queries](https://mlsanity.com/paper/1401.3449/) (2014)
- [Sample Complexity for Winner Prediction in Elections](https://mlsanity.com/paper/1502.04354/) (2015)
- [Estimating the Margin of Victory of an Election using Sampling](https://mlsanity.com/paper/1505.00566/) (2015)
- [Elicitation for Preferences Single Peaked on Trees](https://mlsanity.com/paper/1604.04403/) (2016)
- [Preference Elicitation For Single Crossing Domain](https://mlsanity.com/paper/1604.05194/) (2016)

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

- [Subset Selection Based On Multiple Rankings in the Presence of Bias: Effectiveness of Fairness Constraints for Multiwinner Voting Score Functions](https://mlsanity.com/paper/2306.09835/) (2023)
- [Query-efficient winner prediction in district-based elections](https://mlsanity.com/paper/2610.00577/) (2026)

## Abstract (arXiv)

In a district-based election, we apply a voting rule r to decide the winners in each district, and a candidate who wins in a maximum number of districts is the winner of the election. We present efficient sampling-based algorithms to predict the winner of such district-based election systems in this paper. When r is plurality and the margin of victory is known to be at least varepsilon fraction of the total population, we present an algorithm to predict the winner. The sample complexity of our algorithm is Oleft(frac1varepsilon4log frac1varepsilonlogfrac1δright). We complement this result by proving that any algorithm, from a natural class of algorithms, for predicting the winner in a district-based election when r is plurality, must sample at least Omegaleft(frac1varepsilon4logfrac1δright) votes. We then extend this result to any voting rule r. Loosely speaking, we show that we can predict the winner of a district-based election with an extra overhead of Oleft(frac1varepsilon2logfrac1δright) over the sample complexity of predicting the single-district winner under r. We further extend our algorithm for the case when the margin of victory is unknown, but we have only two candidates. We then consider the median voting rule when the set of preferences in each district is single-peaked. We show that the winner of a district-based election can be predicted with Oleft(frac1varepsilon4logfrac1varepsilonlogfrac1δright) samples even when the harmonious order in different districts can be different and even unknown. Finally, we also show some results for estimating the margin of victory of a district-based election within both additive and multiplicative error bounds.