Computational Politics
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
,
, and
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
trounces
,
trounces
, and
trounces
. 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.
- 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. Essentially all the papers listed below can
be found, in their full technical report versions, in the
UR-CS Technical Report Archive's theory
section. Here is
Lane's complete publication
list
and links to
essentially all his conference and journal papers (and also his arxiv.org
technical reports) can be found via the ``EE'' (electronic edition) links at
Lane's entry at the DBLP
project.
- 2
-
E. Brelsford, P. Faliszewski, E. Hemaspaandra, H. Schnoor, and I. Schnoor.
Approximability of manipulating elections.
In Proceedings of the 23rd AAAI Conference on Artificial
Intelligence. AAAI Press, July 2008.
To appear.
- 3
-
G. Erdélyi, L. Hemaspaandra, J. Rothe, and H. Spakowski.
On approximating optimal weighted lobbying, and frequency of
correctness versus average-case polynomial time.
In Proceedings of the 16th International Symposium on
Fundamentals of Computation Theory, pages 300-311. Springer-Verlag Lecture Notes in Computer Science #4639, August 2007.
- 4
-
P. Faliszewski.
Nonuniform bribery.
In Proceedings of the 7th International Conference on Autonomous
Agents and Multiagent Systems, pages 1569-1572, May 2008.
- 5
-
P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra.
The complexity of bribery in elections.
In Proceedings of the 21st National Conference on Artificial
Intelligence, pages 641-646. AAAI Press, July 2006.
- 6
-
P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
A richer understanding of the complexity of election
systems.
In S. Ravi and S. Shukla, editors, Fundamental Problems in
Computing: Essays in Honor of Professor Daniel J. Rosenkrantz.
Springer.
To appear.
- 7
-
P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Llull and Copeland voting broadly resist bribery and
control.
In Proceedings of the 22nd AAAI Conference on Artificial
Intelligence, pages 724-730. AAAI Press, July 2007.
- 8
-
P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Copeland voting fully resists constructive control.
In Proceedings of the 4th International Conference on
Algorithmic Aspects in Information and Management, pages 165-176.
Springer-Verlag Lecture Notes in Computer Science, June 2008.
To appear.
- 9
-
P. Faliszewski, E. Hemaspaandra, and H. Schnoor.
Copeland voting: Ties matter.
In Proceedings of the 7th International Conference on Autonomous
Agents and Multiagent Systems, pages 983-990, May 2008.
- 10
-
P. Faliszewski and L. Hemaspaandra.
The complexity of power-index comparison
In Proceedings of the 4th International Conference on
Algorithmic Aspects in Information and Management, pages 177-187.
Springer-Verlag Lecture Notes in Computer Science, June 2008.
To appear.
- 11
-
P. Faliszewski and M. Ogihara.
Separating the notions of self- and autoreducibility.
In Proceedings of the 30th International Symposium on
Mathematical Foundations of Computer Science, pages 308-315.
Springer-Verlag Lecture Notes in Computer Science #3618,
August/September 2005.
- 12
-
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.
- 13
-
E. Hemaspaandra and L. Hemaspaandra.
Dichotomy for voting systems.
Journal of Computer and System Sciences, 73(1):73-83, 2007.
- 14
-
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.
- 15
-
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.
In Proceedings of the 24th International Colloquium on Automata,
Languages, and Programming, pages 214-224. Springer-Verlag Lecture
Notes in Computer Science #1256, July 1997.
- 16
-
E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Raising NP lower bounds to parallel NP lower bounds.
SIGACT News, 28(2):2-13, 1997.
- 17
-
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.
- 18
-
E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Anyone but him: The complexity of precluding an alternative.
Artificial Intelligence, 171(5-6):255-285, 2007.
- 19
-
E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Hybrid elections broaden complexity-theoretic resistance to control.
In Proceedings of the 20th International Joint Conference on
Artificial Intelligence, pages 1308-1314. IJCAI, January 2007.
- 20
-
E. Hemaspaandra, H. Spakowski, and J. Vogel.
The complexity of Kemeny elections.
Theoretical Computer Science, 349(3):382-391, 2005.
- 21
-
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.
- 22
-
C. Homan and L. Hemaspaandra.
Guarantees for the success frequency of an algorithm for finding
Dodgson-election winners.
Journal of Heuristics.
To appear.
- 23
-
C. Homan and L. Hemaspaandra.
Guarantees for the success frequency of an algorithm for finding
Dodgson-election winners.
In Proceedings of the 31st International Symposium on
Mathematical Foundations of Computer Science, pages 528-539.
Springer-Verlag Lecture Notes in Computer Science #4162,
August/September 2006.
- 24
-
M. Zuckerman, P. Faliszewski, Y. Bachrach, and E. Elkind.
Manipulating quota value in weighted voting games.
In Proceedings of the 23rd AAAI Conference on Artificial
Intelligence. AAAI Press, July 2008.
To appear.
(Last modified: June 5, 2008.)
Lane A. Hemaspaandra