Computational social choice
Computational social choice is a field at the intersection of
Winner determination
The usefulness of a particular
Hardness of manipulation
By the
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
This section may be too technical for most readers to understand.(July 2017) |
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
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
- Algocracy
- Algorithmic game theory
- Algorithmic mechanism design
- Cake-cutting
- Fair division
- Hedonic games
References
- ^ ISBN 9781107060432.
- 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.
- ^ S2CID 154114517.
- .
- S2CID 367623.
- S2CID 3205730.
- .
- S2CID 5674305.
- ISBN 9783540688655.
- S2CID 16158098.
- S2CID 17749613.
- .
- doi:10.1137/0133030.
- ^ Laslier, Jean-François (1997). Tournament Solutions and Majority Voting. Springer Verlag.
- ^ Moon, John W. (1968-01-01). Topics on tournaments. Holt, Rinehart and Winston.
- S2CID 153953456.
- S2CID 153683957.
- ISBN 978-0300186987.
- .
- ^ 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.
- ^ hdl:1802/10425.
- S2CID 2839179.
- S2CID 5348844.
- .
- arXiv:1602.08109 [cs.GT].
- .
- ISBN 9781586038915.
External links
- The COMSOC website, offering a collection of materials related to computational social choice, such as academic workshops, PhD theses, and a mailing list.