Jump to content

Computational social choice: Difference between revisions

Add links
From Wikipedia, the free encyclopedia
Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
Chstdu (talk | contribs)
258 edits
Review requested
Chstdu (talk | contribs)
258 edits
m →Other topics: Wikilink zu Tournament solution added
Line 10: Line 10:


== Other topics ==
== Other topics ==
* '''Tournament solutions.''' A tournament solution is a rule that assigns to every [[Tournament (graph theory)|tournament]] a set of winners. Since a preference profile induces a tournament through its [[Majority|majority relation]], every tournament solution can also be seen as a voting rule which only uses information about the outcomes of pairwise majority contests<ref>{{Cite journal|last=Fishburn|first=P.|date=1977-11-01|title=Condorcet Social Choice Functions|url=http://epubs.siam.org/doi/abs/10.1137/0133030|journal=SIAM Journal on Applied Mathematics|volume=33|issue=3|pages=469–489|doi=10.1137/0133030|issn=0036-1399}}</ref>. Many tournament solutions have been proposed<ref>{{Cite book|url=https://books.google.de/books/about/Topics_on_tournaments.html?id=P9Q-AAAAIAAJ&redir_esc=y7741,d.ZGg|title=Topics on tournaments|last=Moon|first=John W.|date=1968-01-01|publisher=Holt, Rinehart and Winston|language=en}}</ref>, and computational social choice has studied the complexity of the associated winner determination problems<ref name=":1" />.
* '''[[Draft:Tournament solution|Tournament solutions]].''' A tournament solution is a rule that assigns to every [[Tournament (graph theory)|tournament]] a set of winners. Since a preference profile induces a tournament through its [[Majority|majority relation]], every tournament solution can also be seen as a voting rule which only uses information about the outcomes of pairwise majority contests<ref>{{Cite journal|last=Fishburn|first=P.|date=1977-11-01|title=Condorcet Social Choice Functions|url=http://epubs.siam.org/doi/abs/10.1137/0133030|journal=SIAM Journal on Applied Mathematics|volume=33|issue=3|pages=469–489|doi=10.1137/0133030|issn=0036-1399}}</ref>. Many tournament solutions have been proposed<ref>{{Cite book|url=https://books.google.de/books/about/Topics_on_tournaments.html?id=P9Q-AAAAIAAJ&redir_esc=y7741,d.ZGg|title=Topics on tournaments|last=Moon|first=John W.|date=1968-01-01|publisher=Holt, Rinehart and Winston|language=en}}</ref>, and computational social choice has studied the complexity of the associated winner determination problems<ref name=":1" />.
* '''Preference restrictions.''' Restricted preference domains, such as [[Single peaked preferences|single-peaked]]<ref>{{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}}</ref> or [[Single crossing condition|single-crossing]]<ref>{{Cite journal|last=Rothstein|first=P.|date=1990-12-01|title=Order restricted preferences and majority rule|url=http://link.springer.com/article/10.1007/BF01376281|journal=Social Choice and Welfare|language=en|volume=7|issue=4|pages=331–342|doi=10.1007/BF01376281|issn=0176-1714}}</ref> preferences, are an important area of study in [[social choice theory]], since preferences from these domains avoid the [[Voting paradox|Condorcet paradox]]<ref>{{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=0300186983|language=en}}</ref><ref>{{Cite journal|last=Sen|first=Amartya|last2=Pattanaik|first2=Prasanta K|date=1969-08-01|title=Necessary and sufficient conditions for rational choice under majority decision|url=http://www.sciencedirect.com/science/article/pii/0022053169900209|journal=Journal of Economic Theory|volume=1|issue=2|pages=178–202|doi=10.1016/0022-0531(69)90020-9}}</ref> and thus can circumvent impossibility results like [[Arrow's impossibility theorem|Arrow's]] and the [[Gibbard–Satterthwaite theorem|Gibbard-Satterthwaite theorem]]. From a computational perspective, such domain restrictions are useful to speed up winner determination problems<ref>{{Cite journal|last=Elkind|first=Edith|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|location=New York|publisher=AAAI Press|volume=|issue=|pages=4062-4065|doi=|isbn=|pmid=|access-date=|via=}}</ref>, both computationally hard single-winner<ref name=":2">{{Cite journal|last=Brandt|first=Felix|last2=Brill|first2=Markus|last3=Hemaspaandra|first3=Edith|last4=Hemaspaandra|first4=Lane|date=2015-01-01|title=Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates|url=http://dx.doi.org/10.1613/jair.4647|journal=Journal of Artificial Intelligence Research|volume=53|issue=|doi=10.1613/jair.4647|pmid=|access-date=|via=}}</ref> and multi-winner rules<ref>{{Cite journal|last=N.|first=Betzler,|last2=A.|first2=Slinko,|last3=J.|first3=Uhlmann,|date=2013-01-01|title=On the Computation of Fully Proportional Representation|url=http://www.jair.org/papers/paper3896.html|journal=Journal of Artificial Intelligence Research|volume=47}}</ref><ref>{{Cite journal|last=Skowron|first=Piotr|last2=Yu|first2=Lan|last3=Faliszewski|first3=Piotr|last4=Elkind|first4=Edith|date=2015-03-02|title=The complexity of fully proportional representation for single-crossing electorates|url=http://www.sciencedirect.com/science/article/pii/S0304397514010111|journal=Theoretical Computer Science|volume=569|pages=43–57|doi=10.1016/j.tcs.2014.12.012}}</ref> can be computed in polynomial time when preferences are structured appropriately. On the other hand, manipulation problem also tend to be easy on these domains<ref name=":2" /><ref>{{Cite journal|last=Faliszewski|first=Piotr|last2=Hemaspaandra|first2=Edith|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|url=http://www.sciencedirect.com/science/article/pii/S0890540110001525|journal=Information and Computation|volume=209|issue=2|pages=89–107|doi=10.1016/j.ic.2010.09.001}}</ref>, so complexity shields against manipulation are less effective. 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<ref name=":3">{{Cite journal|last=Doignon|first=J. P.|last2=Falmagne|first2=J. C.|date=1994-03-01|title=A Polynomial Time Algorithm for Unidimensional Unfolding Representations|url=http://www.sciencedirect.com/science/article/pii/S0196677484710108|journal=Journal of Algorithms|volume=16|issue=2|pages=218–233|doi=10.1006/jagm.1994.1010}}</ref><ref>{{Cite journal|last=Escoffier|first=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|location=Amsterdam, The Netherlands, The Netherlands|publisher=IOS Press|pages=366–370|isbn=9781586038915}}</ref> and single-crossing<ref name=":3" /> preferences, but can be hard for more general classes<ref>{{Cite journal|last=Peters|first=Dominik|date=2016-02-25|title=Recognising Multidimensional Euclidean Preferences|url=http://arxiv.org/abs/1602.08109|journal=arXiv:1602.08109 [cs]}}</ref>.
* '''Preference restrictions.''' Restricted preference domains, such as [[Single peaked preferences|single-peaked]]<ref>{{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}}</ref> or [[Single crossing condition|single-crossing]]<ref>{{Cite journal|last=Rothstein|first=P.|date=1990-12-01|title=Order restricted preferences and majority rule|url=http://link.springer.com/article/10.1007/BF01376281|journal=Social Choice and Welfare|language=en|volume=7|issue=4|pages=331–342|doi=10.1007/BF01376281|issn=0176-1714}}</ref> preferences, are an important area of study in [[social choice theory]], since preferences from these domains avoid the [[Voting paradox|Condorcet paradox]]<ref>{{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=0300186983|language=en}}</ref><ref>{{Cite journal|last=Sen|first=Amartya|last2=Pattanaik|first2=Prasanta K|date=1969-08-01|title=Necessary and sufficient conditions for rational choice under majority decision|url=http://www.sciencedirect.com/science/article/pii/0022053169900209|journal=Journal of Economic Theory|volume=1|issue=2|pages=178–202|doi=10.1016/0022-0531(69)90020-9}}</ref> and thus can circumvent impossibility results like [[Arrow's impossibility theorem|Arrow's]] and the [[Gibbard–Satterthwaite theorem|Gibbard-Satterthwaite theorem]]. From a computational perspective, such domain restrictions are useful to speed up winner determination problems<ref>{{Cite journal|last=Elkind|first=Edith|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|location=New York|publisher=AAAI Press|volume=|issue=|pages=4062-4065|doi=|isbn=|pmid=|access-date=|via=}}</ref>, both computationally hard single-winner<ref name=":2">{{Cite journal|last=Brandt|first=Felix|last2=Brill|first2=Markus|last3=Hemaspaandra|first3=Edith|last4=Hemaspaandra|first4=Lane|date=2015-01-01|title=Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates|url=http://dx.doi.org/10.1613/jair.4647|journal=Journal of Artificial Intelligence Research|volume=53|issue=|doi=10.1613/jair.4647|pmid=|access-date=|via=}}</ref> and multi-winner rules<ref>{{Cite journal|last=N.|first=Betzler,|last2=A.|first2=Slinko,|last3=J.|first3=Uhlmann,|date=2013-01-01|title=On the Computation of Fully Proportional Representation|url=http://www.jair.org/papers/paper3896.html|journal=Journal of Artificial Intelligence Research|volume=47}}</ref><ref>{{Cite journal|last=Skowron|first=Piotr|last2=Yu|first2=Lan|last3=Faliszewski|first3=Piotr|last4=Elkind|first4=Edith|date=2015-03-02|title=The complexity of fully proportional representation for single-crossing electorates|url=http://www.sciencedirect.com/science/article/pii/S0304397514010111|journal=Theoretical Computer Science|volume=569|pages=43–57|doi=10.1016/j.tcs.2014.12.012}}</ref> can be computed in polynomial time when preferences are structured appropriately. On the other hand, manipulation problem also tend to be easy on these domains<ref name=":2" /><ref>{{Cite journal|last=Faliszewski|first=Piotr|last2=Hemaspaandra|first2=Edith|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|url=http://www.sciencedirect.com/science/article/pii/S0890540110001525|journal=Information and Computation|volume=209|issue=2|pages=89–107|doi=10.1016/j.ic.2010.09.001}}</ref>, so complexity shields against manipulation are less effective. 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<ref name=":3">{{Cite journal|last=Doignon|first=J. P.|last2=Falmagne|first2=J. C.|date=1994-03-01|title=A Polynomial Time Algorithm for Unidimensional Unfolding Representations|url=http://www.sciencedirect.com/science/article/pii/S0196677484710108|journal=Journal of Algorithms|volume=16|issue=2|pages=218–233|doi=10.1006/jagm.1994.1010}}</ref><ref>{{Cite journal|last=Escoffier|first=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|location=Amsterdam, The Netherlands, The Netherlands|publisher=IOS Press|pages=366–370|isbn=9781586038915}}</ref> and single-crossing<ref name=":3" /> preferences, but can be hard for more general classes<ref>{{Cite journal|last=Peters|first=Dominik|date=2016-02-25|title=Recognising Multidimensional Euclidean Preferences|url=http://arxiv.org/abs/1602.08109|journal=arXiv:1602.08109 [cs]}}</ref>.
* '''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 [[Recommender system|recommendations]] or [[Facility location problem|facilities]] or a shared bundle of items. Work in computational social choice has focussed on defining such voting rules<ref>{{Cite journal|last=Skowron|first=Piotr|last2=Faliszewski|first2=Piotr|last3=Lang|first3=Jerome|date=2015-01-01|title=Finding a Collective Set of Items: From Proportional Multirepresentation to Group Recommendation|url=http://dl.acm.org/citation.cfm?id=2886521.2886617|journal=Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence|series=AAAI'15|location=Austin, Texas|publisher=AAAI Press|pages=2131–2137|isbn=0262511290}}</ref>, understanding their properties<ref>{{Cite journal|last=Elkind|first=Edith|last2=Faliszewski|first2=Piotr|last3=Skowron|first3=Piotr|last4=Slinko|first4=Arkadii|date=2014-01-01|title=Properties of Multiwinner Voting Rules|url=http://dl.acm.org/citation.cfm?id=2615731.2615743|journal=Proceedings of the 2014 International Conference on Autonomous Agents and Multi-agent Systems|series=AAMAS '14|location=Richland, SC|publisher=International Foundation for Autonomous Agents and Multiagent Systems|pages=53–60|isbn=9781450327381}}</ref>, and studying the complexity of the associated winner determination problems<ref>{{Cite journal|last=Procaccia|first=Ariel D.|last2=Rosenschein|first2=Jeffrey S.|last3=Zohar|first3=Aviv|date=2007-04-19|title=On the complexity of achieving proportional representation|url=http://link.springer.com/article/10.1007/s00355-007-0235-2|journal=Social Choice and Welfare|language=en|volume=30|issue=3|pages=353–362|doi=10.1007/s00355-007-0235-2|issn=0176-1714}}</ref><ref>{{Cite journal|last=Lu|first=Tyler|last2=Boutilier|first2=Craig|date=2011-01-01|title=Budgeted Social Choice: From Consensus to Personalized Decision Making|url=http://dx.doi.org/10.5591/978-1-57735-516-8/IJCAI11-057|journal=Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence - Volume Volume One|series=IJCAI'11|location=Barcelona, Catalonia, Spain|publisher=AAAI Press|pages=280–286|doi=10.5591/978-1-57735-516-8/IJCAI11-057|isbn=9781577355137}}</ref><ref>{{Cite journal|last=Skowron|first=Piotr|last2=Faliszewski|first2=Piotr|last3=Slinko|first3=Arkadii|date=2015-05-01|title=Achieving fully proportional representation: Approximability results|url=http://www.sciencedirect.com/science/article/pii/S0004370215000132|journal=Artificial Intelligence|volume=222|pages=67–103|doi=10.1016/j.artint.2015.01.003}}</ref>.
* '''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 [[Recommender system|recommendations]] or [[Facility location problem|facilities]] or a shared bundle of items. Work in computational social choice has focussed on defining such voting rules<ref>{{Cite journal|last=Skowron|first=Piotr|last2=Faliszewski|first2=Piotr|last3=Lang|first3=Jerome|date=2015-01-01|title=Finding a Collective Set of Items: From Proportional Multirepresentation to Group Recommendation|url=http://dl.acm.org/citation.cfm?id=2886521.2886617|journal=Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence|series=AAAI'15|location=Austin, Texas|publisher=AAAI Press|pages=2131–2137|isbn=0262511290}}</ref>, understanding their properties<ref>{{Cite journal|last=Elkind|first=Edith|last2=Faliszewski|first2=Piotr|last3=Skowron|first3=Piotr|last4=Slinko|first4=Arkadii|date=2014-01-01|title=Properties of Multiwinner Voting Rules|url=http://dl.acm.org/citation.cfm?id=2615731.2615743|journal=Proceedings of the 2014 International Conference on Autonomous Agents and Multi-agent Systems|series=AAMAS '14|location=Richland, SC|publisher=International Foundation for Autonomous Agents and Multiagent Systems|pages=53–60|isbn=9781450327381}}</ref>, and studying the complexity of the associated winner determination problems<ref>{{Cite journal|last=Procaccia|first=Ariel D.|last2=Rosenschein|first2=Jeffrey S.|last3=Zohar|first3=Aviv|date=2007-04-19|title=On the complexity of achieving proportional representation|url=http://link.springer.com/article/10.1007/s00355-007-0235-2|journal=Social Choice and Welfare|language=en|volume=30|issue=3|pages=353–362|doi=10.1007/s00355-007-0235-2|issn=0176-1714}}</ref><ref>{{Cite journal|last=Lu|first=Tyler|last2=Boutilier|first2=Craig|date=2011-01-01|title=Budgeted Social Choice: From Consensus to Personalized Decision Making|url=http://dx.doi.org/10.5591/978-1-57735-516-8/IJCAI11-057|journal=Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence - Volume Volume One|series=IJCAI'11|location=Barcelona, Catalonia, Spain|publisher=AAAI Press|pages=280–286|doi=10.5591/978-1-57735-516-8/IJCAI11-057|isbn=9781577355137}}</ref><ref>{{Cite journal|last=Skowron|first=Piotr|last2=Faliszewski|first2=Piotr|last3=Slinko|first3=Arkadii|date=2015-05-01|title=Achieving fully proportional representation: Approximability results|url=http://www.sciencedirect.com/science/article/pii/S0004370215000132|journal=Artificial Intelligence|volume=222|pages=67–103|doi=10.1016/j.artint.2015.01.003}}</ref>.

Revision as of 16:05, 18 November 2016

Computational social choice[1] is a field at the intersection of social choice theory and (theoretical) computer science (and the study of multi-agent systems). It analyzes 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

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, an algorithm is thought to be efficient if it takes polynomial time. Many popular voting systems can be evaluated in polynomial time in a straightforward way (through counting), such as the Borda count, approval voting, or the plurality rule. For rules such as the Schulze method[2] or ranked pairs[3], more sophisticated algorithms can be used to show polynomial runtime. As first pointed in an influential article in 1989[4], certain voting systems are computationally difficult to evaluate. In particular, winner determination for the Kemeny-Young method[4][5], Dodgson's method[4][6], and Young's method[7] are all NP-hard problems. This has led to the development of approximation algorithms[8][9] and fixed-parameter tractable algorithms[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. Much effort in social choice theory has been invested in finding ways to circumvent this result. One such possibility was proposed by Bartholdi, Tovey, and Trick in 1989[11] and is based on computational complexity theory. They considered a voting rule called 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].

These results show that (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. In this sense, 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 has studied the complexity of the associated winner determination problems[1].
  • Preference restrictions. Restricted preference domains, such as single-peaked[16] or single-crossing[17] preferences, are an important area of study in social choice theory, since preferences from these domains avoid the Condorcet paradox[18][19] and thus can circumvent impossibility results like Arrow's and the Gibbard-Satterthwaite theorem. From a computational perspective, such domain restrictions are useful to speed up winner determination problems[20], both computationally hard single-winner[21] and multi-winner rules[22][23] can be computed in polynomial time when preferences are structured appropriately. On the other hand, manipulation problem also tend to be easy on these domains[21][24], so complexity shields against manipulation are less effective. 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[25][26] and single-crossing[25] preferences, but can be hard for more general classes[27].
  • 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 focussed on defining such voting rules[28], understanding their properties[29], and studying the complexity of the associated winner determination problems[30][31][32].

See also

References

  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. ISSN 0176-1714.
  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. Toronto, Ontario, Canada: AAAI Press: 1299–1305.
  4. ^ a b c 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. ISSN 0176-1714.
  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-11-01). "Exact Analysis of Dodgson Elections: Lewis Carroll's 1876 Voting System is Complete for Parallel Access to NP". J. ACM. 44 (6): 806–825. doi:10.1145/268999.269002. ISSN 0004-5411.
  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. doi:10.1007/s00224-002-1093-z. ISSN 1432-4350.
  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. ISSN 0004-5411.
  10. ^ Betzler, Nadja; Fellows, Michael R.; Guo, Jiong; Niedermeier, Rolf; Rosamond, Frances A. (2008-06-23). Fleischer, Rudolf; Xu, Jinhui (eds.). Fixed-Parameter Algorithms for Kemeny Scores. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 60–71. doi:10.1007/978-3-540-68880-8_8. ISBN 9783540688655.
  11. ^ Bartholdi, J. J.; Tovey, C. A.; Trick, M. A. "The computational difficulty of manipulating an election". Social Choice and Welfare. 6 (3): 227–241. doi:10.1007/BF00295861. ISSN 0176-1714.
  12. ^ Bartholdi, John J.; Orlin, James B. "Single transferable vote resists strategic voting". Social Choice and Welfare. 8 (4): 341–354. doi:10.1007/BF00183045. ISSN 0176-1714.
  13. ^ Faliszewski, Piotr; Procaccia, Ariel D. (2010-09-23). "AI's War on Manipulation: Are We Winning?". AI Magazine. 31 (4): 53–64. doi:10.1609/aimag.v31i4.2314. ISSN 0738-4602.
  14. ^ Fishburn, P. (1977-11-01). "Condorcet Social Choice Functions". SIAM Journal on Applied Mathematics. 33 (3): 469–489. doi:10.1137/0133030. ISSN 0036-1399.
  15. ^ Moon, John W. (1968-01-01). Topics on tournaments. Holt, Rinehart and Winston.
  16. ^ Black, Duncan (1948-01-01). "On the Rationale of Group Decision-making". Journal of Political Economy. 56 (1): 23–34. JSTOR 1825026.
  17. ^ Rothstein, P. (1990-12-01). "Order restricted preferences and majority rule". Social Choice and Welfare. 7 (4): 331–342. doi:10.1007/BF01376281. ISSN 0176-1714.
  18. ^ Arrow, Kenneth J. (2012-06-26). Social Choice and Individual Values. Yale University Press. ISBN 0300186983.
  19. ^ 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.
  20. ^ 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. New York: AAAI Press: 4062–4065.
  21. ^ 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. doi:10.1613/jair.4647.
  22. ^ N., Betzler,; A., Slinko,; J., Uhlmann, (2013-01-01). "On the Computation of Fully Proportional Representation". Journal of Artificial Intelligence Research. 47.{{cite journal}}: CS1 maint: extra punctuation (link) CS1 maint: multiple names: authors list (link)
  23. ^ 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. doi:10.1016/j.tcs.2014.12.012.
  24. ^ 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. doi:10.1016/j.ic.2010.09.001.
  25. ^ a b Doignon, J. P.; Falmagne, J. C. (1994-03-01). "A Polynomial Time Algorithm for Unidimensional Unfolding Representations". Journal of Algorithms. 16 (2): 218–233. doi:10.1006/jagm.1994.1010.
  26. ^ 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. Amsterdam, The Netherlands, The Netherlands: IOS Press: 366–370. ISBN 9781586038915.
  27. ^ Peters, Dominik (2016-02-25). "Recognising Multidimensional Euclidean Preferences". arXiv:1602.08109 [cs].
  28. ^ Skowron, Piotr; Faliszewski, Piotr; Lang, Jerome (2015-01-01). "Finding a Collective Set of Items: From Proportional Multirepresentation to Group Recommendation". Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence. AAAI'15. Austin, Texas: AAAI Press: 2131–2137. ISBN 0262511290.
  29. ^ Elkind, Edith; Faliszewski, Piotr; Skowron, Piotr; Slinko, Arkadii (2014-01-01). "Properties of Multiwinner Voting Rules". Proceedings of the 2014 International Conference on Autonomous Agents and Multi-agent Systems. AAMAS '14. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems: 53–60. ISBN 9781450327381.
  30. ^ Procaccia, Ariel D.; Rosenschein, Jeffrey S.; Zohar, Aviv (2007-04-19). "On the complexity of achieving proportional representation". Social Choice and Welfare. 30 (3): 353–362. doi:10.1007/s00355-007-0235-2. ISSN 0176-1714.
  31. ^ Lu, Tyler; Boutilier, Craig (2011-01-01). "Budgeted Social Choice: From Consensus to Personalized Decision Making". Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence - Volume Volume One. IJCAI'11. Barcelona, Catalonia, Spain: AAAI Press: 280–286. doi:10.5591/978-1-57735-516-8/IJCAI11-057. ISBN 9781577355137.
  32. ^ Skowron, Piotr; Faliszewski, Piotr; Slinko, Arkadii (2015-05-01). "Achieving fully proportional representation: Approximability results". Artificial Intelligence. 222: 67–103. doi:10.1016/j.artint.2015.01.003.
  • The 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&oldid=750244874"