The structure of strategy-proof social choice — Part I: General characterization and possibility results on median spaces

We define a general notion of single-peaked preferences based on abstract betweenness relations. Special cases are the classical example of single-peaked preferences on a line, the separable preferences on the hypercube, the “multi-dimensionally single-peaked” preferences on the product of lines, but also the unrestricted preference domain. Generalizing and unifying the existing literature, we show that a social choice function is strategy-proof on a sufficiently rich domain of generalized single-peaked preferences if and only if it takes the form of voting by issues (“voting by committees”) satisfying a simple condition called the “Intersection Property.”Based on the Intersection Property, we show that the class of preference domains associated with “median spaces” gives rise to the strongest possibility results; in particular, we show that the existence of strategy-proof social choice rules that are non-dictatorial and neutral requires an underlying median space. A space is a median space if, for every triple of elements, there is a fourth element that is between each pair of the triple; numerous examples are given (some well-known, some novel), and the structure of median spaces and the associated preference domains is analysed.     

Strategy-proof and individually rational social choice functions for public good economies

Summary This note is to inform about a mistake in my paper (Serizawa, 1996). In that paper, I characterized strategy-proof, individually rational, budget-balancing, non-exploitative and non-bossy social choice functions for economies with one public good and one private good. I established as Theorem 3 (page 507) that a social choice function is strategy-proof, individually rational with respect to endowment, budget-balancing, non-exploitative and non-bossy if and only if it is a scheme of semi-convex cost sharing determined by the minimum demand principle. I also exposed one example (Example 2, page 507) in order to emphasize that non-bossiness is indispensable for this characterization. I claimed that the social choice function in that example satisfies the above axioms except for non-bossiness, and is not a scheme of semi-convex cost sharing. However, the social choice function in the example is actually not strategy-proof, as shown in the simple discussion below. Therefore it is an open question whether or not a similar characterization theorem holds without non-bossiness.I thank Professor Rajat Deb, who kindly pointed out my mistake.     

The communication requirements of social choice rules and supporting budget sets

The paper examines the communication requirements of social choice rules when the (sincere) agents privately know their preferences. It shows that for a large class of choice rules, any minimally informative way to verify that a given alternative is in the choice rule is by verifying a “budget equilibrium”, i.e., that the alternative is optimal to each agent within a “budget set” given to him. Therefore, any communication mechanism realizing the choice rule must find a supporting budget equilibrium. We characterize the class of choice rules that have this property. Furthermore, for any rule from the class, we characterize the minimally informative messages (budget equilibria) verifying it. This characterization is used to identify the amount of communication needed to realize a choice rule, measured with the number of transmitted bits or real variables. Applications include efficiency in convex economies, exact or approximate surplus maximization in combinatorial auctions, the core in indivisible-good economies, and stable many-to-one matchings.     

A leximin characterization of strategy-proof and non-resolute social choice procedures

Summary. We characterize strategy-proof social choice procedures when choice sets need not be singletons. Sets are compared by leximin. For a strategy-proof rule g, there is a positive integer k such that either (i) the choice sets g(r) for all profiles r have the same cardinality k and there is an individual i such that g(r) is the set of alternatives that are the k highest ranking in i's preference ordering, or (ii) all sets of cardinality 1 to k are chosen and there is a coalition L of cardinality k such that g(r) is the union of the tops for the individuals in L. There do not exist any strategy-proof rules such that the choice sets are all of cardinality to k where . Received: November 8, 1999; revised version: September 18, 2001     

Implementation of individually rational social choice functions with guaranteed utilities

A simple mechanism is presented that allocates an indivisible object between two agents for almost any possible compensation rule. Furthermore, the equilibrium strategy guarantees a level of utility not less than −ε, where ε can be arbitrarily small.     

Perfect competition in asymmetric information economies: compatibility of efficiency and incentives

The idea of perfect competition for an economy with asymmetric information is formalized via an idiosyncratic signal process in which the private signals of almost every individual agent can influence only a negligible group of agents, and the individual agents’ relevant signals are essentially pairwise independent conditioned on the true states of nature. Thus, there is no incentive for an individual agent to manipulate her private information. The existence of incentive compatible, ex post Walrasian allocations is shown for such a perfectly competitive asymmetric information economy with or without “common values”. Consequently, the conflict between incentive compatibility and Pareto efficiency is resolved exactly, and its asymptotic version is derived for a sequence of large, but finite private information economies.     

The strategy of manipulating joint decision-making

We study a model of strategic persuasion based on the theory of cheap talk, in which a better-informed agent manipulates two decision-makers’ joint decision on alternative proposals. With the heterogeneity of two decision-makers’ value of the outside option, only the decision-maker with the better outside option is critical in determining whether communication is truthful, overselling, or ineffective.     

Subgame perfect implementation: A full characterization

Moore and Repullo [Subgame perfect implementation, Econometrica 56 (1988) 1191-1220], and Abreu and Sen [Subgame perfect implementation: a necessary and almost sufficient condition, J. Econ. Theory 50 (1990) 285-299] introduce distinct necessary and sufficient conditions for SPE implementation, when the number of players is at least three. This paper closes the gap between the conditions—a complete characterization of the SPE implementable choice rules is provided. The characterization consists of α^*, which strengthens α of Abreu-Sen by adding it a restricted veto-power condition, and the unanimity condition. Under strict preferences α^* is equal to α.     

Von Neumann-Morgenstern solution social choice functions: An impossibility theorem

Recent literature has made significant progress in characterizing those social choice functions that can arise, or be “implemented,” as the equilibria of an underlying noncooperative game. This paper studies the implementability of social choice functions via cooperative games. Specifically, we show that if a social choice function arises, in each environment, as a Von Neumann-Morgenstern solution of an underlying cooperative game, whose dominance structure is monotonic and neutral, then the social choice function is essentially oligarchic, in exactly the same sense that “core” selecting choice functions are oligarchic.     

Detail-free mechanism design in twice iterative dominance: Large economies

This paper investigates unique implementation in large economies with incomplete information and interdependent values; we degenerate the common knowledge assumptions and assume that a central planner is unaware of the specifications of an environment. With a minor restriction on the class of environments, we demonstrate that there exists a detail-free mechanism that virtually implements competitive allocations with complete information in twice iterative dominance, irrespective of how the environment is specified.     

A note on the incompatibility of strategy-proofness and Pareto-optimality in quasi-linear settings with public budgets

We show that any deterministic mechanism, for allocating identical items that are complements to budget-constrained bidders, cannot simultaneously satisfy individual-rationality, strategy-proofness, Pareto-efficiency, and no-positive-transfers. This holds even for two bidders, two items, and commonly-known budgets, and generalizes to richer settings.     

An experimental study on individual choice, social welfare, and social preferences

We experimentally study subjects’ compliance with dominance relationships of income distributions in a ranking task. The experiment consisted of four different treatments: Lottery, individual choice, social preferences, and social planner. Our results suggest that people's risk attitudes do not adequately reflect their inequality attitudes. Uninvolved social planners exhibit randomization preferences, while self-interested social planners are generally more inequality averse and try to avoid extreme outcomes.     

Persuasion,binary choice,and the costs of dishonesty

We study the strategic interaction between a decision maker who needs to take a binary decision but is uncertain about relevant facts and an informed expert who can send a message to the decision maker but has a preference over the decision. We show that the probability that the expert can persuade the decision maker to take the expert’s preferred decision is a hump-shaped function of his costs of sending dishonest messages.     

Stochastic mechanisms in settings without monetary transfers: The regular case

We analyze relative performance of stochastic and deterministic mechanisms in an environment that has been extensively studied in the literature on communication (e.g., [Vincent P. Crawford, Joel Sobel, Strategic information transmission, Econometrica 50 (6) (1982) 1431-1451]) and optimal delegation (e.g., [Bengt Holmström, On the theory of delegation, in: M. Boyer, R.E. Kihlstrom (Eds.), Bayesian Models in Economic Theory, North-Holland, 1984, pp. 115-141]): a principal-agent model with hidden information, no monetary transfers, and single-peaked preferences. We demonstrate that under the common assumption of quadratic payoffs and a certain regularity condition on the distribution of private information and the agent's bias, the optimal mechanism is deterministic. We also provide an explicit characterization of this mechanism.     

Role of linking mechanisms in multitask agency with hidden information

We investigate the adverse selection problem where a principal delegates multiple tasks to an agent. We characterize the virtually implementable social choice functions by using the linking mechanism proposed by Jackson and Sonnenschein (2007) [20] that restricts the message spaces. The principal does not require any incentive wage schemes and can therefore avoid any information rent and welfare loss. We show the resemblance between the functioning of this message space restriction and that of incentive wage schemes. We also extend the results of the single-agent model to the multi-agent model.     

Learnability and rationality of choice

In this paper we study the learnability of the class of rationalizable choice functions using the basic concept of PAC-learnability from statistical learning theory. We prove that the class of rationalizable choice functions on N alternatives is learnable from O(N) examples and is optimal in terms of PAC-learnability among classes which are invariant under permutations of the elements.     

Corrigendum to “School choice: An experimental study” [J. Econ. Theory 127 (1) (2006) 202-231]

We correct an inconsistency in the efficiency comparison reported in [Y. Chen, T. Sönmez, School choice: An experimental study, J. Econ. Theory 127 (1) (2006) 202-231]. The efficiency comparison of the three school choice mechanisms in our paper is based on recombinant estimation with an identical set of 10 tie-breakers, while the statistics reported in Table 7 is computed using 14,400 tie-breakers.     

Serial cost sharing of excludable public goods: general cost functions

Summary. A group of individuals meet to share the cost and determine output allocations of a partial-excludable public good. We demonstrate that, for general cost functions and preferences that satisfy the Spence-Mirlees sorting condition, the serial cost-sharing formula (Moulin, 1994) has remarkable incentive properties. First, a direct economic mechanism that uses the serial formula is coalition strategy-proof, envy-free and satisfies the stand-alone property. Second, the serial mechanism involves partial exclusion, which is important for the reduction of the free-rider problem. Received: June 10, 1996; revised version; February 11, 1997     

An efficiency characterization of plurality social choice on simple preference domains

Summary. We consider a model of social choice dealing with the problem of choosing a subset from a set of objects (e.g. candidate selection, membership, and qualification problems). Agents have trichotomous preferences for which objects are partitioned into three indifference classes, goods, bads, and nulls, or dichotomous preferences for which each object is either a good or a bad. We characterize plurality-like social choice rules on the basis of the three main axioms, known as Pareto efficiency, anonymity, and independence.Received: 29 August 2003, Revised: 3 June 2004, JEL Classification Numbers: D70, D71, D72.Biung-Ghi Ju: I am grateful to William Thomson and Jianbo Zhang for their helpful comments and discussions. I also thank Brandon Dupont, the participants in seminars at Iowa State University, University of Kansas, and the Midwest Theory Meeting at University of Notre Dame. I thank an anonymous referee for detailed comments and suggestions that were very helpful in simplifying the proof of Theorem 1 and in revising the paper.