Dodgson's method

Last updated

Dodgson's method is an electoral system proposed by the author, mathematician and logician Charles Dodgson, better known as Lewis Carroll. The method is to extend the Condorcet method by swapping candidates until a Condorcet winner is found. The winner is the candidate which requires the minimum number of swaps. Dodgson proposed this voting scheme in his 1876 work "A method of taking votes on more than two issues". Given an integer k and an election, it is NP-complete to determine whether a candidate can become a Condorcet winner with fewer than k swaps.

Description

In Dodgson's method, each voter submits an ordered list of all candidates according to their own preference (from best to worst). The winner is defined to be the candidate for whom we need to perform the minimum number of pairwise swaps in each ballot (added over all candidates) before they become a Condorcet winner. In particular, if there is already a Condorcet winner, they win the election.

In short, we must find the voting profile with minimum Kendall tau distance from the input, such that it has a Condorcet winner; then, the Condorcet winner is declared the victor. Computing the winner or even the Dodgson score of a candidate (the number of swaps needed to make that candidate a winner) is an NP-hard problem [1] by reduction from Exact Cover by 3-Sets (X3C). [2]

Related Research Articles

Strategic voting, also called tactical voting, sophisticated voting or insincere voting, occurs in voting systems when a voter votes for another candidate or party than their sincere preference to prevent an undesirable outcome. For example, in a simple plurality election, a voter might gain a better outcome by voting for a less preferred but more generally popular candidate.

The Condorcet paradox in social choice theory is a situation noted by the Marquis de Condorcet in the late 18th century, in which collective preferences can be cyclic, even if the preferences of individual voters are not cyclic. This is paradoxical, because it means that majority wishes can be in conflict with each other: Suppose majorities prefer, for example, candidate A over B, B over C, and yet C over A. When this occurs, it is because the conflicting majorities are each made up of different groups of individuals.

<span class="mw-page-title-main">Condorcet method</span> Pairwise-comparison electoral system

A Condorcet method is an election method that elects the candidate who wins a majority of the vote in every head-to-head election against each of the other candidates, that is, a candidate preferred by more voters than any others, whenever there is such a candidate. A candidate with this property, the pairwise champion or beats-all winner, is formally called the Condorcet winner. The head-to-head elections need not be done separately; a voter's choice within any given pair can be determined from the ranking.

Copeland's method is a ranked voting method based on a scoring system of pairwise "wins", "losses", and "ties". The method has a long history:

In voting systems, the Smith set, named after John H. Smith, but also known as the top cycle, or as Generalized Top-Choice Assumption (GETCHA), is the smallest non-empty set of candidates in a particular election such that each member defeats every candidate outside the set in a pairwise election. The Smith set provides one standard of optimal choice for an election outcome. Voting systems that always elect a candidate from the Smith set pass the Smith criterion and are said to be 'Smith-efficient' or to satisfy the Smith criterion.

Ranked pairs or the Tideman method is an electoral system developed in 1987 by Nicolaus Tideman that selects a single winner using votes that express preferences. The ranked-pairs procedure can also be used to create a sorted list of winners.

The Schulze method is an electoral system developed in 1997 by Markus Schulze that selects a single winner using votes that express preferences. The method can also be used to create a sorted list of winners. The Schulze method is also known as Schwartz Sequential dropping (SSD), cloneproof Schwartz sequential dropping (CSSD), the beatpath method, beatpath winner, path voting, and path winner. The Schulze method is a Condorcet method, which means that if there is a candidate who is preferred by a majority over every other candidate in pairwise comparisons, then this candidate will be the winner when the Schulze method is applied.

An electoral system satisfies the Condorcet winner criterion if it always chooses the Condorcet winner when one exists. The candidate who wins a majority of the vote in every head-to-head election against each of the other candidates – that is, a candidate preferred by more voters than any others – is the Condorcet winner, although Condorcet winners do not exist in all cases. It is sometimes simply referred to as the "Condorcet criterion", though it is very different from the "Condorcet loser criterion". Any voting method conforming to the Condorcet winner criterion is known as a Condorcet method. The Condorcet winner is the person who would win a two-candidate election against each of the other candidates in a plurality vote. For a set of candidates, the Condorcet winner is always the same regardless of the voting system in question, and can be discovered by using pairwise counting on voters' ranked preferences.

The Borda count electoral system can be combined with an instant-runoff procedure to create hybrid election methods that are called Nanson method and Baldwin method. Both methods are designed to satisfy the Condorcet criterion, and allow for incomplete ballots and equal rankings.

CPO-STV, or the Comparison of Pairs of Outcomes by the Single Transferable Vote, is a ranked voting system designed to achieve proportional representation. It is a more sophisticated variant of the Single Transferable Vote (STV) system, designed to overcome some of that system's perceived shortcomings. It does this by incorporating some of the features of Condorcet's method, a voting system designed for single-winner elections, into STV. As in other forms of STV, in a CPO-STV election more than one candidate is elected and voters must rank candidates in order of preference. As of February 2021, it has not been used for a public election.

The Kemeny–Young method is an electoral system that uses preferential ballots and pairwise comparison counts to identify the most popular choices in an election. It is a Condorcet method because if there is a Condorcet winner, it will always be ranked as the most popular choice.

The later-no-harm criterion is a voting system criterion formulated by Douglas Woodall. Woodall defined the criterion as "[a]dding a later preference to a ballot should not harm any candidate already listed." For example, a ranked voting method in which a voter adding a 3rd preference could reduce the likelihood of their 1st preference being selected, fails later-no-harm.

The Borda count is a family of positional voting rules which gives each candidate, for each ballot, a number of points corresponding to the number of candidates ranked lower. In the original variant, the lowest-ranked candidate gets 0 points, the next-lowest gets 1 point, etc., and the highest-ranked candidate gets n − 1 points, where n is the number of candidates. Once all votes have been counted, the option or candidate with the most points is the winner. The Borda count is intended to elect broadly acceptable options or candidates, rather than those preferred by a majority, and so is often described as a consensus-based voting system rather than a majoritarian one.

Instant-runoff voting (IRV) is a type of ranked preferential voting method. It uses a majority voting rule in single-member districts in which there are more than two candidates.

<span class="mw-page-title-main">Electoral system</span> Method by which voters make a choice between options

An electoral system or voting system is a set of rules that determine how elections and referendums are conducted and how their results are determined. Electoral systems are used in politics to elect governments, while non-political elections may take place in business, non-profit organisations and informal organisations. These rules govern all aspects of the voting process: when elections occur, who is allowed to vote, who can stand as a candidate, how ballots are marked and cast, how the ballots are counted, how votes translate into the election outcome, limits on campaign spending, and other factors that can affect the result. Political electoral systems are defined by constitutions and electoral laws, are typically conducted by election commissions, and can use multiple types of elections for different offices.

<span class="mw-page-title-main">Ranked voting</span> Family of electoral systems

The term ranked voting, also known as preferential voting or ranked choice voting refers to any voting system in which voters rank their candidates or options—in a sequence of first, second, third, and so on—on their respective ballots. Ranked voting systems differ on the basis of how the ballots are marked, how the preferences are tabulated and counted, how many seats are filled, and whether voters are allowed to rank candidates equally. An electoral system that uses ranked voting uses one of the many available counting methods to select the winning candidate or candidates. There is also variation among ranked voting electoral systems in that in some ranked voting systems, officials require voters to rank a set number of candidates, sometimes all of them; in others, citizens may rank as many candidates as they see fit.

The later-no-help criterion is a voting system criterion formulated by Douglas Woodall. The criterion is satisfied if, in any election, a voter giving an additional ranking or positive rating to a less-preferred candidate can not cause a more-preferred candidate to win. Voting systems that fail the later-no-help criterion are vulnerable to the tactical voting strategy called mischief voting, which can deny victory to a sincere Condorcet winner.

Computational social choice is a field at the intersection of social choice theory, theoretical computer science, and the analysis of multi-agent systems. It consists of the analysis of problems arising from the aggregation of preferences of a group of agents from a computational perspective. In particular, computational social choice is concerned with the efficient computation of outcomes of voting rules, with the computational complexity of various forms of manipulation, and issues arising from the problem of representing and eliciting preferences in combinatorial settings.

Electoral systems are the rules for conducting elections, a main component of which is the algorithm for determining the winner from the ballots cast. This article discusses methods and results of comparing different electoral systems, both those that elect a unique candidate in a 'single-winner' election and those that elect a group of representatives in a multiwinner election.

Multiwinner voting, also called multiple-winner elections or committee voting or committee elections, is an electoral system in which multiple candidates are elected. The number of elected candidates is usually fixed in advance. For example, it can be the number of seats in a country's parliament, or the required number of members in a committee.

References

  1. Bartholdi, J.; Tovey, C. A.; Trick, M. A. (April 1989). "Voting schemes for which it can be difficult to tell who won the election". Social Choice and Welfare. 6 (2): 157–165. doi:10.1007/BF00303169. S2CID   154114517. The article only directly proves NP-hardness, but it is clear that the decision problem is in NP since given a candidate and a list of k swaps, you can tell whether that candidate is a Condorcet winner in polynomial time.
  2. Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability . W.H. Freeman Co., San Francisco. ISBN   9780716710455.