Computational Politics

UR-CS Participating Faculty: Lane A. Hemaspaandra (= Lane A. Hemachandra).

Project Description

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 $\langle {a<b<c} \rangle $, one third of the voters have preference $\langle {b<c<a} \rangle$, and one third of the voters have preference $\langle {c<a<b} \rangle$. 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 initial focus of this project was the exact analysis of the complexity, and we achieved that in our 1997 JACM paper.

Other past and ongoing research on this project studies the complexity of other voting systems for which the complexity of determining the winner remains an open issue, the complexity of manipulating and controlling elections, the complexity of controlling an election to preclude a given candidate from winning, the issue of how power indices interact with apportionment methods, the success-frequency analysis of heuristic algorithms for Dodgson-election winner finding, and seeking to find outright dichotomy results that classify the complexity not of individual systems directly but that instead find exactly what properties are the ones that create or preclude complexity (what is the source of complexity in election winner/control/manipulation problems).

The project--largely joint with Professors Edith Hemaspaandra and Christopher Homan of RIT, Professor Jörg Rothe's group at the University of Düsseldorf, Professor Kulather Rajasethupathy of SUNY-Brockport, and many current and former students and visitors--is supported by a 5-year NSF ITR (Research for National Priorities Program) grant and a 3-year travel grant from the Humboldt Foundation. The list below contains some of our papers on this project to date.

Bibliography

1
This is a list of selected journal (except when the work has not yet appeared in journal/book form) papers, from or related to this project, by University of Rochester authors or close project collaborators. Most of the papers listed below can be found, in their full technical report versions, in the UR-CS Technical Report Archive's theory section. Lane Hemaspaandra's complete publication list can always be found at http://www.cs.rochester.edu/u/lane/publist.pdf.

2
E. Hemaspaandra and L. Hemaspaandra.
Computational politics: Electoral systems.
In Proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science, pages 64-83. Springer-Verlag Lecture Notes in Computer Science #1893, August/September 2000.

3
E. Hemaspaandra and L. Hemaspaandra.
Dichotomy for voting systems.
Technical Report TR-861, Department of Computer Science, University of Rochester, Rochester, NY, April 2005.

4
E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP.
Journal of the ACM, 44(6):806-825, 1997.

5
E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Raising NP lower bounds to parallel NP lower bounds.
SIGACT News, 28(2):2-13, 1997.

6
E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Anyone but him: The complexity of precluding an alternative.
In Proceedings of the 20th National Conference on Artificial Intelligence, pages 95-101. AAAI Press, July 2005.

7
E. Hemaspaandra, H. Spakowski, and J. Vogel.
The complexity of Kemeny elections.
Theoretical Computer Science, 349(3):382-391, 2005.

8
L. Hemaspaandra, K. Rajasethupathy, P. Sethupathy, and M. Zimand.
Power balance and apportionment algorithms for the United States Congress.
ACM Journal of Experimental Algorithmics, 3(1), 1998.
URL http://www.jea.acm.org/1998/HemaspaandraPower, 16pp.

9
C. Homan and L. Hemaspaandra.
Guarantees for the success frequency of an algorithm for finding Dodgson-election winners.
Technical Report TR-881, Department of Computer Science, University of Rochester, Rochester, NY, September 2005.

10
J. Rothe, H. Spakowski, and J. Vogel.
Exact complexity of the winner problem for Young elections.
Theory of Computing Systems, 36(4):375-386, 2003.

11
H. Spakowski and J. Vogel.
$ {\rm {\Theta}}_2^p$-completeness: A classical approach for new results.
In Proceedings of the 20th Conference on Foundations of Software Technology and Theoretical Computer Science, pages 348-360. Springer-Verlag Lecture Notes in Computer Science #1974, December 2000.



Lane A. Hemaspaandra