Numbers Rule by Szpiro George; Szpiro George G. G.; Szpiro George G

Author:Szpiro, George; Szpiro, George G. G.; Szpiro, George G.
Language: eng
Format: epub
Publisher: Princeton University Press

Elector 2:

Alex > Dick > Carl > Bob

Elector 3:

Alex > Bob > Dick > Carl

Elector 4:

Alex > Bob > Dick > Carl

Elector 5:

Bob > Carl > Alex > Dick

Elector 6:

Bob > Carl > Alex > Dick

Elector 7:

Bob > Dick > Carl > Alex

Elector 8:

Carl > Bob > Dick > Alex

Elector 9:

Carl > Bob > Dick > Alex

Elector 10:

Carl > Bob > Dick > Alex

Elector 11:

Dick > Carl > Bob > Alex

In a traditional majority election, Alex would receive four votes, Bob and Carl would get three votes each, and Dick one vote. Alex would be declared winner. But seven out of eleven electors prefer Bob to Alex. Furthermore, six electors prefer Carl to Bob, six prefer Dick to Carl, and six prefer Alex to Dick. The complete ranking is Alex > Dick > Carl > Bob > Alex. We have a cycle, and nobody should be declared winner.

But if Elector 11 would change his preferences slightly (by interchanging Carl and Bob) the majority ranking would become Bob > Alex > Dick > Carl. The cycle would be resolved and Bob would be the undisputed winner. Or if Elector 5 interchanged Bob and Carl, Carl would win. Yet to make Alex or Dick win would require four interchanges. Hence Bob and Carl have more claim to the crown than do Alex or Dick.

Dodgson’s proposal is tantamount to finding the candidate who is closest to being a Condorcet winner. The cycle-breaking rule therefore goes as follows: count the number of swaps that each candidate in a cycle would need in order to come out on top, and declare the candidate who requires the fewest swaps the winner. (A swap is defined as an interchange of adjacent candidates in the voters’ preference.) The lowest number of swaps that are required to make a candidate a Condorcet winner is called the Dodgson score. If a true Condorcet winner exists, he has a Dodgson score of zero. (He needs no swaps.) Of course, there could be more than one candidate in a cycle with the same, low, Dodgson score. In the above example, both Bob and Carl have a Dodgson score of one. But since this is less than Alex’s and Dick’s Dodgson-scores the number of potential winners has at least been whittled down from four to two.

But there remains a problem. Determining whether a candidate is a Dodgson winner is no easy task. One needs to find which preferences, of which voters, need to be swapped. Of course, if sufficiently many swaps are allowed, any candidate can be made into a Condorcet winner. But the point is to find the lowest number of swaps that is needed to make a candidate come out on top. This problem is hard; in fact, it is very hard as computer scientists found out 113 years after the publication of Dodgson’s third pamphlet.

It was in 1989 that three professors of Operations Research—John Bartholdi, Craig Tovey, and Michael Trick—decided to take a close look at Dodgson’s suggestion as to how to break voting cycles.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.