nach oben

Social Choice and Welfare

Erschienen in:

17.02.2015

Set-monotonicity implies Kelly-strategyproofness

verfasst von: Felix Brandt

Erschienen in: Social Choice and Welfare | Ausgabe 4/2015

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

This paper studies the strategic manipulation of set-valued social choice functions according to Kelly’s preference extension, which prescribes that one set of alternatives is preferred to another if and only if all elements of the former are preferred to all elements of the latter. It is shown that set-monotonicity—a new variant of Maskin-monotonicity—implies Kelly-strategyproofness in comprehensive subdomains of the linear domain. Interestingly, there are a handful of appealing Condorcet extensions—such as the top cycle, the minimal covering set, and the bipartisan set—that satisfy set-monotonicity even in the unrestricted linear domain, thereby answering questions raised independently by Barberà (J Econ Theory 15(2):266–278(1977a)) and Kelly (Econometrica 45(2):439–446 (1977)).

Vorheriger Artikel The tyranny puzzle in social preferences: an empirical investigation

Nächster Artikel Level consensus and stable social choice

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

For instance, Gärdenfors (1976) claims that “[resoluteness] is a rather restrictive and unnatural assumption.” In a similar vein, Kelly (1977) writes that “the Gibbard–Satterthwaite theorem [...] uses an assumption of singlevaluedness which is unreasonable” and Taylor (2005) that “If there is a weakness to the Gibbard–Satterthwaite theorem, it is the assumption that winners are unique.” This sentiment is echoed by various other authors (see, e.g., Barberà 1977b; Feldman 1979b; Bandyopadhyay 1983a, b; Duggan and Schwartz 2000; Nehring 2000; Ching and Zhou 2002).

Barberà (1977a) actually uses an extension that is even weaker than that of Kelly (1977).

According to Nehring’s definition, a manipulator is only better off if he strictly prefers all alternatives in the new choice set to all alternatives in the original choice set. For linear preferences, the two definitions only differ in whether there can be a single alternative at the intersection of both choice sets or not.

Sanver and Zwicker (2012) study monotonicity properties for set-valued SCFs in general. None of the properties they consider is equivalent to set-monotonicity.

Note that set-monotonicity is in conflict with decisiveness. For instance, non-trivial set-monotonic SCFs cannot satisfy the (rather strong) positive responsiveness condition introduced by Barberà (1977b).

The strong superset property goes back to early work by Chernoff (1954) (where it was called postulate \(5^*\)) and is also known as \(\widehat{\alpha }\) (Brandt and Harrenstein 2011), the attention filter axiom (Masatlioglu et al. 2012), and outcast (Aizerman and Aleskerov 1995). The term strong superset property was first used by Bordes (1979). We refer to Monjardet (2008) for a more thorough discussion of the origins of this condition.

Remarkably, the robustness of the minimal covering set and the bipartisan set with respect to strategic manipulation also extends to agenda manipulation. The strong superset property precisely states that an SCF is resistant to adding and deleting losing alternatives (see also the discussion by Bordes 1983). Moreover, both SCFs are composition-consistent, i.e., they are strongly resistant to the introduction of clones (Laffond et al. 1996). Scoring rules like plurality and Borda’s rule are prone to both types of agenda manipulation (Laslier 1996; Brandt and Harrenstein 2011) as well as to strategic manipulation.

Another prominent Condorcet extension—the tournament equilibrium set (Schwartz 1990)—was conjectured to satisfy SSP and monotonicity for almost 20 years. This conjecture was recently disproved by Brandt et al. (2013). In fact, it can be shown that the tournament equilibrium set as well as the related minimal extending set (Brandt 2011) can be Kelly-manipulated.

For generalized strategyproofness as defined by Nehring (2000) (see Remark 6), the second condition is not required and every coarsening of a strategyproof SCF is strategyproof.

For generalized strategyproofness, it would also suffice to require a weakening of set-monotonicity in which the choice set can only get smaller when unchosen alternatives are weakened.

Pérez (2001) and Jimeno et al. (2009) have proved versions of Moulin’s theorem (Moulin 1988) for set-valued Condorcet extensions by using stronger assumptions on preference over sets.

Aizerman M, Aleskerov F (1995) Theory of choice, of studies in mathematical and managerial economics, vol 38. North-Holland, Amsterdam

Bandyopadhyay T (1982) Threats, counter-threats and strategic manipulation for non-binary group decision rules. Math Soc Sci 2(2):145–155CrossRef

Bandyopadhyay T (1983a) Multi-valued decision rules and coalitional non-manipulability. Econ Lett 13(1):37–44CrossRef

Bandyopadhyay T (1983b) Manipulation of non-imposed, non-oligarchic, non-binary group decision rules. Econ Lett 11(1–2):69–73CrossRef

Barberà S (1977a) Manipulation of social decision functions. J Econ Theory 15(2):266–278CrossRef

Barberà S (1977b) The manipulation of social choice mechanisms that do not leave too much to chance. Econometrica 45(7):1573–1588CrossRef

Barberà S (1979) A note on group strategy-proof decision schemes. Econometrica 47(3):637–640CrossRef

Barberà S (2010) Strategy-proof social choice. In: Arrow KJ, Sen AK, Suzumura K (eds) Handbook of Social Choice and Welfare, vol. 2, Chap. 25. Elsevier, Amsterdam, pp 731–832

Barberà S, Dutta B, Sen A (2001) Strategy-proof social choice correspondences. J Econ Theory 101(2):374–394CrossRef

Bordes G (1976) Consistency, rationality and collective choice. Rev Econ Stud 43(3):451–457CrossRef

Bordes G (1979) Some more results on consistency, rationality and collective choice. In: Laffont JJ (ed) Aggregation and Revelation of Preferences, Chap. 10. North-Holland, Amsterdam, pp 175–197

Bordes G (1983) On the possibility of reasonable consistent majoritarian choice: some positive results. J Econ Theory 31:122–132CrossRef

Brandt F (2011) Minimal stable sets in tournaments. J Econ Theory 146(4):1481–1499CrossRef

Brandt F, Brill M (2011) Necessary and sufficient conditions for the strategyproofness of irresolute social choice functions. In: Proceedings of the 13th conference on theoretical aspects of rationality and knowledge (TARK), ACM Press, pp 136–142

Brandt, F. Geist C (2014) Finding strategyproof social choice functions via SAT solving. In: Proceedings of the 13th international conference on autonomous agents and multi-agent systems (AAMAS) IFAAMAS, pp 1193–1200

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

Brandt F, Chudnovsky M, Kim I, Liu G, Norin S, Scott A, Seymour P, Thomassé S (2013) A counterexample to a conjecture of Schwartz. Soc Choice Welfare 40:739–743CrossRef

Chernoff H (1954) Rational selection of decision functions. Econometrica 22:422–443CrossRef

Ching S, Zhou L (2002) Multi-valued strategy-proof social choice rules. Soc Choice Welfare 19:569–580CrossRef

Duggan J (2013) Uncovered sets. Soc Choice Welfare 41:489–535CrossRef

Duggan J, Schwartz T (2000) Strategic manipulability without resoluteness or shared beliefs: Gibbard-Satterthwaite generalized. Soc Choice Welfare 17(1):85–93CrossRef

Dutta B (1990) On the tournament equilibrium set. Soc Choice Welfare 7(4):381–383CrossRef

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

Feldman A (1979a) Manipulation and the Pareto rule. J Econ Theory 21:473–482CrossRef

Feldman A (1979b) Nonmanipulable multi-valued social choice decision functions. Public Choice 34:177–188CrossRef

Fishburn PC, Brams SJ (1983) Paradoxes of preferential voting. Mathematics Magazine 56(4):207–214CrossRef

Gärdenfors P (1976) Manipulation of social choice functions. J Econ Theory 13(2):217–228CrossRef

Gibbard A (1973) Manipulation of voting schemes. Econometrica 41:587–602CrossRef

Gibbard A (1977) Manipulation of schemes that mix voting with chance. Econometrica 45(3):665–681CrossRef

Gibbard A (1978) Straightforwardness of game forms with lotteries as outcomes. Econometrica 46(3):595–614CrossRef

Good IJ (1971) A note on Condorcet sets. Public Choice 10:97–101CrossRef

Jimeno JL, Pérez J, García E (2009) An extension of the Moulin no show paradox for voting correspondences. Soc Choice Welfare 33(3):343–459CrossRef

Kelly JS (1977) Strategy-proofness and social choice functions without single-valuedness. Econometrica 45(2):439–446CrossRef

Klaus B, Bochet O (2013) The relation between monotonicity and strategyproofness. Soc Choice Welfare 40(1):41–63CrossRef

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

Laffond G, Lainé J, Laslier J-F (1996) Composition-consistent tournament solutions and social choice functions. Soc Choice Welfare 13:75–93CrossRef

Laslier J-F (1996) Rank-based choice correspondences. Econ Lett 52:279–286CrossRef

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

Laslier J-F (2000) Aggregation of preferences with a variable set of alternatives. Soc Choice Welfare 17:269–282CrossRef

MacIntyre I, Pattanaik PK (1981) Strategic voting under minimally binary group decision functions. J Econ Theory 25(3):338–352CrossRef

Mas-Colell A, Sonnenschein H (1972) General possibility theorems for group decisions. Rev Econ Stud 39(2):185–192CrossRef

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

Maskin E (1999) Nash equilibrium and welfare optimality. Rev Econ Stud 66(26):23–38CrossRef

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

Moulin H (1988) Condorcet’s principle implies the no show paradox. J Econ Theory 45:53–64CrossRef

Muller E, Satterthwaite MA (1977) The equivalence of strong positive association and strategy-proofness. J Econ Theory 14(2):412–418CrossRef

Nehring K (2000) Monotonicity implies generalized strategy-proofness for correspondences. Soc Choice Welfare 17(2):367–375CrossRef

Pérez J (2001) The strong no show paradoxes are a common flaw in Condorcet voting correspondences. Soc Choice Welfare 18(3):601–616CrossRef

Sanver MR, Zwicker WS (2012) Monotonicity properties and their adaption to irresolute social choice rules. Soc Choice Welfare 39(2–3):371–398CrossRef

Sato S (2008) On strategy-proof social choice correspondences. Soc Choice Welfare 31:331–343CrossRef

Satterthwaite MA (1975) Strategy-proofness and Arrow’s conditions: existence and correspondence theorems for voting procedures and social welfare functions. J Econ Theory 10:187–217CrossRef

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 Welfare 7(1):19–29CrossRef

Sen AK (1977) Social choice theory: a re-examination. Econometrica 45(1):53–89CrossRef

Smith JH (1973) Aggregation of preferences with variable electorate. Econometrica 41(6):1027–1041CrossRef

Taylor AD (2005) Social choice and the mathematics of manipulation. Cambridge University Press, New YorkCrossRef

Umezawa M (2009) Coalitionally strategy-proof social choice correspondences and the Pareto rule. Soc Choice Welfare 33:151–158CrossRef

von Neumann J, Morgenstern O (1947) Theory of games and economic behavior, 2nd edn. Princeton University Press, Princeton

Titel: Set-monotonicity implies Kelly-strategyproofness
verfasst von: Felix Brandt
Publikationsdatum: 17.02.2015
Verlag: Springer Berlin Heidelberg
Erschienen in: Social Choice and Welfare / Ausgabe 4/2015
Print ISSN: 0176-1714
Elektronische ISSN: 1432-217X
DOI: https://doi.org/10.1007/s00355-015-0881-8

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 4/2015

A Hurwicz type result in a model with public good production

Tagging with leisure needs

Efficient extensions of the Myerson value

Level $$r$$ r consensus and stable social choice

Choosing two finalists and the winner

The tyranny puzzle in social preferences: an empirical investigation

Premium Partner