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)).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
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).
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, 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.
References
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–155
Bandyopadhyay T (1983a) Multi-valued decision rules and coalitional non-manipulability. Econ Lett 13(1):37–44
Bandyopadhyay T (1983b) Manipulation of non-imposed, non-oligarchic, non-binary group decision rules. Econ Lett 11(1–2):69–73
Barberà S (1977a) Manipulation of social decision functions. J Econ Theory 15(2):266–278
Barberà S (1977b) The manipulation of social choice mechanisms that do not leave too much to chance. Econometrica 45(7):1573–1588
Barberà S (1979) A note on group strategy-proof decision schemes. Econometrica 47(3):637–640
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–394
Bordes G (1976) Consistency, rationality and collective choice. Rev Econ Stud 43(3):451–457
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–132
Brandt F (2011) Minimal stable sets in tournaments. J Econ Theory 146(4):1481–1499
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–1731
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–743
Chernoff H (1954) Rational selection of decision functions. Econometrica 22:422–443
Ching S, Zhou L (2002) Multi-valued strategy-proof social choice rules. Soc Choice Welfare 19:569–580
Duggan J (2013) Uncovered sets. Soc Choice Welfare 41:489–535
Duggan J, Schwartz T (2000) Strategic manipulability without resoluteness or shared beliefs: Gibbard-Satterthwaite generalized. Soc Choice Welfare 17(1):85–93
Dutta B (1990) On the tournament equilibrium set. Soc Choice Welfare 7(4):381–383
Dutta B, Laslier J-F (1999) Comparison functions and choice correspondences. Soc Choice Welfare 16(4):513–532
Feldman A (1979a) Manipulation and the Pareto rule. J Econ Theory 21:473–482
Feldman A (1979b) Nonmanipulable multi-valued social choice decision functions. Public Choice 34:177–188
Fishburn PC, Brams SJ (1983) Paradoxes of preferential voting. Mathematics Magazine 56(4):207–214
Gärdenfors P (1976) Manipulation of social choice functions. J Econ Theory 13(2):217–228
Gibbard A (1973) Manipulation of voting schemes. Econometrica 41:587–602
Gibbard A (1977) Manipulation of schemes that mix voting with chance. Econometrica 45(3):665–681
Gibbard A (1978) Straightforwardness of game forms with lotteries as outcomes. Econometrica 46(3):595–614
Good IJ (1971) A note on Condorcet sets. Public Choice 10:97–101
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–459
Kelly JS (1977) Strategy-proofness and social choice functions without single-valuedness. Econometrica 45(2):439–446
Klaus B, Bochet O (2013) The relation between monotonicity and strategyproofness. Soc Choice Welfare 40(1):41–63
Laffond G, Laslier J-F, Le Breton M (1993) The bipartisan set of a tournament game. Game Econ Behav 5:182–201
Laffond G, Lainé J, Laslier J-F (1996) Composition-consistent tournament solutions and social choice functions. Soc Choice Welfare 13:75–93
Laslier J-F (1996) Rank-based choice correspondences. Econ Lett 52:279–286
Laslier J-F (1997) Tournament solutions and majority voting. Springer-Verlag, Berlin
Laslier J-F (2000) Aggregation of preferences with a variable set of alternatives. Soc Choice Welfare 17:269–282
MacIntyre I, Pattanaik PK (1981) Strategic voting under minimally binary group decision functions. J Econ Theory 25(3):338–352
Mas-Colell A, Sonnenschein H (1972) General possibility theorems for group decisions. Rev Econ Stud 39(2):185–192
Masatlioglu Y, Nakajima D, Ozbay EY (2012) Revealed attention. Am Econ Rev 102(5):2183–2205
Maskin E (1999) Nash equilibrium and welfare optimality. Rev Econ Stud 66(26):23–38
Monjardet B (2008) Statement of precedence and a comment on IIA terminology. Game Econ Behav 62:736–738
Moulin H (1988) Condorcet’s principle implies the no show paradox. J Econ Theory 45:53–64
Muller E, Satterthwaite MA (1977) The equivalence of strong positive association and strategy-proofness. J Econ Theory 14(2):412–418
Nehring K (2000) Monotonicity implies generalized strategy-proofness for correspondences. Soc Choice Welfare 17(2):367–375
Pérez J (2001) The strong no show paradoxes are a common flaw in Condorcet voting correspondences. Soc Choice Welfare 18(3):601–616
Sanver MR, Zwicker WS (2012) Monotonicity properties and their adaption to irresolute social choice rules. Soc Choice Welfare 39(2–3):371–398
Sato S (2008) On strategy-proof social choice correspondences. Soc Choice Welfare 31:331–343
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–217
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–29
Sen AK (1977) Social choice theory: a re-examination. Econometrica 45(1):53–89
Smith JH (1973) Aggregation of preferences with variable electorate. Econometrica 41(6):1027–1041
Taylor AD (2005) Social choice and the mathematics of manipulation. Cambridge University Press, New York
Umezawa M (2009) Coalitionally strategy-proof social choice correspondences and the Pareto rule. Soc Choice Welfare 33:151–158
von Neumann J, Morgenstern O (1947) Theory of games and economic behavior, 2nd edn. Princeton University Press, Princeton
Acknowledgments
I am grateful to Florian Brandl, Markus Brill, and Paul Harrenstein for helpful discussions and comments. This material is based on work supported by the Deutsche Forschungsgemeinschaft under Grants BR 2312/3-3, BR 2312/7-1, and BR 2312/7-2. Early results of this paper were presented at the 22nd International Joint Conference on Artificial Intelligence (Barcelona, July 2011). A previous version of this paper, titled “Group-Strategyproof Irresolute Social Choice Functions,” circulated since 2010.
Author information
Authors and Affiliations
Corresponding author
Appendix
Appendix
For the domain of transitive and complete (but not necessarily antisymmetric) preference relations \(\fancyscript{R}^N\), we show that all Condorcet extensions are Kelly-manipulable. This strengthens Theorem 3 by Gärdenfors (1976) and Theorem 8.1.2 by Taylor (2005), who showed the same statement for a weaker notion of manipulability and a weaker notion of Condorcet winners, respectively. When assuming that pairwise choices are made according to majority rule, this also strengthens Theorems 1 and 2 by MacIntyre and Pattanaik (1981). However, our construction requires that the number of agents is linear in the number of alternatives.
Theorem 2
No Condorcet extension is Kelly-strategyproof in domain \(\fancyscript{R}^N\) when there are more than two alternatives.
Proof
Let \(A=\{a_1,\dots ,a_m\}\) with \(m\ge 3\) and consider the following preference profile \(R\) with \(3m\) agents. In the representation below, sets denote indifference classes of the agents.
For every alternative \(a_i\), there are two agents who prefer every alternative to \(a_i\) and are otherwise indifferent. Moreover, for every alternative \(a_i\) there is one agent who prefers every alternative except \(a_{i+1}\) to \(a_i\), ranks \(a_{i+1}\) below \(a_i\), and is otherwise indifferent.
Since \(f(R)\) yields a nonempty choice set, there has to be some \(a_i\in f(R)\). Due to the symmetry of the preference profile, we may assume without loss of generality that \(a_2\in f(R)\). Now, let
and define \(R^\prime =(R_{-3},R^\prime _3)\) and \(R^{\prime \prime }=(R^\prime _{-4},R^\prime _4)\). That is, \(R^\prime \) is identical to \(R\), except that agent 3 lifted \(a_1\) on top and \(R^{\prime \prime }\) is identical to \(R^\prime \), except that agent 4 lifted \(a_1\) on top. Observe that \(f(R^{\prime \prime })=\{a_1\}\) because \(a_1\) is the Condorcet winner in \(R^{\prime \prime }\).
In case that \(a_2\not \in f(R^\prime )\), agent 3 can manipulate as follows. Suppose \(R\) is the true preference profile. Then, the least favorable alternative of agent 3 is chosen (possibly among other alternatives). He can misstate his preferences as in \(R^\prime \) such that \(a_2\) is not chosen. Since he is indifferent between all other alternatives, \(f(R^\prime ) \mathrel {\widehat{P}_3} f(R)\).
If \(a_2\in f(R^\prime )\), agent 4 can manipulate similarly. Suppose \(R'\) is the true preference profile. Again, the least favorable alternative of agent 4 is chosen. By misstating his preferences as in \(R^{\prime \prime }\), he can assure that one of his preferred alternatives, namely \(a_1\), is selected exclusively because it is the Condorcet winner in \(R^{\prime \prime }\). Hence, \(f(R^{\prime \prime }) \mathrel {\widehat{P}^\prime _4} f(R^\prime )\).\(\square \)