Dodgson's method
Encyclopedia
Dodgson's Method is a voting system
Voting system
A voting system or electoral system is a method by which voters make a choice between options, often in an election or on a policy referendum....

 proposed by Charles Dodgson.

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 (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
Kendall tau distance
The Kendall tau distance is a metric that counts the number of pairwise disagreements between two lists. The larger the distance, the more dissimilar the two lists are. Kendall tau distance is also called bubble-sort distance since it is equivalent to the number of swaps that the bubble sort...

 from the input, such that it has a Condorcet winner; they are declared the victor. Computing the winner is an NP-hard
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...

problem.
The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK