Overview

Dodgson's and Young's election systems, dating from 1876 and 1977, are beautiful, historically resonant election systems. Surprisingly, both of these systems turn out to have highly intractable winner-determination problems: The winner problems of these systems are complete for parallel access to NP. This chapter discusses both the complexity of these winner-determination problems and approaches—through heuristic algorithms, fixed-parameter algorithms, and approximation algorithms—to circumventing that complexity.

Introduction, Election-System Definitions, and Results Overview

Charles Lutwidge Dodgson, better known under his pen name of Lewis Carroll, was a mathematics tutor at Oxford. In his 1876 pamphlet, “A Method of Taking Votes on More than Two Issues” (Dodgson, 1876), printed by the Clarendon Press, Oxford and headed “not yet published,” he defined an election system that is compellingly beautiful in many ways, and yet that also turned out to be so subtle and complex, also in many ways, that it has in recent decades been much studied by computational social choice researchers.

Dodgson's election system is very simply defined. An election will consist of a finite number of voters, each voting by casting a linear order over (the same) finite set of candidates. (Recall that linear orders are inherently antisymmetric, i.e., are “tie-free.”) A Condorcet winner (respectively, weak Condorcet winner) is a candidate a who, for each other candidate b, is preferred to b by strictly more than half (respectively, by at least half) of the voters. It is natural to want election systems to be Condorcet-consistent, that is, to have the property that if there is a Condorcet winner, he or she is the one and only winner under the election system. Dodgson's system is Condorcet-consistent. In fact, the system is defined based on each candidate's closeness to being a Condorcet winner. Dodgson's view was that whichever candidate (or candidates if there is a tie for closest) was “closest” to being Condorcet winners should be the winner(s), and his system is a realization of that view.

In particular, the Dodgson score of a candidate, a, is the smallest number of sequential exchanges of adjacent candidates in preference orders such that after those exchanges a is a Condorcet winner. All candidates having the smallest Dodgson score among the candidates are the winner(s) in Dodgson's system.