A robust theory of resource allocation

The theory of social choice introduced in [5, 6] is robust: it is completely independent of the choice of topology on spaces of preferences. This theory has been fruitful in linking diverse forms of resource allocation: it has been shown [17] that contractibility is necessary and sufficient for solving the social choice paradox; this condition is equivalent [11] to another — limited arbitrage — which is necessary and sufficient for the existence of a competitive equilibrium and the core of an economy [13, 14, 15, 16, 17]. The space of monotone preferences is contractible; as shown already in [6, 17] such spaces admit social choice rules. However, monotone preferences are of little interest in social choice theory because the essence of the social choice problem, such as Condorcet triples, rules out monotonicity.The author is Director, Program on Information and Resources, and Professor of Economics, Columbia University. 1994-5 Salinbemi Professor, University of Siena, Italy. Research support from NSF grants Nos. 92 16928 and from the Leif Johansen Award at the University of Oslo, Norway, are gratefully acknowledged.     

Nash Implementation with Lottery Mechanisms

Consider the problem of exact Nash Implementation of social choice correspondences. Define a lottery mechanism as a mechanism in which the planner can randomize on alternatives out of equilibrium while pure alternatives are always chosen in equilibrium. When preferences over alternatives are strict, we show that Maskin monotonicity (Maskin in Rev Econ stud 66: 23–38, 1999) is both necessary and sufficient for a social choice correspondence to be Nash implementable. We discuss how to relax the assumption of strict preferences. Next, we examine social choice correspondences with private components. Finally, we apply our method to the issue of voluntary implementation (Jackon and Palfrey in J Econ Theory 98: 1–25, 2001).I thank Toyo Sakai for his comments on a previous draft. I also thank two anonymous referees and an editor of this journal for helpful comments that improved this paper. A previous version circulated as “A note on Maskin monotonicity”. After the results presented here were obtained, I became aware of a new unpublished paper by Benoit and Ok (2004). The result of Theorem 2 and the discussion that follows is partially similar to their Theorem 1.     

Arbitrage and global cones: Another counterexample

Chichilnisky (1997) claims that another variant of her condition limiting arbitrage is necessary and sufficient for existence of equilibrium and nonemptiness of the core in an economy with short sales allowing half lines in indifference surfaces. Her proof, however, is based on a proposition purporting to relate her notion of “global cone” (see Chichilnisky (1997) for references) to the Page-Wooders “increasing cone.” In this paper, we present a counterexample showing that parts (i) and (ii) of Chichilnisky's proposition are false. Thus, Chichilnisky's claimed result is without proof. Received: 18 August 1997/Accepted: 30 January 1998     

Consistency between tastes and values: A universalization approach

The object of this paper is to propose a consistency test for an individual involved in collective choice process. Collective choice processes considered in the paper are those that transform individuals ‘tastes’– which reflect the self-interested view point of the individuals – into (social) ranking of alternatives. In addition to her tastes, an individual has values about the way by which collective decision should be made. We distinguish two categories of such values. First, there are end-values that restrict the class of social rankings that the individual considers ethically acceptable. Second there are aggregation-values that specify the way by which the social ranking should depend upon the individuals tastes. The consistency test stands on an hypothetical operation of universalization of the individual tastes to everyone. Five illustrations of the potential usefulness of our approach for interpreting social choice theory and welfare economics are proposed. These illustrations deal with utilitarian aggregation in the presence of income inequality aversion, the so-called ‘ethics of responsibility’ and the aggregation of individual ranking of opportunity sets based on their freedom of choice. A discussion of the relevance of the consistency test for addressing the problem of ‘laundering’ individual preferences is also provided. Received: 25 June 1998/Accepted: 16 March 1999     

Subgame perfect implementation of stable matchings in marriage problems

We study a sequential matching mechanism, an extensive form game of perfect information, to implement stable matchings in marriage problems. It is shown that the SPE (subgame perfect equilibrium) of this mechanism leads to the unique stable matching when the Eeckhout (Econ Lett 69:1–8, 2000) condition for the existence of a unique stable matching holds. This result does not extend to preferences that violate the Eeckhout condition, even if the matching problem has a unique stable matching. We then introduce a weaker condition, called the α ^M condition, under which the SPE outcome of the men-move-first mechanism is the men-optimal stable matching. The α ^M condition is necessary and sufficient for the men-optimal stable matching to be Pareto optimal for men.     

On the equilibrium of voting games with abstention and several levels of approval

We study the core of “(j, k) simple games”, where voters choose one level of approval from among j possible levels, partitioning the society into j coalitions, and each possible partition facing k levels of approval in the output (Freixas and Zwicker in Soc Choice Welf 21:399–431, 2003). We consider the case of (j, 2) simple games, including voting games in which each voter may cast a “yes” or “no” vote, or abstain (j = 3). A necessary and sufficient condition for the non-emptiness of the core of such games is provided, with an important application to weighted symmetric (j, 2) simple games. These results generalize the literature, and provide a characterization of constitutions under which a society would allow a given number of candidates to compete for leadership without running the risk of political instability. We apply these results to well-known voting systems and social choice institutions including the relative majority rule, the two-thirds relative majority rule, the United States Senate, and the United Nations Security Council.     

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     

Reconsidering two-agent Nash implementation

In this paper, we reconsider the full characterization of two-agent Nash implementation provided in the celebrated papers by Moore and Repullo (Econometrica 58:1083–1099, 1990) and Dutta and Sen (Rev Econ Stud 58:121–128, 1991), since we are able to show that the characterizing conditions are not logically independent. We prove that an amended version of the conditions proposed in these papers is still necessary and sufficient for Nash implementability. Then, by using our necessary and sufficient condition, we show that Maskin’s impossibility result can be avoided under restrictions on the outcomes and the domain of preferences much weaker than those previously imposed by Moore and Repullo (Econometrica 58:1083–1099, 1990) and Dutta and Sen (Rev Econ Stud 58:121–128, 1991).     

Choosing subsets: a size-independent probabilistic model and the quest for a social welfare ordering

“Subset voting” denotes a choice situation where one fixed set of choice alternatives (candidates, products) is offered to a group of decision makers, each of whom is requested to pick a subset containing any number of alternatives. In the context of subset voting we merge three choice paradigms, “approval voting“ from political science, the “weak utility model” from mathematical psychology, and “social welfare orderings” from social choice theory. We use a probabilistic choice model proposed by Falmagne and Regenwetter (1996) built upon the notion that each voter has a personal ranking of the alternatives and chooses a subset at the top of the ranking. Using an extension of Sen's (1966) theorem about value restriction, we provide necessary and sufficient conditions for this empirically testable choice model to yield a social welfare ordering. Furthermore, we develop a method to compute Borda scores and Condorcet winners from subset choice probabilities. The technique is illustrated on an election of the Mathematical Association of America (Brams, 1988). Received: 18 August 1995 / Accepted: 13 February 1997     

Representation of effectivity functions in coalition proof Nash equilibrium: A complete characterization

The concept of coalition proof Nash equilibrium was introduced by Bernheim et al. [5]. In the present paper, we consider the representation problem for coalition proof Nash equilibrium: For a given effectivity function, describing the power structure or the system of rights of coalitions in society, it is investigated whether there is a game form which gives rise to this effectivity function and which is such that for any preference assignment, there is a coalition proof Nash equilibrium.  It is shown that the effectivity functions which can be represented in coalition proof Nash equilibrium are exactly those which satisfy the well-known properties of maximality and superadditivity. As a corollary of the result, we obtain necessary conditions for implementation of a social choice correspondence in coalition proof Nash equilibrium which can be formulated in terms of the associated effectivity function. Received: 24 June 1999/Accepted: 20 September 2000     

An extension of Bowen’s dynamic voting rule to many dimensions

 We ask in this paper about the effect on social decisions of limiting the size of changes that voters may propose each time in an otherwise standard dynamic social choice model. The voting rule we study can be seen as an extension of Bowen’s dynamic “majority voting” rule, and is closely related to the dynamic procedures for public good allocation in the literature (Drèze and de la Vallée Poussin 1971; Malinvaud 1971; Laffont and Maskin 1983; Chander 1993). Under general assumptions we prove existence and Pareto efficiency of equilibrium, and show that our rule motivates voters not to misrepresent preferences (more precisely, the rule is Strongly Locally Individually Incentive Compatible). Under Euclidean preferences we find that electoral cycles do not arise (i.e., the rule is convergent), that there is a unique equilibrium, and that the equilibrium coincides with the solution to an old problem of geometry, first addressed by Fermat, Torricelli, and Cavallieri. Received: 20 September 1994/Accepted: 6 August 1996     

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.     

Games of capacity allocation in many-to-one matching with an aftermarket

In this paper, we study many-to-one matching (hospital–intern markets) with an aftermarket. We first show that every stable matching system is manipulable via aftermarket. We then analyze the Nash equilibria of capacity allocation games, in which preferences of hospitals and interns are common knowledge and every hospital determines a quota for the regular market given its total capacity for the two matching periods. Under the intern-optimal stable matching system, we show that a pure-strategy Nash equilibrium may not exist. Common preferences for hospitals ensure the existence of equilibrium in weakly dominant strategies whereas unlike in games of capacity manipulation strong monotonicity of population is not a sufficient restriction on preferences to avoid the non-existence problem. Besides, in games of capacity allocation, it is not true either that every hospital weakly prefers a mixed-strategy Nash equilibrium to any larger regular market quota profiles.     

Contraction consistent stochastic choice correspondence

We model a general choice environment via probabilistic choice correspondences, with (possibly) incomplete domain and infinite universal set of alternatives. We offer a consistency restriction regarding choice when the feasible set contracts. This condition, ‘contraction consistency’, subsumes earlier notions such as Chernoff’s Condition, Sen’s α and β, and regularity. We identify a restriction on the domain of the stochastic choice correspondence (SCC), under which contraction consistency is equivalent to the weak axiom of revealed preference in its most general form. When the universal set of alternatives is finite, this restriction is also necessary for such equivalence. Analogous domain restrictions are also identified for the special case where choice is deterministic but possibly multi-valued. Results due to Sen (Rev Econ Stud 38:307–317, 1971) and Dasgupta and Pattanaik (Econ Theory 31:35–50, 2007) fall out as corollaries. Thus, conditions are established, under which our notion of consistency, articulated only in reference to contractions of the feasible set, suffices as the axiomatic foundation for a general revealed preference theory of choice behaviour.     

A note on the paradox of smaller coalitions

We consider hedonic coalition formation games that are induced by a simple TU-game and a cooperative solution. For such models, Shenoy’s (Int J Game Theory 8:133–164, 1979) absence of the paradox of smaller coalitions provides a sufficient condition for core existence. We present three different versions of his condition in order to compare it to the top coalition property of Banerjee et al. (Social Choice Welfare 18:135–153, 2001) that guarantees nonemptiness of the core in more general models. As it turns out, the top coalition property implies a condition in which Shenoy’s paradox is not present for at least one minimal winning coalition. Conversely, if for each non-null player Shenoy’s paradox is not present for at least one minimal winning coalition containing that player, then the induced hedonic game satisfies the top coalition property.     

The ordinal egalitarian bargaining solution for finite choice sets

Rubinstein et al. (Econometrica 60:1171–1186, 1992) introduced the Ordinal Nash Bargaining Solution. They prove that Pareto optimality, ordinal invariance, ordinal symmetry, and IIA characterize this solution. A feature of their work is that attention is restricted to a domain of social choice problems with an infinite set of basic allocations. We introduce an alternative approach to solving finite social choice problems using a new notion called the Ordinal Egalitarian (OE) bargaining solution. This suggests the middle ranked allocation (or a lottery over the two middle ranked allocations) of the Pareto set as an outcome. We show that the OE solution is characterized by weak credible optimality, ordinal symmetry and independence of redundant alternatives. We conclude by arguing that what allows us to make progress on this problem is that with finite choice sets, the counting metric is a natural and fully ordinal way to measure gains and losses to agents seeking to solve bargaining problems.     

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.     

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     

On probabilistic rationalizability

This paper examines the problem of rationalizability of a choice system without imposing restrictions on the universal set of alternatives and the family of feasible sets. A choice system is the probabilistic counterpart of a choice function which is basic to much of the theory of individual choice behaviour in economics. We provide a necessary and sufficient condition for a choice system to be induced by a probability measure on a set of utility functions. I would like to thank the editor and two anonymous referees for helpful comments.     

Consequences,opportunities, and Arrovian impossibility theorems with consequentialist domains

We examine the possibility of Arrovian social choice when alternatives consist of outcomes and opportunity sets from which they are chosen. Consequentialism is a choice attitude towards outcomes and opportunities for choice and prioritizes outcomes rather than opportunities for choice. We first propose a sufficient condition for a restricted domain on which Arrow’s impossibility theorem holds. A domain such that there exists a similarity of choice attitudes within consequentialism satisfies the proposed domain condition. We observe that a diversity of choice attitudes within consequentialism is crucial to resolve an Arrovian impossibility, but this resolution is restricted in plausibility.