UR-CS Participating Faculty: Lane Hemaspaandra.
This project studies complexity-theoretic aspects of political science--in particular, of voting theory. One focus is an experimental study of Congressional apportionment, and the other is a theoretical study of voting systems.
Regarding the latter,
the Condorcet criterion is that an election is won by any
candidate who defeats all others in pairwise majority-rule elections.
The Condorcet Paradox,
dating from 1785,
notes that not only is it not always the case
that Condorcet winners exist but, far worse,
when there are more than two candidates, pairwise majority-rule
elections may yield strict cycles in the aggregate preference
even if each voter has non-cyclic
preferences.
(The standard
example is an election over candidates a, b, and c in which
one third of the voters have preference 
,
one third of the voters have preference 
, and
one third of the voters have preference 
.
In this case, though each voter individually has
well-ordered preferences, the
aggregate preference of the electorate is that b trounces
a, c trounces b, and a trounces c. In short, individually
well-ordered preferences do not
necessarily aggregate to a well-ordered societal preference.)
This
is a widely discussed and troubling feature of majority
rule.
In 1876, Charles Lutwidge Dodgson--more commonly referred to today by his pen name, Lewis Carroll--proposed an election system that is inspired by the Condorcet criterion (Carroll did not use this term--indeed, Black has shown that Carroll ``almost beyond a doubt'' was unfamiliar with Condorcet's work), yet that sidesteps the abovementioned problem. In particular, a Condorcet winner is a candidate who defeats each other candidate in pairwise majority-rule elections. In Carroll's system, an election is won by the candidate who is ``closest'' to being a Condorcet winner. In particular, each candidate is given a score that is the smallest number of exchanges of adjacent preferences in the voters' preference orders needed to make the candidate a Condorcet winner with respect to the resulting preference orders. Whatever candidate (or candidates, in the case of a tie) has the lowest score is the winner. This system admits ties but, as each candidate is assigned an integer score, no strict-preference cycles are possible.
Bartholdi, Tovey, and Trick, in their paper ``Voting Schemes for which It Can Be Difficult to Tell Who Won the Election,'' raise a difficulty regarding Carroll's election system. Though the notion of winner(s) in Carroll's election system is mathematically well-defined, Bartholdi et al. raise the issue of what the computational complexity is of determining who is the winner. Though most natural election schemes admit obvious polynomial-time algorithms for determining who won, in sharp contrast Bartholdi et al. prove that Carroll's election scheme has the disturbing property that it is NP-hard to determine whether a given candidate has won a given election (a problem they dub DodgsonWinner), and that it is NP-hard even to determine whether a given candidate has tied-or-defeated another given candidate (a problem they dub DodgsonRanking).
Bartholdi, Tovey, and Trick's NP-hardness results establish lower bounds for the complexity of DodgsonRanking and DodgsonWinner. A central focus of this project has been the exact analysis of the complexity, and we have recently achieved this. Ongoing research in this project studies the complexity of other voting systems for which the complexity of determining the winner remains an open issue.
Go back to URCS Research Projects Page