# Algorithmic Techniques for Necessary and Possible Winners

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 May 2020.

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

- [DiRe Committee : Diversity and Representation Constraints in Multiwinner Elections](https://mlsanity.com/paper/2107.07356/) (2021)
- [Fairly Allocating Utility in Constrained Multiwinner Elections](https://mlsanity.com/paper/2211.12820/) (2022)

## Abstract (arXiv)

We investigate the practical aspects of computing the necessary and possible winners in elections over incomplete voter preferences. In the case of the necessary winners, we show how to implement and accelerate the polynomial-time algorithm of Xia and Conitzer. In the case of the possible winners, where the problem is NP-hard, we give a natural reduction to Integer Linear Programming (ILP) for all positional scoring rules and implement it in a leading commercial optimization solver. Further, we devise optimization techniques to minimize the number of ILP executions and, oftentimes, avoid them altogether. We conduct a thorough experimental study that includes the construction of a rich benchmark of election data based on real and synthetic data. Our findings suggest that, the worst-case intractability of the possible winners notwithstanding, the algorithmic techniques presented here scale well and can be used to compute the possible winners in realistic scenarios.