On strategy-proof social choice correspondences

We introduce two new concepts of strategy-proofness for social choice correspondences based on the theory of preferences over sets of alternatives under complete uncertainty. One is based on Pattanaik and Peleg (Soc Choice Welf 1:113–122, 1984) and the other is based on Bossert et al. (Econ Theory 16:295–312, 2000). We prove that there is no social choice correspondence satisfying anonymity, neutrality, a range condition, and either of our concepts of strategy-proofness. An erratum to this article can be found at     

Coalitionally strategy-proof social choice correspondences and the Pareto rule

This paper studies coalitional strategy-proofness of social choice correspondences that map preference profiles into sets of alternatives. In particular, we focus on the Pareto rule, which associates the set of Pareto optimal alternatives with each preference profile, and examine whether or not there is a necessary connection between coalitional strategy-proofness and Pareto optimality. The definition of coalitional strategy-proofness is given on the basis of a max–min criterion. We show that the Pareto rule is coalitionally strategy-proof in this sense. Moreover, we prove that given an arbitrary social choice correspondence satisfying the coalitional strategy-proofness and nonimposition, all alternatives selected by the correspondence are Pareto optimal. These two results imply that the Pareto rule is the maximal correspondence in the class of coalitionally strategy-proof and nonimposed social choice correspondences.     

On strategy-proof social choice under categorization

I consider social choice problems such that (i) the set of alternatives can be partitioned into categories based on a prominent and objective feature and (ii) agents have strict preferences over the alternatives. Main results are characterizations of the structure of the strategy-proof social choice functions. I prove that each social choice function is strategy-proof if and only if it is decomposable into “small” strategy-proof social choice functions; one of them chooses one category and each of the others chooses one alternative from a category.     

A fundamental structure of strategy-proof social choice correspondences with restricted preferences over alternatives

I prove that under each strategy-proof and unanimous social choice correspondence, there is at least one agent who is decisive. Because the result is established on a weak requirement on preferences over sets, the existence of a decisive agent is an underlying feature of most strategy-proof and unanimous social choice correspondences. Moreover, I consider a restriction on the space of preferences over alternatives. I prove that circular sets of preferences over alternatives are sufficient for the existence of a decisive agent.     

On the manipulation of social choice correspondences

Duggan and Schwartz (Soc Choice and Welfare 17: 85–93, 2000) have proposed a generalization of the Gibbard–Satterthwaite Theorem to multivalued social choice rules. They show that only dictatorial rules are strategy-proof and satisfy citizens sovereignty and residual resoluteness. Citizens sovereignty requires that each alternative is chosen at some preference profile. Residual resoluteness compels the election to be single-valued when the preferences of the voters are “similar”. We propose an alternative proof to the Duggan and Schwartz’s Theorem. Our proof highlights the crucial role of residual resoluteness. In addition, we prove that every strategy-proof and onto social choice correspondence concentrates the social decision power in the hands of an arbitrary group of voters. Finally, we show that this result still holds in a more general framework in which voters report their preferences over sets of alternatives.     

Multi-valued strategy-proof social choice rules

In this paper we introduce a new definition of strategy-proofness for multi-valued social choice correspondences. We prove two Gibbard-Satterthwaite type results for strategy-proof social choice correspondences. These results show that allowing multiple outcomes as social choices will not necessarily lead to an escape from the Gibbard-Satterthwaite impossibility theorem. Received: 24 January 2001/Accepted: 19 March 2001     

Strategy-proof resolute social choice correspondences

We qualify a social choice correspondence as resolute when its set valued outcomes are interpreted as mutually compatible alternatives which are altogether chosen. We refer to such sets as “committees” and analyze the manipulability of resolute social choice correspondences which pick fixed size committees. When the domain of preferences over committees is unrestricted, the Gibbard–Satterthwaite theorem—naturally—applies. We show that in case we wish to “reasonably” relate preferences over committees to preferences over committee members, there is no domain restriction which allows escaping Gibbard–Satterthwaite type of impossibilities. We also consider a more general model where the range of the social choice rule is determined by imposing a lower and an upper bound on the cardinalities of the committees. The results are again of the Gibbard–Satterthwaite taste, though under more restrictive extension axioms.     

Veto in fixed agenda social choice correspondences

In this paper we analyze the relationship between social decision functions (SDF) and fixed agenda social choice correspondences (fixed agenda SCC), satisfying some rationality conditions (such as Pareto, Independence, Monotonicity, Neutrality or Anonimity), with the aim of translating known results on the existence of individuals with veto power into the fixed agenda framework (e.g., Blair and Pollak [2], Blau and Deb [3], …). In order to do this, a new independence condition (which we call Pseudo-Independence), as well as a notion of veto power, are introduced in the context of fixed agenda SCC. The conclusion is that, by fixing the agenda, under Independence and Pareto assumptions, the existence of individuals with veto power cannot be avoided. Received: 6 November 1995 / Accepted: 9 September 1997     

The implementation of social choice functions via social choice correspondences: A general formulation and a limit result

A corollary of Maskin's characterization theorem for Nash implementable social choice correspondences is that only trivial social choice functions can be implemented. This paper explores the consequences of implementing non-trivial social choice functions by extending them minimally to social choice correspondences which are implementable. The concept of asymptotic monotonicity is introduced. The main result states that it is not possible to find social choice rules satisfying a mild condition on its range, which is asymptotically monotonic. The implication of this result is that the multiplicity of equilibria problem which is at the heart of Nash implementation theory persists even in the limit as the number of individuals in society tends to infinity. This is true even though the opportunities for an individual to manipulate the outcome disappears in the limit.This paper is an extensively revised version of a chapter of my Ph.D. dissertation submitted to Princeton University in June 1987. I wish to thank my advisor Hugo Sonnenschein for his valuable advice and constant encouragement. I am also grateful to Andrew Caplin, Vijay Krishna, William Thomson, Jean-Luc Vila and two anonymous referees of this journal for their numerous suggestions. All remaining errors are my own responsibility.     

Strongly implementable social choice correspondences and the supernucleus

In this paper, we present a characterization of social choice correspondences which can be implemented in strong Nash equilibrium, stated in terms of the power structure implicit in the social choice rule. We extend the notion of an effectivity function to allow for simultaneous vetoing by several coalitions. This leads to the concept of a domination structure as a generalized effectivity function.  Using this concept and a solution known from the theory of effectivity functions, the supernucleus, we give a characterization of strongly implementable social choice correspondences as supernucleus correspondence relative to an appropriate domination structure. Received: 2 February 1996/Accepted: 2 February 1998     

Game forms for Nash implementation of general social choice correspondences

Several game forms are given for Nash implementing general social choice correspondences (SCC's) which satisfy Maskin's conditions of monotonicity and No Veto Power. The game forms have smaller strategy spaces than those used in previously studied mechanisms: the strategy for an individual consists of an alternative, two subsets (of alternatives), and a player number. For certain types of economic and political SCC's, including -majority rule, the Walrasian, and Lindahl correspondence, the strategy space reduces to an alternative and a vector, where the number of components of the vector is at most twice the dimension of the alternative space.This paper was inspired by Tatsuyoshi Saijo's dissertation. I am greatly indebted to Kim Border, Leo Hurwicz, and Tatsuyoshi Saijo for some very helpful discussions. I acknowledge support of NSF grant No. SES 8208184.     

A characterization of strategy-proof social choice functions for economies with pure public goods

We characterize strategy-proof social choice functions when individuals have strictly quasi-concave, continuous and satiated utility functions on convex subsets of IR ^m , representing preferences for the provision of m pure public goods. When specialized to the case m=1, these assumptions amount to requiring that preferences are single peaked, and for such a domain there exists a wide class of strategy-proof social choice functions. These were studied by Moulin (1980) under strong additional assumptions. Our first results characterize the complete class, after an appropriate extension of the single-peakedness condition. The new characterization retains the flavour of Moulin's elegant representation theorem. For the general m-dimensional case, previous results have shown that there is no efficient, strategy-proof, nondictatorial social choice function, even within the domain restrictions under consideration (Border and Jordan 1983; Zhou 1991). In fact, Zhou's powerful result indicates that nondictatorial strategy-proof s.c.f.'s will have a range of dimension one. This allows us to conclude with a complete characterization of all strategy-proof s.c.f.'s on IR ^m , because restrictions of preferences from our admissible class to one dimensional subsets satisfy the slightly generalized notion of single-peakedness that is used in our characterization for the case m=1. We feel that a complete knowledge of the class of strategy-proof mechanisms, in this as well as in other contexts, is an important step in the analysis of the trade-offs between strategy-proofness and other performance criteria, like efficiency.This paper was written while both authors were visiting GREMAQ, Université des Sciences Sociales de Toulouse. We are thankful for its hospitality and good research atmosphere. Barberà's work is supported by the Instituto de Estudios Fiscales and by research grant PB89-0294 from the Secretaría de Estado de Universidades e Investigación, Spain. Jackson acknowledges the support of NSF grant SES8921409. We thank Jacques Crémer, Beth Allen, John Weymark and two anonymous referees for helpful comments on earlier drafts.     

Comparison functions and choice correspondences

In this paper, we introduce the concept of a comparison function, which is a mapping g that assigns numbers to ordered pairs of alternatives (x,y) with the property that g(x,y)=−g(y,x). The paper discusses how some well-known choice correspondences on tournaments such as the uncovered set, the minimal covering set and the bipartisan set can be extended to this general framework. Axiomatic characterizations and properties are studied for these correspondences. Received: 4 November 1996/Accepted: 13 April 1998     

Condorcet choice correspondences for weak tournaments

Tournaments are complete and asymmetric binary relations. This type of binary relation rules out the possibility of ties or indifferences which are quite common in other contexts. In this work we generalize, from a normative point of view, some important tournament solutions to the context in which ties are possible. Received: 12 November 1996/Accepted: 4 November 1997     

On the informational basis of social choice

The notion of informational basis in social choice can be broadened so as to cover not only the standard notions related to interpersonal utility comparisons, but also information about utilities or preferences at (ir)relevant alternatives, non-utility features of alternatives, personal responsibility, unconcerned subpopulations, and feasibility constraints. This paper proposes a unified conceptual framework for all these notions, and analyzes the kind of information retained in each case. This new framework yields a deeper understanding of the difficulties and possibilities of social choice. New welfarism theorems are also obtained.I am indebted to W. Bossert, W. Gaertner, F. Gaspart, L. Gevers, N. Gravel, S. Kolm, M. Le Breton, Ph. Mongin, P. Hammond, K. Suzumura, K. Tadenuma, A. Trannoy and J. Weymark for many conversations on topics related to this paper. I have benefited from reactions of the audience at the conference in honor of Louis Gevers, Namur 1999, and at a seminar at the LSE, and from comments by two referees and the editor, F. Maniquet. None of them is responsible for the shortcomings of the paper.