# Determining Possible and Necessary Winners Given Partial Orders

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jan 2014.

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

- [DeepGroup: Representation Learning for Group Recommendation with Implicit Feedback](https://mlsanity.com/paper/2103.07597/) (2021)
- [On the Complexity of Finding a Diverse and Representative Committee using a Monotone, Separable Positional Multiwinner Voting Rule](https://mlsanity.com/paper/2211.13217/) (2022)
- [Determining Winners in Elections with Absent Votes](https://mlsanity.com/paper/2310.07150/) (2023)

## Abstract (arXiv)

Usually a voting rule requires agents to give their preferences as linear orders. However, in some cases it is impractical for an agent to give a linear order over all the alternatives. It has been suggested to let agents submit partial orders instead. Then, given a voting rule, a profile of partial orders, and an alternative (candidate) c, two important questions arise: first, is it still possible for c to win, and second, is c guaranteed to win? These are the possible winner and necessary winner problems, respectively. Each of these two problems is further divided into two sub-problems: determining whether c is a unique winner (that is, c is the only winner), or determining whether c is a co-winner (that is, c is in the set of winners). We consider the setting where the number of alternatives is unbounded and the votes are unweighted. We completely characterize the complexity of possible/necessary winner problems for the following common voting rules: a class of positional scoring rules (including Borda), Copeland, maximin, Bucklin, ranked pairs, voting trees, and plurality with runoff.