Voting schemes for which it can be difficult to tell who won the election

By J. BartholdiIII, Craig A. Tovey, Michael A. Trick. 1989

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

A Short Introduction to Computational Social Choice (2007, background): “[10], and ∆2 (O(log n))-complete by Hemaspaandra et al.”
Single transferable vote resists strategic voting (2015, background): “In [4] it was observed that voting schemes due to Dodgson and to Kemeny had the undesirable property that it is NP-hard to tell whether any particular candidate has won the election.”
When are elections with few candidates hard to manipulate? (2007, methodology): “…as we pointed out in the Introduction.6 (Manipulation by individuals in the complete information setting is hard for some voting protocols if one allows the number of voters and the number of candidates to be unbounded [Bartholdi et al. 1989a; Bartholdi and Orlin 1991; Conitzer and Sandholm 2003].”
Label ranking by learning pairwise preferences (2008, background): “In fact, the computation of Kemeny-optimal rankings is known to be NP-hard [6].”
Aggregating inconsistent information: ranking and clustering (2005, background): “Finding a Ke-meny optimal ranking is NP-hard [7] and remains NP-hard even when there are only four input lists to aggregate [14].”
Properties of multiwinner voting rules (2014, unknown): “Among the few examples of prominent non-monotonic single-winner rules are STV and the Dodgson rule (see, e.g., the work of Brandt 2009).”
Multiwinner Voting: A New Challenge for Social Choice Theory (2017, background): “In the single-winner setting, almost all prominent voting rules are polynomial time computable (although there are important exceptions, such as the rules of Dodgson, Young, and Kemeny (Bartholdi et al., 1989; Hemaspaandra et al., 1997; Rothe et al., 2003; Hemaspaandra et al., 2005)).”