nach oben

Social Choice and Welfare

Erschienen in:

16.01.2018 | Original Paper

Extending tournament solutions

verfasst von: Felix Brandt, Markus Brill, Paul Harrenstein

Erschienen in: Social Choice and Welfare | Ausgabe 2/2018

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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.

Nächster Artikel The socially acceptable scoring rule

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

This definition slightly diverges from the common graph-theoretic definition where $\succsim $ is defined on A rather than on U. However, it facilitates the definition of tournament solutions and their properties.

Defining tournaments with a reflexive dominance relation is non-standard. The reason we define tournaments in such a way is to ensure that every tournament is a weak tournament. Whether the dominance relation of a tournament is reflexive or not does not make a difference for any of our results.

Similarly, one could define a generic extension that returns all alternatives that are chosen in all orientations of the weak tournament. However, this extension would not constitute a generalized tournament solution because it may return the empty set.

For instance, the property monotonicity requires that a chosen alternative is still chosen if it is strengthened. In this case, the operation $ f $ would map a weak tournament W to a weak tournament $W'$ that is identical to W except that some alternative in S(W) has been strengthened with respect to another alternative. See Sect. 4.2 for details.

There is another way of strengthening a against b that is not captured by this definition, namely, replacing $b \succ a$ with $a \sim b$. Let us refer to this additional operation as a $\sim $-strengthening. The properties monotonicity, IUA, and set-monotonicity are usually defined in such a way that $\sim $-strengthenings are also taken into account. While we do not consider $\sim $-strengthenings, it can easily be shown that the conservative extension [S] satisfies monotonicity, IUA, or set-monotonicity with respect to $\sim $-strengthenings whenever [S] satisfies the respective property with respect to strengthenings as defined here.

We refer to Monjardet (2008) for a more thorough discussion of the origins of this condition.

The same is true for Sen’s original $\gamma $ (e.g., Moulin 1986).

For example, this statement holds for all tournament solutions considered in Sect. 5: $ TC $, $ BP $, and $ MC $ satisfy both ${\widehat{\alpha }}$ and ${\widehat{\gamma }}$, and $ CO $, $ UC $, $ BA $, and $ TEQ $ satisfy neither ${\widehat{\alpha }}$ nor ${\widehat{\gamma }}$.

We note that alternative definitions, such as the one discussed after Proposition 8, are conceivable.

A similar argument, involving a more complicated weak tournament can be given for the tournament solution $ BA _{ reg }$ defined such that, for all tournaments $T=(A,\succ )$,

$$\begin{aligned} BA _{ reg }(T) = {\left\{ \begin{array}{ll} A &{} \text {if } T \text { is regular,}\\ BA (T) &{} \text {otherwise.} \end{array}\right. } \end{aligned}$$

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–44CrossRef

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–804CrossRef

Brandt F, Harrenstein P (2010) Characterization of dominance relations in finite coalitional games. Theory Decis 69(2):233–256CrossRef

Brandt F, Harrenstein P (2011) Set-rationalizable choice and self-stability. J Econ Theory 146(4):1721–1731CrossRef

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)CrossRef

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, CambridgeCrossRef

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–443CrossRef

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–535CrossRef

Duggan J, Le Breton M (1996) Dutta’s minimal covering set and Shapley’s saddles. J Econ Theory 70(1):257–265CrossRef

Duggan J, Le Breton M (2001) Mixed refinements of Shapley’s saddles and weak tournaments. Soc Choice Welf 18(1):65–78CrossRef

Dutta B, Laslier J-F (1999) Comparison functions and choice correspondences. Soc Choice Welf 16(4):513–532CrossRef

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–236CrossRef

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–63CrossRef

Laffond G, Laslier J-F, Le Breton M (1993) The bipartisan set of a tournament game. Games Econ Behav 5(1):182–201CrossRef

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–157CrossRef

Laslier J-F (1997) Tournament solutions and majority voting. Springer, BerlinCrossRef

Masatlioglu Y, Nakajima D, Ozbay EY (2012) Revealed attention. Am Econ Rev 102(5):2183–2205CrossRef

May K (1952) A set of independent, necessary and sufficient conditions for simple majority decisions. Econometrica 20(4):680–684CrossRef

Monjardet B (2008) Statement of precedence and a comment on IIA terminology. Games Econ Behav 62:736–738CrossRef

Moulin H (1986) Choosing from a tournament. Soc Choice Welf 3(4):271–291CrossRef

Peris JE, Subiza B (1999) Condorcet choice correspondences for weak tournaments. Soc Choice Welf 16(2):217–231CrossRef

Schwartz T (1972) Rationality and the myth of the maximum. Noûs 6(2):97–117CrossRef

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–29CrossRef

Sen AK (1986) Social choice theory. In: Arrow KJ, Intriligator MD (eds) Handbook of mathematical economics, vol 3, Chapter 22. Elsevier, Amsterdam, pp 1073–1181CrossRef

Woeginger GJ (2003) Banks winners in tournaments are difficult to recognize. Soc Choice Welf 20(3):523–528CrossRef

Titel: Extending tournament solutions
verfasst von: Felix Brandt
Markus Brill
Paul Harrenstein
Publikationsdatum: 16.01.2018
Verlag: Springer Berlin Heidelberg
Erschienen in: Social Choice and Welfare / Ausgabe 2/2018
Print ISSN: 0176-1714
Elektronische ISSN: 1432-217X
DOI: https://doi.org/10.1007/s00355-018-1112-x

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 2/2018

Transitions in poverty and its deprivations

Electoral competition under best-worst voting rules

How to rank rankings? Group performance in multiple-prize contests

The bargaining correspondence: when Edgeworth meets Nash

The socially acceptable scoring rule

Revealed votes