fbpx
Wikipedia

Computational social choice

November 12, 2023

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.

Winner determination edit

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 edit

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 edit

Tournament solutions edit

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 edit

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 edit

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 edit

References edit

  1. ^ a b 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. ^ a b 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. ^ a b 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.

External links edit

  • The COMSOC website, offering a collection of materials related to computational social choice, such as academic workshops, PhD theses, and a mailing list.

November 12, 2023
computational, social, choice, this, article, relies, excessively, references, primary, sources, please, improve, this, article, adding, secondary, tertiary, sources, find, sources, news, newspapers, books, scholar, jstor, july, 2017, learn, when, remove, this. This article relies excessively on references to primary sources Please improve this article by adding secondary or tertiary sources Find sources Computational social choice news newspapers books scholar JSTOR July 2017 Learn how and when to remove this template message 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 1 Winner determination 2 Hardness of manipulation 3 Other topics 3 1 Tournament solutions 3 2 Preference restrictions 3 3 Multiwinner elections 4 See also 5 References 6 External linksWinner determination editThe 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 editBy 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 editThis section may be too technical for most readers to understand Please help improve it to make it understandable to non experts without removing the technical details July 2017 Learn how and when to remove this template message Tournament solutions edit 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 edit 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 edit 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 editAlgocracy Algorithmic game theory Algorithmic mechanism design Cake cutting Fair division Hedonic gamesReferences edit a b Brandt Felix Conitzer Vincent Endriss Ulle Lang Jerome Procaccia Ariel D 2016 04 25 Handbook of Computational Social Choice Cambridge University Press ISBN 9781107060432 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 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 a b 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 Hemaspaandra Edith Spakowski Holger Vogel Jorg 2005 12 16 The complexity of Kemeny elections Theoretical Computer Science 349 3 382 391 doi 10 1016 j tcs 2005 08 031 Hemaspaandra Edith Hemaspaandra Lane A Rothe Jorg 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 Rothe Jorg Spakowski Holger Vogel Jorg 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 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 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 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 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 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 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 Fishburn P 1977 11 01 Condorcet Social Choice Functions SIAM Journal on Applied Mathematics 33 3 469 489 doi 10 1137 0133030 Laslier Jean Francois 1997 Tournament Solutions and Majority Voting Springer Verlag Moon John W 1968 01 01 Topics on tournaments Holt Rinehart and Winston 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 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 Arrow Kenneth J 2012 06 26 Social Choice and Individual Values Yale University Press ISBN 978 0300186987 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 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 a b 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 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 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 Faliszewski Piotr Hemaspaandra Edith Hemaspaandra Lane A Rothe Jorg 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 Peters Dominik 2016 02 25 Recognising Multidimensional Euclidean Preferences arXiv 1602 08109 cs GT 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 Escoffier Bruno Lang Jerome Ozturk 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 External links editThe COMSOC website offering a collection of materials related to computational social choice such as academic workshops PhD theses and a mailing list Retrieved from https en wikipedia org w index php title Computational social choice amp oldid 1180378165, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.