Extending tournament solutions
Tóm tắt
An important subclass of social choice functions, so-called majoritarian (or C1) functions, only take into account the pairwise majority relation between alternatives. In the absence of majority ties—e.g., when there is an odd number of agents with linear preferences—the majority relation is antisymmetric and complete and can thus conveniently be represented by a tournament. Tournaments have a rich mathematical theory and many formal results for majoritarian functions assume that the majority relation constitutes a tournament. Moreover, most majoritarian functions have only been defined for tournaments and allow for a variety of generalizations to unrestricted preference profiles, none of which can be seen as the unequivocal extension of the original function. In this paper, we argue that restricting attention to tournaments is justified by the existence of a conservative extension, which inherits most of the commonly considered properties from its underlying tournament solution.
Tài liệu tham khảo
Aizerman M, Aleskerov F (1995) Theory of choice, Studies in mathematical and managerial economics, vol 38. North-Holland, Amsterdam
Arrow KJ, Raynaud H (1986) Social choice and multicriterion decision-making. MIT Press, Cambridge
Aziz H, Brill M, Fischer F, Harrenstein P, Lang J, Seedig HG (2015) Possible and necessary winners of partial tournaments. J Artif Intell Res 54:493–534
Banks JS, Bordes GA (1988) Voting games, indifference, and consistent sequential choice rules. Soc Choice Welf 5:31–44
Bordes G (1979) Some more results on consistency, rationality and collective choice. In: Laffont JJ (ed) Aggregation and revelation of preferences, chapter 10. North-Holland, Amsterdam, pp 175–197
Bouyssou D, Marchant T, Pirlot M, Tsoukiàs A, Vincke P (2006) Evaluation and decision models: stepping stones for the analyst. Springer, Berlin
Brandt F(2009) Tournament solutions—extensions of maximality and their applications to decision-making. Habilitation Thesis, Faculty for Mathematics, Computer Science, and Statistics, University of Munich
Brandt F (2015) Set-monotonicity implies Kelly-strategyproofness. Soc Choice Welf 45(4):793–804
Brandt F, Harrenstein P (2010) Characterization of dominance relations in finite coalitional games. Theory Decis 69(2):233–256
Brandt F, Harrenstein P (2011) Set-rationalizable choice and self-stability. J Econ Theory 146(4):1721–1731
Brandt F, Fischer F, Harrenstein P (2009) The computational complexity of choice sets. Math Log Q 55(4):444–459 (Special Issue on Computational Social Choice)
Brandt F, Brill M, Harrenstein P (2016) Tournament solutions. In: Brandt F, Conitzer V, Endriss U, Lang J, Procaccia AD (eds) Handbook of computational social choice, Chapter 3. Cambridge University Press, Cambridge
Brandt F, Brill M, Seedig HG, Suksompong W (2018) On the structure of stable tournament solutions. Econ Theory (forthcoming). https://doi.org/10.1007/s00199-016-1024-x
Brill M, Fischer F (2012) The price of neutrality for the ranked pairs method. In: Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI). AAAI Press, Palo Alto, pp 1299–1305
Brill M, Freeman R, Conitzer V (2016) Computing possible and necessary equilibrium actions (and bipartisan set winners). In: Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI). AAAI Press, Palo Alto, pp 418–424
Chernoff H (1954) Rational selection of decision functions. Econometrica 22(4):422–443
Conitzer V, Rognlie M, Xia L (2009) Preference functions that score rankings and maximum likelihood estimation. In: Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI). AAAI Press, Palo Alto, pp 109–115
Cook WJ, Cunningham WH, Pulleyblank WR, Schrijver A (1998) Combinatorial optimization. Wiley, New York
Duggan J (2013) Uncovered sets. Soc Choice Welf 41(3):489–535
Duggan J, Le Breton M (1996) Dutta’s minimal covering set and Shapley’s saddles. J Econ Theory 70(1):257–265
Duggan J, Le Breton M (2001) Mixed refinements of Shapley’s saddles and weak tournaments. Soc Choice Welf 18(1):65–78
Dutta B, Laslier J-F (1999) Comparison functions and choice correspondences. Soc Choice Welf 16(4):513–532
Faliszewski P, Hemaspaandra E, Hemaspaandra L, Rothe J (2009) Llull and Copeland voting computationally resist bribery and constructive control. J Artif Intell Res 35:275–341
Fisher DC, Ryan J (1995) Tournament games and positive tournaments. J Graph Theory 19(2):217–236
Freeman R, Brill M, Conitzer V (2015) General tiebreaking schemes for computational social choice. In: Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS). IFAAMAS, pp 1401–1409
Henriet D (1985) The Copeland choice function: an axiomatic characterization. Soc Choice Welf 2(1):49–63
Laffond G, Laslier J-F, Le Breton M (1993) The bipartisan set of a tournament game. Games Econ Behav 5(1):182–201
Lang J, Pini MS, Rossi F, Salvagnin D, Venable KB, Walsh T (2012) Winner determination in voting trees with incomplete preferences and weighted votes. J Auton Agents Multi Agent Syst 25(1):130–157
Laslier J-F (1997) Tournament solutions and majority voting. Springer, Berlin
Masatlioglu Y, Nakajima D, Ozbay EY (2012) Revealed attention. Am Econ Rev 102(5):2183–2205
May K (1952) A set of independent, necessary and sufficient conditions for simple majority decisions. Econometrica 20(4):680–684
Monjardet B (2008) Statement of precedence and a comment on IIA terminology. Games Econ Behav 62:736–738
Moulin H (1986) Choosing from a tournament. Soc Choice Welf 3(4):271–291
Peris JE, Subiza B (1999) Condorcet choice correspondences for weak tournaments. Soc Choice Welf 16(2):217–231
Schwartz T (1972) Rationality and the myth of the maximum. Noûs 6(2):97–117
Schwartz T (1986) The logic of collective choice. Columbia University Press, New York
Schwartz T (1990) Cyclic tournaments and cooperative majority voting: a solution. Soc Choice Welf 7(1):19–29
Sen AK (1986) Social choice theory. In: Arrow KJ, Intriligator MD (eds) Handbook of mathematical economics, vol 3, Chapter 22. Elsevier, Amsterdam, pp 1073–1181
Woeginger GJ (2003) Banks winners in tournaments are difficult to recognize. Soc Choice Welf 20(3):523–528