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]

Hardness of manipulation

By the Gibbard-Satterthwaite theorem, all non-trivial voting rules can be manipulated in the sense that voters can sometimes achieve a better outcome by misrepresenting their preferences, that is, they submit a non-truthful ballot to the voting system. Social choice theorists have long considered ways to circumvent this issue, such as the proposition by Bartholdi, Tovey, and Trick in 1989 based on computational complexity theory. [11] They considered the second-order Copeland rule (which can be evaluated in polynomial time), and proved that it is NP-complete for a voter to decide, given knowledge of how everyone else has voted, whether it is possible to manipulate in such a way as to make some favored candidate the winner. The same property holds for single transferable vote. [12]

Hence, assuming the widely believed hypothesis that P ≠ NP, there are instances where polynomial time is not enough to establish whether a beneficial manipulation is possible. Because of this, the voting rules that come with an NP-hard manipulation problem are "resistant" to manipulation. One should note that these results only concern the worst-case: it might well be possible that a manipulation problem is usually easy to solve, and only requires superpolynomial time on very unusual inputs. [13]

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. [14] Many tournament solutions have been proposed, [15] and computational social choice theorists have studied the complexity of the associated winner determination problems. [16] [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. [17] [18] [19] [20] 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. [21] [22] [23] [24] On the other hand, manipulation problem also tend to be easy on these domains, so complexity shields against manipulation are less effective. [22] [25] 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. [26] [27] [28]

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

The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved.

<span class="mw-page-title-main">Quantum computing</span> Technology that uses quantum mechanics

A quantum computer is a computer that exploits quantum mechanical phenomena.

<span class="mw-page-title-main">Time complexity</span> Estimate of time taken for running an algorithm

In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor.

In computer science, 2-satisfiability, 2-SAT or just 2SAT is a computational problem of assigning values to variables, each of which has two possible values, in order to satisfy a system of constraints on pairs of variables. It is a special case of the general Boolean satisfiability problem, which can involve constraints on more than two variables, and of constraint satisfaction problems, which can allow more than two choices for the value of each variable. But in contrast to those more general problems, which are NP-complete, 2-satisfiability can be solved in polynomial time.

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.

The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.

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.

The Kemeny–Young method is an electoral system that uses preferential 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.

Dodgson's method is an electoral system proposed by the author, mathematician and logician Charles Dodgson, better known as Lewis Carroll. The method is to extend the Condorcet method by swapping candidates until a Condorcet winner is found. The winner is the candidate which requires the minimum number of swaps. Dodgson proposed this voting scheme in his 1876 work "A method of taking votes on more than two issues". Given an integer k and an election, it is NP-complete to determine whether a candidate can become a Condorcet winner with fewer than k swaps.

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:

Proportional approval voting (PAV) is a proportional electoral system for selecting committees. It is an extension of the D'Hondt method of apportionment that additionally allows for personal votes (voters vote for candidates, not for a party list). The voters vote via approval ballots where each voter marks those candidates that the voter finds acceptable.

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.

<span class="mw-page-title-main">Polygonalization</span> Polygon through a set of points

In computational geometry, a polygonalization of a finite set of points in the Euclidean plane is a simple polygon with the given points as its vertices. A polygonalization may also be called a polygonization, simple polygonalization, Hamiltonian polygon, non-crossing Hamiltonian cycle, or crossing-free straight-edge spanning cycle.

In computer science, the Robertson–Webb (RW) query model is a model of computation used by algorithms for the problem of fair cake-cutting. In this problem, there is a resource called a "cake", and several agents with different value measures on the cake. The goal is to divide the cake among the agents such that each agent will consider his/her piece as "fair" by his/her personal value measure. Since the agents' valuations can be very complex, they cannot - in general - be given as inputs to a fair division algorithm. The RW model specifies two kinds of queries that a fair division algorithm may ask the agents: Eval and Cut. Informally, an Eval query asks an agent to specify his/her value to a given piece of the cake, and a Cut query asks an agent to specify a piece of cake with a given value.

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

Multiwinner voting, also called multiple-winner elections or committee voting or committee elections, is an electoral system in which multiple candidates are elected. The number of elected candidates is usually fixed in advance. For example, it can be the number of seats in a country's parliament, or the required number of members in a committee.

In economics and computer science, the house allocation problem is the problem of assigning objects to people with different preferences, such that each person receives exactly one object. The name "house allocation" comes from the main motivating application, which is assigning dormitory houses to students. Other commonly used terms are assignment problem and one-sided matching. When agents already own houses, the problem is often called a housing market. In house allocation problems, it is assumed that monetary transfers are not allowed; the variant in which monetary transfers are allowed is known as rental harmony.

Edith Hemaspaandra is a Dutch-American theoretical computer scientist whose research concerns computational social choice, the computational complexity theory of problems in social choice theory, and particularly on computational problems involving election manipulation. She is a professor of computer science at the Rochester Institute of Technology.

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.

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. ↑ Bartholdi, J. J.; Tovey, C. A.; Trick, M. A. (1989). "The computational difficulty of manipulating an election". Social Choice and Welfare. 6 (3): 227–241. doi:10.1007/BF00295861. S2CID   16158098.
  12. ↑ Bartholdi, John J.; Orlin, James B. (1991). "Single transferable vote resists strategic voting". Social Choice and Welfare. 8 (4): 341–354. CiteSeerX   10.1.1.127.97 . doi:10.1007/BF00183045. S2CID   17749613.
  13. ↑ Faliszewski, Piotr; Procaccia, Ariel D. (2010-09-23). "AI's War on Manipulation: Are We Winning?". AI Magazine. 31 (4): 53–64. CiteSeerX   10.1.1.205.2873 . doi:10.1609/aimag.v31i4.2314.
  14. ↑ Fishburn, P. (1977-11-01). "Condorcet Social Choice Functions". SIAM Journal on Applied Mathematics. 33 (3): 469–489. doi:10.1137/0133030.
  15. ↑ Laslier, Jean-François (1997). Tournament Solutions and Majority Voting. Springer Verlag.
  16. ↑ Moon, John W. (1968-01-01). Topics on tournaments. Holt, Rinehart and Winston.
  17. ↑ 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.
  18. ↑ 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.
  19. ↑ Arrow, Kenneth J. (2012-06-26). Social Choice and Individual Values. Yale University Press. ISBN   978-0300186987.
  20. ↑ 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.
  21. ↑ 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.
  22. 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 .
  23. ↑ 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.
  24. ↑ 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.
  25. ↑ 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.
  26. ↑ Peters, Dominik (2016-02-25). "Recognising Multidimensional Euclidean Preferences". arXiv: 1602.08109 [cs.GT].
  27. ↑ 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.
  28. ↑ 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.