Computational Social Choice Theory

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

Note: Please also see the web pages of my wonderful colleague, Prof. Anson Kahng.

Project Description

This project studies complexity-theoretic and algorithmic aspects of political science and economics—in 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 written (we hope accessible!) surveys in Communications of the ACM (“Using Complexity to Protect Elections” [18]) and in the book chapter “A Richer Understanding of the Complexity of Election Systems” [26] (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 majority-rule 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 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 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 success-frequency analysis of heuristic algorithms for Dodgson-election winner finding, the extent to which complexity-theoretic protections of elections persist or evaporate when the electorates are single-peaked, 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 has been a participant on complexity-of-election 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.

References

1

This is a list of selected papers, from or related to this project, by University of Rochester authors. Links to essentially all Lane's conference and journal papers (and also his arXiv.org technical reports) can be found via the pointers from the related entries within Lane's entry at the DBLP project. Additionally, here is a link to Lane's complete publication list (note: that list does not itself have links to papers).

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 199–251. Springer, 2010.

3

F. Brandt, M. Brill, E. Hemaspaandra, and L. Hemaspaandra.
Bypassing combinatorial protections: Polynomial-time algorithms for single-peaked electorates.
In Proceedings of the 24th AAAI Conference on Artificial Intelligence, pages 715–722. AAAI Press, July 2010.

4

F. Brandt, M. Brill, E. Hemaspaandra, and L. Hemaspaandra.
Bypassing combinatorial protections: Polynomial-time algorithms for single-peaked electorates.
Journal of Artificial Intelligence Research, 53:439–496, 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 44–49. 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, pages 103–126. Cambridge University Press, 2016.

7

B. Carleton, M. Chavrimootoo, L. Hemaspaandra, D. Narváez, C. Taliancich, and H. Welles.
Search versus search for collapsing electoral control types (extended abstract).
In Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems. International Foundation for Autonomous Agents and Multiagent Systems, May–June 2023.
to appear.

8

B. Carleton, M. Chavrimootoo, L. Hemaspaandra, D. Narváez, C. Taliancich, and H. Welles.
Separating and collapsing electoral control types.
In Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems. International Foundation for Autonomous Agents and Multiagent Systems, May–June 2023.
to appear.

9

G. Erdélyi, E. Hemaspaandra, and L. Hemaspaandra.
Bribery and voter control under voting-rule uncertainty.
In Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems, pages 61–68. International Foundation for Autonomous Agents and Multiagent Systems, May 2014.

10

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 396–413. Springer-Verlag Lecture Notes in Artificial Intelligence #9346, September 2015.

11

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

12

G. Erdélyi, L. Hemaspaandra, J. Rothe, and H. Spakowski.
Generalized juntas and NP-hard sets.
Theoretical Computer Science, 410(38–40):3995–4000, 2009.

13

P. Faliszewski.
Manipulations of elections: Algorithms and infeasibility results.
Technical Report TR-941, 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/theory-trs.html, of Piotr Faliszewski's Ph.D. dissertation.

14

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

15

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.

16

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

17

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

18

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

19

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

20

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

21

P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra.
The complexity of manipulative attacks in nearly single-peaked electorates.
Artificial Intelligence, 207:69–99, 2014.

22

P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra.
The complexity of manipulative attacks in nearly single-peaked electorates.
In Proceedings of the 24th International Joint Conference on Artificial Intelligence, pages 4178–4182. AAAI Press, July/August 2015.

23

P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra.
Weighted electoral control.
Journal of Artificial Intelligence Research, 52:507–542, 2015.

24

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.

25

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:275–341, 2009.

26

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 375–406. Springer, 2009.

27

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

28

P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
The shield that never was: Societies with single-peaked preferences are more open to manipulation and control.
Information and Computation, 209(2):89–107, 2011.

29

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

30

P. Faliszewski and L. Hemaspaandra.
The complexity of power-index comparison.
Theoretical Computer Science, 410(1):101–107, 2009.

31

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 113–119. AAAI Press, August 2013.

32

Z. Fitzsimmons, E. Hemaspaandra, and L. Hemaspaandra.
Manipulation complexity of same-system runoff elections.
Annals of Mathematics and Artificial Intelligence, 77(3–4):159–189, 2016.

33

Z. Fitzsimmons, E. Hemaspaandra, and L. Hemaspaandra.
Control in the presence of manipulators: Cooperative and competitive cases.
Autonomous Agents and Multi-Agent Systems, 34(2, Article 52):1–32, 2020.

34

T. Gvozdeva, L. Hemaspaandra, and A. Slinko.
Three hierarchies of simple games parameterized by “resource” parameters.
International Journal of Game Theory, 42(1):1–17, 2013.

35

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.

36

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

37

E. Hemaspaandra and L. Hemaspaandra.
Credimus.
In J.-F. Laslier, H. Moulin, M. Sanver, and W. Zwicker, editors, The Future of Economic Design: The Continuing Development of a Field as Envisioned by Its Researchers, pages 141–152. Springer, 2019.

38

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 377–388. Leibniz International Proceedings in Informatics (LIPIcs) #20, February/March 2013.

39

E. Hemaspaandra, L. Hemaspaandra, and C. Menton.
Search versus decision for election manipulation problems.
ACM Transactions on Computation Theory, 12(#1, Article 3):1–42, 2020.

40

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.

41

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.

42

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

43

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.

44

E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Anyone but him: The complexity of precluding an alternative.
Artificial Intelligence, 171(5–6):255–285, 2007.

45

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.

46

E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Hybrid elections broaden complexity-theoretic resistance to control.
Mathematical Logic Quarterly, 55(4):397–424, 2009.

47

E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Controlling candidate-sequential elections.
In Proceedings of the 20th European Conference on Artificial Intelligence, pages 905–906. IOS Press, August 2012.

48

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

49

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

50

E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
The complexity of manipulative actions in single-peaked societies.
In J. Rothe, editor, Economics and Computation: An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division, pages 327–360. Springer, 2016.

51

E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
The complexity of controlling candidate-sequential elections.
Theoretical Computer Science, 678:14–21, 2017.

52

E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
The complexity of online voter control in sequential elections.
Autonomous Agents and Multi-Agent Systems, 31(5):1055–1076, 2017.

53

E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
The complexity of online bribery in sequential elections.
In Proceedings of the 17th Conference on Theoretical Aspects of Rationality and Knowledge, pages 233–251. Electronic Proceedings in Theoretical Computer Science #297, July 2019.

54

E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
The complexity of online bribery in sequential elections.
Journal of Computer and System Sciences, 127:66–90, 2022.

55

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 712–720. AAAI Press, July 2014.

56

E. Hemaspaandra, L. Hemaspaandra, T. Tantau, and O. Watanabe.
On the complexity of kings.
Theoretical Computer Science, 411(4–5):783–798, 2010.

57

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

58

L. Hemaspaandra.
Computational social choice and computational complexity: BFFs?
In Proceedings of the 32nd AAAI Conference on Artificial Intelligence, pages 7971–7977. AAAI Press, February 2018.

59

L. Hemaspaandra.
That most important intersection.
In H.-J. Böckenhauer, D. Komm, and W. Unger, editors, Adventures Between Lower Bounds and Higher Altitudes: Essays Dedicated to Juraj Hromkovič on the Occasion of his 60th Birthday, pages 568–589. Springer, 2018.

60

L. Hemaspaandra, R. Lavaee, and C. Menton.
Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control.
In Proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems, pages 1345–1346. International Foundation for Autonomous Agents and Multiagent Systems, May 2013.

61

L. Hemaspaandra, R. Lavaee, and C. Menton.
Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control.
Annals of Mathematics and Artificial Intelligence, 77(3–4):191–223, 2016.

62

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.

63

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.

64

C. Homan and L. Hemaspaandra.
Guarantees for the success frequency of an algorithm for finding Dodgson-election winners.
Journal of Heuristics, 15(4):403–423, 2009.

65

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

66

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 215–220. AAAI Press, July 2008.

$\begin{tabular}{l} {}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\ \hline \end{tabular}$

(Last modified: February 16, 2023.)