Computational Social Choice Theory and Algorithmic Game Theory
NOTE: Click here
for our
Nov. 2010 CACM review article on using complexity to protect elections.
This project studies complexitytheoretic and algorithmic aspects of political
science and economicsin particular, of voting theory and game theory.
Our work ranges from
experimental study of Congressional apportionment to
theoretical studies of voting systems and
cooperative game theory. We are particularly interested in
the ways in which complexity can serve as a tool to protect elections from attacks.
Regarding our work on voting systems,
we have recently written (we hope accessible!) surveys
in Communications of the ACM (``Using Complexity to Protect Elections'' [16])
and in the book chapter ``A Richer Understanding of the Complexity of Election
Systems'' [24]
(and, more narrowly in scope, in the book chapter
[2]).
But let us here build to a particular example of our
work in this line.
The Condorcet criterion is that an election is won by any
candidate who defeats all others in pairwise majorityrule elections,
when such a candidate exists.
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 majorityrule
elections may yield strict cycles in the aggregate preference
even if each voter has noncyclic
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
wellordered preferences, the
aggregate preference of the electorate is that trounces
, trounces , and trounces . In short, individually
wellordered preferences do not
necessarily aggregate to a wellordered societal preference.)
This
is a widely discussed and troubling feature of majority
rule.
In 1876, Charles Lutwidge Dodgsonmore commonly referred to today by
his pen name, Lewis Carrollproposed an election system that is
inspired by the Condorcet
criterion (Carroll
did not use this termindeed, 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 majorityrule 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 strictpreference 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 welldefined, 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 polynomialtime algorithms for determining who
won, in sharp contrast Bartholdi et al. prove that Carroll's election
scheme has the disturbing property that it is NPhard to determine
whether a given candidate has won a given election (a problem they dub
DodgsonWinner), and that it is NPhard even to determine whether
a given candidate has tiedordefeated
another given candidate (a problem they
dub DodgsonRanking).
Bartholdi, Tovey, and Trick's NPhardness 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 complexity of control attacks that simultaneously
use many types of control (multiprong control attacks),
the issue of
how power indices interact with apportionment methods, the
successfrequency analysis of heuristic algorithms for
Dodgsonelection winner finding,
the extent to which complexitytheoretic protections of
elections persist or evaporate when the electorates
are singlepeaked,
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).
We also have, jointly with Arkadii Slinko's Auckland group,
computationally studied topics in cooperative game theory, such as
particularly the complexity of comparing power indices and building
hierarchies of simple games based on how wide and flexible the ``tie''
region is.
Lane works closely on this project with Professors Edith Hemaspaandra
and Christopher Homan
of RIT,
Professor Jörg Rothe of the University of Düsseldorf,
Professor Piotr Faliszewski of AGH University of Science and Technology, and many current and
former students and visitors and other researchers.
Lane is the PI on an NSF grant on this topic,
won the
Friedrich Wilhelm Bessel Research Award of the
Alexander von Humboldt Foundation,
and is a participant on complexityofelection grants from the European
Science Foundation (ESF) and the Australian Research Council (ARC). The list below contains some of this project's papers to date.
 1

This is a list of selected journal (except when the work has not yet
appeared in journal/book form, plus in some cases some conference articles)
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 URCS 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

D. Baumeister, G. Erdélyi, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Computational aspects of approval voting.
In J. Laslier and M. Sanver, editors, Handbook on Approval
Voting, pages 199251. Springer, 2010.
 3

F. Brandt, M. Brill, E. Hemaspaandra, and L. Hemaspaandra.
Bypassing combinatorial protections: Polynomialtime algorithms for
singlepeaked electorates.
In Proceedings of the 24th AAAI Conference on Artificial
Intelligence, pages 715722. AAAI Press, July 2010.
 4

F. Brandt, M. Brill, E. Hemaspaandra, and L. Hemaspaandra.
Bypassing combinatorial protections: Polynomialtime algorithms for
singlepeaked electorates.
Journal of Artificial Intelligence Research, 53:439496, July
2015.
 5

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, pages 4449. AAAI Press, July 2008.
 6

I. Caragiannis, E. Hemaspaandra, and L. Hemaspaandra.
Dodgson's Rule and Young's Rule.
In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. Procaccia,
editors, Handbook of Computational Social Choice. Cambridge University
Press.
To appear.
 7

G. Erdélyi, E. Hemaspaandra, and L. Hemaspaandra.
Bribery and voter control under votingrule uncertainty.
In Proceedings of the 13th International Conference on
Autonomous Agents and Multiagent Systems, pages 6168. International
Foundation for Autonomous Agents and Multiagent Systems, May 2014.
 8

G. Erdélyi, E. Hemaspaandra, and L. Hemaspaandra.
More natural models of electoral control by partition.
In Proceedings of the 4th International Conference on
Algorithmic Decision Theory, pages 396413. SpringerVerlag Lecture
Notes in Artificial Intelligence #9346, September 2015.
 9

G. Erdélyi, L. Hemaspaandra, J. Rothe, and H. Spakowski.
Frequency of correctness versus average polynomial time.
Information Processing Letters, 109(16):946949, 2009.
 10

G. Erdélyi, L. Hemaspaandra, J. Rothe, and H. Spakowski.
Generalized juntas and NPhard sets.
Theoretical Computer Science, 410(3840):39954000, 2009.
 11

P. Faliszewski.
Manipulations of elections: Algorithms and infeasibility results.
Technical Report TR941, Department of Computer Science, University
of Rochester, Rochester, NY, November 2008.
This is the technical report version, available on the web at
cs.rochester.edu/trs/theorytrs.html, of Piotr Faliszewski's Ph.D.
dissertation.
 12

P. Faliszewski.
Nonuniform bribery.
In Proceedings of the 7th International Conference on Autonomous
Agents and Multiagent Systems, pages 15691572. International Foundation
for Autonomous Agents and Multiagent Systems, May 2008.
 13

P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra.
The complexity of bribery in elections.
In Proceedings of the 21st National Conference on Artificial
Intelligence, pages 641646. AAAI Press, July 2006.
 14

P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra.
How hard is bribery in elections?
Journal of Artificial Intelligence Research, 35:485532, 2009.
 15

P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra.
Multimode control attacks on elections.
In Proceedings of the 21st International Joint Conference on
Artificial Intelligence, pages 128133. AAAI Press, July 2009.
 16

P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra.
Using complexity to protect elections.
Communications of the ACM, 53(11):7482, 2010.
 17

P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra.
Multimode control attacks on elections.
Journal of Artificial Intelligence Research, 40:305351, 2011.
 18

P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra.
Weighted electoral control.
In Proceedings of the 12th International Conference on
Autonomous Agents and Multiagent Systems, pages 367374. International
Foundation for Autonomous Agents and Multiagent Systems, May 2013.
 19

P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra.
The complexity of manipulative attacks in nearly singlepeaked
electorates.
Artificial Intelligence, 207:6999, 2014.
 20

P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra.
The complexity of manipulative attacks in nearly singlepeaked
electorates.
In Proceedings of the 24th International Joint Conference on
Artificial Intelligence, pages 41784182. AAAI Press, July/August 2015.
 21

P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra.
Weighted electoral control.
Journal of Artificial Intelligence Research, 52:507542, 2015.
 22

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 724730. AAAI Press, July 2007.
 23

P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Llull and Copeland voting computationally resist bribery and
constructive control.
Journal of Artificial Intelligence Research, 35:275341, 2009.
 24

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,
pages 375406. Springer, 2009.
 25

P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
The shield that never was: Societies with singlepeaked preferences
are more open to manipulation and control.
In Proceedings of the 12th Conference on Theoretical Aspects of
Rationality and Knowledge, pages 118127. ACM Digital Library, July 2009.
 26

P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
The shield that never was: Societies with singlepeaked preferences
are more open to manipulation and control.
Information and Computation, 209(2):89107, 2011.
 27

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 983990. International Foundation for
Autonomous Agents and Multiagent Systems, May 2008.
 28

P. Faliszewski and L. Hemaspaandra.
The complexity of powerindex comparison.
Theoretical Computer Science, 410(1):101107, 2009.
 29

Z. Fitzsimmons, E. Hemaspaandra, and L. Hemaspaandra.
Manipulation complexity of samesystem runoff elections.
Annals of Mathematics and Artificial Intelligence.
To appear.
 30

Z. Fitzsimmons, E. Hemaspaandra, and L. Hemaspaandra.
Control in the presence of manipulators: Cooperative and
competitive cases.
In Proceedings of the 23rd International Joint Conference on
Artificial Intelligence, pages 113119. AAAI Press, August 2013.
 31

T. Gvozdeva, L. Hemaspaandra, and A. Slinko.
Three hierarchies of simple games parameterized by ``resource''
parameters.
International Journal of Game Theory, 42(1):117, 2013.
 32

E. Hemaspaandra and L. Hemaspaandra.
Computational politics: Electoral systems.
In Proceedings of the 25th International Symposium on
Mathematical Foundations of Computer Science, pages 6483. SpringerVerlag
Lecture Notes in Computer Science #1893, August/September 2000.
 33

E. Hemaspaandra and L. Hemaspaandra.
Dichotomy for voting systems.
Journal of Computer and System Sciences, 73(1):7383, 2007.
 34

E. Hemaspaandra, L. Hemaspaandra, and C. Menton.
Search versus decision for election manipulation problems.
In Proceedings of the 30th Annual Symposium on Theoretical
Aspects of Computer Science, pages 377388. Leibniz International
Proceedings in Informatics (LIPIcs), February/March 2013.
 35

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):806825, 1997.
 36

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 214224. SpringerVerlag Lecture
Notes in Computer Science #1256, July 1997.
 37

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

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 95101. AAAI Press, July 2005.
 39

E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Anyone but him: The complexity of precluding an alternative.
Artificial Intelligence, 171(56):255285, 2007.
 40

E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Hybrid elections broaden complexitytheoretic resistance to control.
In Proceedings of the 20th International Joint Conference on
Artificial Intelligence, pages 13081314. IJCAI, January 2007.
 41

E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Hybrid elections broaden complexitytheoretic resistance to control.
Mathematical Logic Quarterly, 55(4):397424, 2009.
 42

E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Controlling candidatesequential elections.
In Proceedings of the 20th European Conference on Artificial
Intelligence, pages 905906. IOS Press, August 2012.
 43

E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Online voter control in sequential elections.
In Proceedings of the 20th European Conference on Artificial
Intelligence, pages 396401. IOS Press, August 2012.
 44

E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
The complexity of online manipulation of sequential elections.
Journal of Computer and System Sciences, 80(4):697710, 2014.
 45

E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
The complexity of manipulative actions in singlepeaked societies.
In J. Rothe, editor, Economics and Computation: An
Introduction to Algorithmic Game Theory, Computational Social Choice, and
Fair Division, pages 327360. Springer, 2016.
 46

E. Hemaspaandra, L. Hemaspaandra, and H. Schnoor.
A control dichotomy for pure scoring rules.
In Proceedings of the 28th AAAI Conference on Artificial
Intelligence, pages 712720. AAAI Press, July 2014.
 47

E. Hemaspaandra, L. Hemaspaandra, T. Tantau, and O. Watanabe.
On the complexity of kings.
Theoretical Computer Science, 411(45):783798, 2010.
 48

E. Hemaspaandra, H. Spakowski, and J. Vogel.
The complexity of Kemeny elections.
Theoretical Computer Science, 349(3):382391, 2005.
 49

L. Hemaspaandra, R. Lavaee, and C. Menton.
Schulze and rankedpairs voting are fixedparameter tractable to
bribe, manipulate, and control.
Annals of Mathematics and Artificial Intelligence.
To appear.
 50

L. Hemaspaandra, R. Lavaee, and C. Menton.
Schulze and rankedpairs voting are fixedparameter tractable to
bribe, manipulate, and control.
In Proceedings of the 12th International Conference on
Autonomous Agents and Multiagent Systems, pages 13451346. International
Foundation for Autonomous Agents and Multiagent Systems, May 2013.
 51

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 doi.acm.org/10.1145/297096.297106, 16pp.
 52

C. Homan and L. Hemaspaandra.
Guarantees for the success frequency of an algorithm for finding
Dodgsonelection winners.
In Proceedings of the 31st International Symposium on
Mathematical Foundations of Computer Science, pages 528539.
SpringerVerlag Lecture Notes in Computer Science #4162,
August/September 2006.
 53

C. Homan and L. Hemaspaandra.
Guarantees for the success frequency of an algorithm for finding
Dodgsonelection winners.
Journal of Heuristics, 15(4):403423, 2009.
 54

C. Menton.
Normalized range voting broadly resists control.
Theory of Computing Systems, 53(4):507531, 2013.
 55

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, pages 215220. AAAI Press, July 2008.
(Last modified: April 16, 2016.)
Lane A. Hemaspaandra
