computational social choice

The usefulness of a particular voting system can be severely limited if it takes a very long time to calculate the winner of an election. Therefore, it is important to design fast algorithms that can evaluate a voting rule when given ballots as input. As is common in computational complexity theory, an algorithm is thought to be efficient if it takes polynomial time. Many popular voting rules can be evaluated in polynomial time in a straightforward way (i.e., counting), such as the Borda count, approval voting, or the plurality rule. For rules such as the Schulze method or ranked pairs, more sophisticated algorithms can be used to show polynomial runtime.{{Cite journal|last=Schulze|first=Markus|date=2010-07-11|title=A new monotonic, clone-independent, reversal symmetric, and condorcet-consistent single-winner election method|journal=Social Choice and Welfare|volume=36|issue=2|pages=267–303|doi=10.1007/s00355-010-0475-4|s2cid=1927244}}{{Cite journal|last1=Brill|first1=Markus|last2=Fischer|first2=Felix|date=2012-01-01|title=The Price of Neutrality for the Ranked Pairs Method|url=http://dl.acm.org/citation.cfm?id=2900728.2900912|journal=Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence|series=AAAI'12|pages=1299–1305}} Certain voting systems, however, are computationally difficult to evaluate.{{Cite journal|last1=Bartholdi III|first1=J.|last2=Tovey|first2=C. A.|last3=Trick|first3=M. A.|author3-link= Michael Trick |date=1989-04-01|title=Voting schemes for which it can be difficult to tell who won the election|journal=Social Choice and Welfare|volume=6|issue=2|pages=157–165|doi=10.1007/BF00303169|s2cid=154114517}} In particular, winner determination for the Kemeny-Young method, Dodgson's method, and Young's method are all NP-hard problems.{{Cite journal|last1=Hemaspaandra|first1=Edith|author1-link=Edith Hemaspaandra|last2=Spakowski|first2=Holger|last3=Vogel|first3=Jörg|date=2005-12-16|title=The complexity of Kemeny elections|journal=Theoretical Computer Science|volume=349|issue=3|pages=382–391|doi=10.1016/j.tcs.2005.08.031|doi-access=free}}{{Cite journal|last1=Hemaspaandra|first1=Edith|author1-link=Edith Hemaspaandra|last2=Hemaspaandra|first2=Lane A.|last3=Rothe|first3=Jörg|year=1997|title=Exact Analysis of Dodgson Elections: Lewis Carroll's 1876 Voting System is Complete for Parallel Access to NP|journal=J. ACM|volume=44|issue=6|pages=806–825|doi=10.1145/268999.269002|arxiv=cs/9907036|s2cid=367623}}{{Cite journal|last1=Rothe|first1=Jörg|last2=Spakowski|first2=Holger|last3=Vogel|first3=Jörg|date=2003-06-06|title=Exact Complexity of the Winner Problem for Young Elections|journal=Theory of Computing Systems|volume=36|issue=4|pages=375–386|doi=10.1007/s00224-002-1093-z|arxiv=cs/0112021|s2cid=3205730}} This has led to the development of approximation algorithms and fixed-parameter tractable algorithms to improve the theoretical calculation of such problems.{{Cite journal|last1=Caragiannis|first1=Ioannis|last2=Covey|first2=Jason A.|last3=Feldman|first3=Michal|author3-link= Michal Feldman |last4=Homan|first4=Christopher M.|last5=Kaklamanis|first5=Christos|last6=Karanikolas|first6=Nikos|last7=Procaccia|first7=Ariel D.|last8=Rosenschein|first8=Jeffrey S.|date=2012-08-01|title=On the approximability of Dodgson and Young elections|journal=Artificial Intelligence|volume=187|pages=31–51|doi=10.1016/j.artint.2012.04.004|doi-access=free}}{{Cite journal|last1=Ailon|first1=Nir|last2=Charikar|first2=Moses|last3=Newman|first3=Alantha|date=2008-11-01|title=Aggregating Inconsistent Information: Ranking and Clustering|journal=J. ACM|volume=55|issue=5|pages=23:1–23:27|doi=10.1145/1411509.1411513|s2cid=5674305}}{{Cite book|last1=Betzler|first1=Nadja|last2=Fellows|first2=Michael R.|last3=Guo|first3=Jiong|last4=Niedermeier|first4=Rolf|last5=Rosamond|first5=Frances A.|title=Algorithmic Aspects in Information and Management |chapter=Fixed-Parameter Algorithms for Kemeny Scores |author4-link=Rolf Niedermeier|date=2008-06-23|publisher=Springer Berlin Heidelberg|isbn=9783540688655|editor-last=Fleischer|editor-first=Rudolf|series=Lecture Notes in Computer Science|volume=5034 |pages=60–71|doi=10.1007/978-3-540-68880-8_8|editor-last2=Xu|editor-first2=Jinhui|citeseerx = 10.1.1.145.9310}}

An important differentiation between voting rules is the format of ballots used by the voters to represent their preference. The two most common formats are approval ballots and ordinal ranks.

In approval ballots, each voter approves some candidates she likes. There is no further differentiation or hierarchy within the approved candidates. The same holds for the non-approved candidates. Thus, such ballots are also called dichotomous. Approval ballots are used for instance in satisfaction approval voting and proportional approval voting.

In contrast, ordinal ranks require the voter to rank all candidates from best to worst. This type of ballot is used for example in Borda's rule or in Bucklin voting.

There are many other types of ballot formats described in literature, such as truncated ranks, trichotomous ballots, or cardinal utility ballots.

Some research in computational social choice is focused on how representative ballot formats are, and on developing expressive, yet compact ballot formats. This is especially important in combinatorial settings, such as multiwinner voting.

{{Technical|section|date=July 2017}}

A tournament solution is a rule that assigns to every tournament a set of winners. Since a preference profile induces a tournament through its majority relation, every tournament solution can also be seen as a voting rule which only uses information about the outcomes of pairwise majority contests.{{Cite journal|last=Fishburn|first=P.|date=1977-11-01|title=Condorcet Social Choice Functions|journal=SIAM Journal on Applied Mathematics|volume=33|issue=3|pages=469–489|doi=10.1137/0133030}} Many tournament solutions have been proposed,{{Cite book|title=Tournament Solutions and Majority Voting|last=Laslier|first=Jean-François|date=1997|publisher=Springer Verlag}} and computational social choice theorists have studied the complexity of the associated winner determination problems.{{Cite book|url=https://books.google.com/books?id=P9Q-AAAAIAAJ|title=Topics on tournaments|last=Moon|first=John W.|date=1968-01-01|publisher=Holt, Rinehart and Winston}}

Restricted preference domains, such as single-peaked or single-crossing preferences, are an important area of study in social choice theory, since preferences from these domains avoid the Condorcet paradox and thus can circumvent impossibility results like Arrow's theorem and the Gibbard-Satterthwaite theorem.{{Cite journal|last=Black|first=Duncan|date=1948-01-01|title=On the Rationale of Group Decision-making|jstor=1825026|journal=Journal of Political Economy|volume=56|issue=1|pages=23–34|doi=10.1086/256633|s2cid=153953456}}{{Cite journal|last=Rothstein|first=P.|date=1990-12-01|title=Order restricted preferences and majority rule|journal=Social Choice and Welfare|volume=7|issue=4|pages=331–342|doi=10.1007/BF01376281|s2cid=153683957}}{{Cite book|url=https://books.google.com/books?id=y_rkX6QWOYMC|title=Social Choice and Individual Values|last=Arrow|first=Kenneth J.|date=2012-06-26|publisher=Yale University Press|isbn=978-0300186987}}{{Cite journal|last1=Sen|first1=Amartya|last2=Pattanaik|first2=Prasanta K|date=1969-08-01|title=Necessary and sufficient conditions for rational choice under majority decision|journal=Journal of Economic Theory|volume=1|issue=2|pages=178–202|doi=10.1016/0022-0531(69)90020-9}} From a computational perspective, such domain restrictions are useful to speed up winner determination problems, both computationally hard single-winner and multi-winner rules can be computed in polynomial time when preferences are structured appropriately.{{Cite journal|last1=Elkind|first1=Edith|author-link=Edith Elkind|last2=Lackner|first2=Martin|last3=Peters|first3=Dominik|date=2016-07-01|title=Preference Restrictions in Computational Social Choice: Recent Progress|url=http://www.ijcai.org/Proceedings/16/Papers/601.pdf|journal=Proceedings of the 25th International Conference on Artificial Intelligence|series=IJCAI'16|pages=4062–4065}}{{Cite journal|last1=Brandt|first1=Felix|last2=Brill|first2=Markus|last3=Hemaspaandra|first3=Edith|author3-link=Edith Hemaspaandra|last4=Hemaspaandra|first4=Lane|date=2015-01-01|title=Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates|journal=Journal of Artificial Intelligence Research|volume=53|pages=439–496|doi=10.1613/jair.4647|doi-access=free|hdl=1802/10425|hdl-access=free}}{{Cite journal|last1=N.|first1=Betzler|last2=A.|first2=Slinko|last3=J.|first3=Uhlmann|year=2013|title=On the Computation of Fully Proportional Representation|url=http://www.jair.org/papers/paper3896.html|journal=Journal of Artificial Intelligence Research|volume=47|issue=2013|pages=475–519|bibcode=2014arXiv1402.0580B|arxiv=1402.0580|doi=10.1613/jair.3896|s2cid=2839179}}{{Cite journal|last1=Skowron|first1=Piotr|last2=Yu|first2=Lan|last3=Faliszewski|first3=Piotr|last4=Elkind|first4=Edith|author4-link=Edith Elkind|date=2015-03-02|title=The complexity of fully proportional representation for single-crossing electorates|journal=Theoretical Computer Science|volume=569|pages=43–57|doi=10.1016/j.tcs.2014.12.012|arxiv=1307.1252|s2cid=5348844 }} On the other hand, manipulation problem also tend to be easy on these domains, so complexity shields against manipulation are less effective.{{Cite journal|last1=Faliszewski|first1=Piotr|last2=Hemaspaandra|first2=Edith|author2-link=Edith Hemaspaandra|last3=Hemaspaandra|first3=Lane A.|last4=Rothe|first4=Jörg|date=2011-02-01|title=The shield that never was: Societies with single-peaked preferences are more open to manipulation and control|journal=Information and Computation|volume=209|issue=2|pages=89–107|doi=10.1016/j.ic.2010.09.001|arxiv=0909.3257}} Another computational problem associated with preference restrictions is that of recognizing when a given preference profile belongs to some restricted domain. This task is polynomial time solvable in many cases, including for single-peaked and single-crossing preferences, but can be hard for more general classes.{{Cite arXiv|last=Peters|first=Dominik|date=2016-02-25|title=Recognising Multidimensional Euclidean Preferences|eprint=1602.08109|class=cs.GT}}{{Cite journal|last1=Doignon|first1=J. P.|last2=Falmagne|first2=J. C.|date=1994-03-01|title=A Polynomial Time Algorithm for Unidimensional Unfolding Representations|journal=Journal of Algorithms|volume=16|issue=2|pages=218–233|doi=10.1006/jagm.1994.1010|url=https://dipot.ulb.ac.be/dspace/bitstream/2013/310087/3/1994_Doignon_Falmagne.pdf }}{{Cite journal|last1=Escoffier|first1=Bruno|last2=Lang|first2=Jérôme|last3=Öztürk|first3=Meltem|date=2008-01-01|title=Single-peaked Consistency and Its Complexity|url=http://dl.acm.org/citation.cfm?id=1567281.1567363|journal=Proceedings of the 2008 Conference on ECAI 2008: 18th European Conference on Artificial Intelligence|pages=366–370|isbn=9781586038915}}

While most traditional voting rules focus on selecting a single winner, many situations require selecting multiple winners. This is the case when a fixed-size parliament or a committee is to be elected, though multiwinner voting rules can also be used to select a set of recommendations or facilities or a shared bundle of items. Work in computational social choice has focused on defining such voting rules, understanding their properties, and studying the complexity of the associated winner determination problems. See multiwinner voting.

• Algocracy
• Algorithmic game theory
• Algorithmic mechanism design
• Cake-cutting
• Fair division
• Hedonic games

{{Reflist|2}}

• [http://www.illc.uva.nl/COMSOC/ The COMSOC website], offering a collection of materials related to computational social choice, such as academic workshops, PhD theses, and a mailing list.

Category:Social choice theory

Category:Voting theory

Category:Subfields of computer science