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     

On strategy-proofness and essentially single-valued cores: A converse result

In a general model of indivisible good allocation, S?nmez (1999) established that, whenever the core is nonempty for each preference profile, if an allocation rule is strategy-proof, individually rational and Pareto optimal, then the rule is a selection from the core correspondence, and the core correspondence must be essentially single-valued. This paper studies the converse claim of this result. I demonstrate that whenever the preference domain satisfies a certain condition of `richness', if the core correspondence is essentially single-valued, then any selection from the core correspondence is strategy-proof (even weakly coalition strategy-proof, in fact). In particular, on the domain of preferences in which each individual has strict preferences over his own assignments and there is no consumption externality, such an allocation rule is coalition strategy-proof. And on this domain, coalition strategy-proofness is equivalent to Maskin monotonicity, an important property in implementation theory. Received: 22 February 2000/Accepted: 22 January 2002 I am grateful to Ryo-ichi Nagahisa, Shinji Ohseto, Hiroshi Ono, Tomoichi Shinotsuka and Shigehiro Serizawa for valuable comments. And I am indebted to two anonymous referees for useful suggestions. Especially, I owe the present proof of Lemma 2 to one referee. I also thank Yukihiko Funaki, Atsushi Kajii, Mamoru Kaneko, Eiichi Miyagawa, Tatsuyoshi Saijo, Manimay Sengupta, Yves Sprumont, Yoshikatsu Tatamitani, Manabu Toda, Takashi Ui, Takehiko Yamato, Naoki Yoshihara and the participants of the seminars in Hokkaido University, Kansai University, ISER (Osaka University), Otaru University of Commerce and Tsukuba University. All errors are my own responsiblity.     

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

Generalized condorcet-winners for single peaked and single-plateau preferences

When preferences are single peaked the choice functions that are independent of irrelevant alternatives both in Nash's and in Arrow's sense are characterized. They take the Condorcet winner of the n individual peaks plus at most n-1 fixed ballots (phantom voters). These choice functions are also coalitionally strategy-proof.Next the domain of individual preferences is enlarged to allow for singleplateau preferences: again, Nash's IIA and Arrow's IIA uniquely characterize a class of generalized Condorcet winners choice functions. These are, again, coalitionally strategy-proof.     

Strategy-proofness and markets

If a market is considered to be a social choice function, then the domain of admissible preferences is restricted and standard social choice theorems do not apply. A substantial body of analysis, however, strongly supports the notion that attractive strategy-proof social choice functions do not exist in market settings. Yet price theory, which implicitly assumes the strategy-proofness of markets, performs quite well in describing many real markets. This paper resolves this paradox in two steps. First, given that a market is not strategy-proof, it should be modeled as a Bayesian game of incomplete information. Second, a double auction market, which is perhaps the simplest operationalization of supply and demand as a Bayesian game, is approximately strategy-proof even when the number of traders on each side of the market is quite moderate. Received: 24 March 1999/Accepted: 25 October 1999     

Distribution of coalitional power in randomized multi-valued social choice

This paper considers the distribution of coalitional influence under probabilistic social choice functions which are randomized social choice rules that allow social indifference by mapping each combination of a preference profile and a feasible set to a social choice lottery over all possible choice sets from the feasible set. When there are at least four alternatives in the universal set and ex-post Pareto optimality, independence of irrelevant alternatives and regularity are imposed, we show that: (i) there is a system of additive coalitional weights such that the weight of each coalition is its power to be decisive in every two-alternative feasble set; and (ii) for each combination of a feasible proper subset of the universal set and a preference profile, the society can be partioned in such a way that for each coalition in this partition, the probability of society's choice set being contained in the union of the best sets of its members is equal to the coalition's power or weight. It is further shown that, for feasible proper subsets of the universal set, the probability of society's choice set containing a pair of alternatives that are not jointly present in anyone's best set is zero. Our results remain valid even when the universal set itself becomes feasible provided some additional conditions hold. Received: 10 May 1999/Accepted: 18 June 2000 I would like to thank Professor Prasanta Pattanaik for suggesting to me the line of investigation carried out in this paper. I am solely responsible for any remaining errors and omissions.     

Partially efficient voting by committees

On the separable preference domain, voting by committees is the only class of voting rules that satisfy strategy-proofness and unanimity, and dictatorial rules are the only ones that are strategy-proof and Pareto efficient. To fill the gap, we define a sequence of efficiency conditions. We prove that for strategy-proof rules on the separable preference domain, the various notions of efficiency reduce to three: unanimity, partial efficiency, and Pareto efficiency. We also show that on the domain, strategy-proofness and partial efficiency characterize the class of voting rules represented as simple games which are independent of objects, proper and strong. We call such rules voting by stable committee.The author is deeply indebted to William Thomson for many helpful discussions on an earlier draft. The current version is greatly benefited from detailed comments of an anonymous referee. Thanks are also due to Jeffrey Banks, Salvador Barberà, Marcus Berliant, Ryo-ichi Nagahisa, Takehiko Yamato, and participants in a seminar at Rochester in 1992, the 1992 Midwest Conference at Michigan State, and the 1993 Summer Meeting of Econometric Society at Boston University for conversations and suggestions.     

Single-Crossing, Strategic Voting and the Median Choice Rule

This paper studies the strategic foundation of the Representative Voter Theorem (Rothstein in: Pub Choice 72:193–212, 1991), also called the “second version” of the Median Voter Theorem. As a by-product, it also considers the existence of strategy-proof social choice functions over the domain of single-crossing preferences. The main result shows that single-crossing constitutes a domain restriction over the real line that allows not only majority voting equilibria, but also non-manipulable choice rules. In particular, this is true for the median rule, which is found to be group strategic-proof over the full set of alternatives and over every nonempty subset. In addition, the paper also examines the relation between single-crossing and order-restriction. And it uses this relation together with the strategy-proofness of the median rule to prove that the outcome predicted by the Representative Voter Theorem can be implemented in dominant strategies through a simple mechanism. This mechanism is a two-stage voting procedure in which, first, individuals select a representative among themselves, and then the winner chooses a policy to be implemented by the planner.     

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.     

Pairwise Strategy-Proofness and Self-Enforcing Manipulation

“Strategy-proofness” is one of the axioms that are most frequently used in the recent literature on social choice theory. It requires that by misrepresenting his preferences, no agent can manipulate the outcome of the social choice rule in his favor. The stronger requirement of “group strategy-proofness” is also often employed to obtain clear characterization results of social choice rules. Group strategy-proofness requires that no group of agents can manipulate the outcome in their favors. In this paper, we advocate “effective pairwise strategy-proofness.” It is the requirement that the social choice rule should be immune to unilateral manipulation and “self-enforcing” pairwise manipulation in the sense that no agent of a pair has the incentive to betray his partner. We apply the axiom of effective pairwise strategy-proofness to three types of economies: public good economy, pure exchange economy, and allotment economy. Although effective pairwise strategy-proofness is seemingly a much weaker axiom than group strategy-proofness, effective pairwise strategy-proofness characterizes social choice rules that are analyzed by using different axioms in the literature.     

Generalized median social welfare functions

The article considers the construction of social welfare functions when the set of alternatives is the two-dimensional nonnegative orthant, as would be the case if there are two divisible public goods which can be consumed in any nonnegative quantities. With individual and social preferences required to be linear and strictly monotonic, but otherwise unrestricted, we characterize all of the social welfare functions which satisfy binary independence of irrelevant alternatives and anonymity and which satisfy binary independence of irrelevant alternatives, anonymity, and weak Pareto. These classes of social welfare functions are shown to be formally equivalent to the classes of social choice functions characterized by Moulin in his study of strategy-proof social choice with single-peaked preferences.We are grateful to Charles Blackorby, Hervé Moulin, and an anonymous referee for their comments.     

Minimal manipulability: anonymity and unanimity

This paper is concerned with the minimal number of profiles at which a unanimous and anonymous social choice function for three alternatives is manipulable. The lower bound is derived and examples of social choice functions attaining the lower bound are given. It is conjectured that these social choice functions are in fact all minimally manipulable social choice functions. Since some of these social choice functions are Pareto optimal, it follows that the lower bound also holds for Pareto optimal and anonymous social choice functions. Some of the minimally manipulable Pareto optimal and anonymous social choice functions can be interpreted as status quo voting.     

Nash implementation via hyperfunctions

Hyperfunctions are social choice rules which assign sets of alternatives to preference profiles over sets. Therefore, they are more general objects compared to standard (social choice) correspondences. In fact, every correspondence can be expressed in terms of an equivalent hyperfunction. We give a partial characterization of Nash-implementable hyperfunctions and explore the conditions under which correspondences have Nash-implementable equivalent hyperfunctions. While the strength of these conditions depends on the axioms used to extend preferences over alternatives to sets, they are at most as strong as the conjunction of Maskin monotonicity with the no veto power condition. Thus, our approach expands the set of Nash-implementable social choice rules. In fact, social choice rules such as the majority rule and the top cycle are Nash-implementable through their equivalent hyperfunctions, while they are not Maskin-monotonic, and thus, not Nash-implementable in the standard framework.

---

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.     

A necessary and sufficient condition for stable matching rules to be strategy-proof

We study one-to-one matching problems and analyze conditions on preference domains that admit the existence of stable and strategy-proof rules. In this context, when a preference domain is unrestricted, it is known that no stable rule is strategy-proof. We introduce the notion of the no-detour condition, and show that under this condition, there is a stable and group strategy-proof rule. In addition, we show that when the men’s preference domain is unrestricted, the no-detour condition is also a necessary condition for the existence of stable and strategy-proof rules. As a result, under the assumption that the men’s preference domain is unrestricted, the following three statements are equivalent: (i) a preference domain satisfies the no-detour condition, (ii) there is a stable and group strategy-proof rule, (iii) there is a stable and strategy-proof rule.     

Characterization of social choice sets in terms of individuals' maximal sets: The fixed agenda framework

In this paper we analyze the explicit representation of fixed agenda social choice correspondences under different rationality assumptions (independence, Pareto optimality, etc.). It is well known that, under some of these assumptions, the existence of dictators, oligarchies or individuals with veto power can be proven ([6] and [10]); but only a partial characterization of the social choice set is obtained. We establish a relationship between the social choice set and the individuals' maximal sets, which explicitly describes a fixed agenda social choice correspondence that satisfies these rationality assumptions. Received: 30 December 1997/Accepted: 20 December 1999     

Monotonicity implies generalized strategy-proofness for correspondences

We show that Maskin monotone social choice correspondences on sufficiently rich domains satisfy a generalized strategy-proofness property, thus generalizing Muller and Satterthwaite’s (1977) theorem to correspondences. The result is interpreted as a possibility theorem on the dominant-strategy implementability of monotone SCCs via set-valued mechanisms for agents who are completely ignorant about the finally selected outcome. Alternatively, the result yields a partial characterization of the restrictions entailed by Nash implementability of correspondences. Received: 3 November 1997/Accepted: 26 April 1999     

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