Computational social choice

Last updated

Computational social choice is a field at the intersection of social choice theory, theoretical computer science, and the analysis of multi-agent systems. [1] It consists of the analysis of problems arising from the aggregation of preferences of a group of agents from a computational perspective. In particular, computational social choice is concerned with the efficient computation of outcomes of voting rules, with the computational complexity of various forms of manipulation, and issues arising from the problem of representing and eliciting preferences in combinatorial settings.

Contents

Winner determination

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. [2] [3] Certain voting systems, however, are computationally difficult to evaluate. [4] In particular, winner determination for the Kemeny-Young method, Dodgson's method, and Young's method are all NP-hard problems. [4] [5] [6] [7] This has led to the development of approximation algorithms and fixed-parameter tractable algorithms to improve the theoretical calculation of such problems. [8] [9] [10]

Preference Representation

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.

Other topics

Tournament solutions

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. [11] Many tournament solutions have been proposed, [12] and computational social choice theorists have studied the complexity of the associated winner determination problems. [13] [1]

Preference restrictions

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. [14] [15] [16] [17] 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. [18] [19] [20] [21] On the other hand, manipulation problem also tend to be easy on these domains, so complexity shields against manipulation are less effective. [19] [22] 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. [23] [24] [25]

Multiwinner elections

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.

See also

Related Research Articles

In complexity theory, UP is the complexity class of decision problems solvable in polynomial time on an unambiguous Turing machine with at most one accepting path for each input. UP contains P and is contained in NP.

<span class="mw-page-title-main">Random ballot</span> Electoral system with lottery among ballots

A random ballot or random dictatorship is a randomized electoral system where the election is decided on the basis of a single randomly-selected ballot. A closely-related variant is called random serialdictatorship, which repeats the procedure and draws another ballot if multiple candidates are tied on the first ballot.

Algorithmic topology, or computational topology, is a subfield of topology with an overlap with areas of computer science, in particular, computational geometry and computational complexity theory.

<span class="mw-page-title-main">Nanson's method</span> Single-winner electoral system

The Borda count electoral system can be combined with an instant-runoff procedure to create hybrid election methods that are called Nanson method and Baldwin method. Both methods are designed to satisfy the Condorcet criterion, and allow for incomplete ballots and equal rankings.

<span class="mw-page-title-main">Unknotting problem</span> Determining whether a knot is the unknot

In mathematics, the unknotting problem is the problem of algorithmically recognizing the unknot, given some representation of a knot, e.g., a knot diagram. There are several types of unknotting algorithms. A major unresolved challenge is to determine if the problem admits a polynomial time algorithm; that is, whether the problem lies in the complexity class P.

<span class="mw-page-title-main">Kemeny–Young method</span> Single-winner electoral system

The Kemeny–Young method is an electoral system that uses ranked ballots and pairwise comparison counts to identify the most popular choices in an election. It is a Condorcet method because if there is a Condorcet winner, it will always be ranked as the most popular choice.

<span class="mw-page-title-main">Dodgson's method</span> Single-winner ranked-choice voting system

Dodgson's method is an electoral system based on a proposal by mathematician Charles Dodgson, better known as Lewis Carroll. The method searches for a majority-preferred winner; if no such winner is found, the method proceeds by finding the candidate who could be transformed into a Condorcet winner with the smallest number of ballot edits possible, where a ballot edit switches two neighboring candidates on a voter's ballot.

There are a number of different criteria which can be used for voting systems in an election, including the following

Fair item allocation is a kind of the fair division problem in which the items to divide are discrete rather than continuous. The items have to be divided among several partners who potentially value them differently, and each item has to be given as a whole to a single person. This situation arises in various real-life scenarios:

<span class="mw-page-title-main">Proportional approval voting</span> Multiple-winner electoral system

Proportional approval voting (PAV) is a proportional electoral system for multiwinner elections. It is a multiwinner approval method that extends the highest averages method of apportionment commonly used to calculate apportionments for party-list proportional representation. However, PAV allows voters to support only the candidates they approve of, rather than being forced to approve or reject all candidates on a given party list.

Fisher market is an economic model attributed to Irving Fisher. It has the following ingredients:

Envy-free (EF) item allocation is a fair item allocation problem, in which the fairness criterion is envy-freeness - each agent should receive a bundle that they believe to be at least as good as the bundle of any other agent.

Combinatorial participatory budgeting, also called indivisible participatory budgeting or budgeted social choice, is a problem in social choice. There are several candidate projects, each of which has a fixed costs. There is a fixed budget, that cannot cover all these projects. Each voter has different preferences regarding these projects. The goal is to find a budget-allocation - a subset of the projects, with total cost at most the budget, that will be funded. Combinatorial participatory budgeting is the most common form of participatory budgeting.

An agreeable subset is a subset of items that is considered, by all people in a certain group, to be at least as good as its complement. Finding a small agreeable subset is a problem in computational social choice.

<span class="mw-page-title-main">Justified representation</span> Criterion for evaluating fairness of electoral systems

Justified representation (JR) is a criterion of fairness in multiwinner approval voting. It can be seen as an adaptation of the proportional representation criterion to approval voting.

<span class="mw-page-title-main">Multiwinner approval voting</span> Family of proportional election methods

Multiwinner approval voting, sometimes also called approval-based committee (ABC) voting, refers to a family of multi-winner electoral systems that use approval ballots. Each voter may select ("approve") any number of candidates, and multiple candidates are elected.

<span class="mw-page-title-main">Multiwinner voting</span> Process of electing more than one winner in the same election / district

Multiwinner, at-large, or committeevoting refers to electoral systems that elect several candidates at once. Such methods can be used to elect parliaments or committees.

Multi-issue voting is a setting in which several issues have to be decided by voting. Multi-issue voting raises several considerations, that are not relevant in single-issue voting.

Fully proportional representation(FPR) is a property of multiwinner voting systems. It extends the property of proportional representation (PR) by requiring that the representation be based on the entire preferences of the voters, rather than on their first choice. Moreover, the requirement combines PR with the requirement of accountability - each voter knows exactly which elected candidate represents him, and each candidate knows exactly which voters he represents.

Thiele's voting rules are rules for multiwinner voting. They allow voters to vote for individual candidates rather than parties, but still guarantee proportional representation. They were published by Thorvald Thiele in Danish in 1895, and translated to English by Svante Janson in 2016. They were used in Swedish parliamentary elections to distribute seats within parties, and are still used in city council elections.

References

  1. 1 2 Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016-04-25). Handbook of Computational Social Choice. Cambridge University Press. ISBN   9781107060432.
  2. ↑ Schulze, Markus (2010-07-11). "A new monotonic, clone-independent, reversal symmetric, and condorcet-consistent single-winner election method". Social Choice and Welfare. 36 (2): 267–303. doi:10.1007/s00355-010-0475-4. S2CID   1927244.
  3. ↑ Brill, Markus; Fischer, Felix (2012-01-01). "The Price of Neutrality for the Ranked Pairs Method". Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence. AAAI'12: 1299–1305.
  4. 1 2 Bartholdi III, J.; Tovey, C. A.; Trick, M. A. (1989-04-01). "Voting schemes for which it can be difficult to tell who won the election". Social Choice and Welfare. 6 (2): 157–165. doi:10.1007/BF00303169. S2CID   154114517.
  5. ↑ Hemaspaandra, Edith; Spakowski, Holger; Vogel, Jörg (2005-12-16). "The complexity of Kemeny elections". Theoretical Computer Science. 349 (3): 382–391. doi: 10.1016/j.tcs.2005.08.031 .
  6. ↑ Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg (1997). "Exact Analysis of Dodgson Elections: Lewis Carroll's 1876 Voting System is Complete for Parallel Access to NP". J. ACM. 44 (6): 806–825. arXiv: cs/9907036 . doi:10.1145/268999.269002. S2CID   367623.
  7. ↑ Rothe, Jörg; Spakowski, Holger; Vogel, Jörg (2003-06-06). "Exact Complexity of the Winner Problem for Young Elections". Theory of Computing Systems. 36 (4): 375–386. arXiv: cs/0112021 . doi:10.1007/s00224-002-1093-z. S2CID   3205730.
  8. ↑ Caragiannis, Ioannis; Covey, Jason A.; Feldman, Michal; Homan, Christopher M.; Kaklamanis, Christos; Karanikolas, Nikos; Procaccia, Ariel D.; Rosenschein, Jeffrey S. (2012-08-01). "On the approximability of Dodgson and Young elections". Artificial Intelligence. 187: 31–51. doi: 10.1016/j.artint.2012.04.004 .
  9. ↑ Ailon, Nir; Charikar, Moses; Newman, Alantha (2008-11-01). "Aggregating Inconsistent Information: Ranking and Clustering". J. ACM. 55 (5): 23:1–23:27. doi:10.1145/1411509.1411513. S2CID   5674305.
  10. ↑ Betzler, Nadja; Fellows, Michael R.; Guo, Jiong; Niedermeier, Rolf; Rosamond, Frances A. (2008-06-23). "Fixed-Parameter Algorithms for Kemeny Scores". In Fleischer, Rudolf; Xu, Jinhui (eds.). Algorithmic Aspects in Information and Management. Lecture Notes in Computer Science. Vol. 5034. Springer Berlin Heidelberg. pp. 60–71. CiteSeerX   10.1.1.145.9310 . doi:10.1007/978-3-540-68880-8_8. ISBN   9783540688655.
  11. ↑ Fishburn, P. (1977-11-01). "Condorcet Social Choice Functions". SIAM Journal on Applied Mathematics. 33 (3): 469–489. doi:10.1137/0133030.
  12. ↑ Laslier, Jean-François (1997). Tournament Solutions and Majority Voting. Springer Verlag.
  13. ↑ Moon, John W. (1968-01-01). Topics on tournaments. Holt, Rinehart and Winston.
  14. ↑ Black, Duncan (1948-01-01). "On the Rationale of Group Decision-making". Journal of Political Economy. 56 (1): 23–34. doi:10.1086/256633. JSTOR   1825026. S2CID   153953456.
  15. ↑ Rothstein, P. (1990-12-01). "Order restricted preferences and majority rule". Social Choice and Welfare. 7 (4): 331–342. doi:10.1007/BF01376281. S2CID   153683957.
  16. ↑ Arrow, Kenneth J. (2012-06-26). Social Choice and Individual Values. Yale University Press. ISBN   978-0300186987.
  17. ↑ Sen, Amartya; Pattanaik, Prasanta K (1969-08-01). "Necessary and sufficient conditions for rational choice under majority decision". Journal of Economic Theory. 1 (2): 178–202. doi:10.1016/0022-0531(69)90020-9.
  18. ↑ Elkind, Edith; Lackner, Martin; Peters, Dominik (2016-07-01). "Preference Restrictions in Computational Social Choice: Recent Progress" (PDF). Proceedings of the 25th International Conference on Artificial Intelligence. IJCAI'16: 4062–4065.
  19. 1 2 Brandt, Felix; Brill, Markus; Hemaspaandra, Edith; Hemaspaandra, Lane (2015-01-01). "Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates". Journal of Artificial Intelligence Research. 53: 439–496. doi: 10.1613/jair.4647 . hdl: 1802/10425 .
  20. ↑ N., Betzler; A., Slinko; J., Uhlmann (2013). "On the Computation of Fully Proportional Representation". Journal of Artificial Intelligence Research. 47 (2013): 475–519. arXiv: 1402.0580 . Bibcode:2014arXiv1402.0580B. doi:10.1613/jair.3896. S2CID   2839179.
  21. ↑ Skowron, Piotr; Yu, Lan; Faliszewski, Piotr; Elkind, Edith (2015-03-02). "The complexity of fully proportional representation for single-crossing electorates". Theoretical Computer Science. 569: 43–57. arXiv: 1307.1252 . doi:10.1016/j.tcs.2014.12.012. S2CID   5348844.
  22. ↑ Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg (2011-02-01). "The shield that never was: Societies with single-peaked preferences are more open to manipulation and control". Information and Computation. 209 (2): 89–107. arXiv: 0909.3257 . doi:10.1016/j.ic.2010.09.001.
  23. ↑ Peters, Dominik (2016-02-25). "Recognising Multidimensional Euclidean Preferences". arXiv: 1602.08109 [cs.GT].
  24. ↑ Doignon, J. P.; Falmagne, J. C. (1994-03-01). "A Polynomial Time Algorithm for Unidimensional Unfolding Representations" (PDF). Journal of Algorithms. 16 (2): 218–233. doi:10.1006/jagm.1994.1010.
  25. ↑ Escoffier, Bruno; Lang, Jérôme; Öztürk, Meltem (2008-01-01). "Single-peaked Consistency and Its Complexity". Proceedings of the 2008 Conference on ECAI 2008: 18th European Conference on Artificial Intelligence: 366–370. ISBN   9781586038915.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.