A geometric proof of Gibbard's random dictatorship theorem

Summary Gibbard has shown that a social choice function is strategy-proof if and only if it is a convex combination of dictatorships and pair-wise social choice functions. I use geometric techniques to prove the corollary that every strategy-proof and sovereign social choice function is a random dictatorship.I thank Kim Border for several useful discussions and many insightful comments.     

Dictatorial domains

Summary. In this paper, we introduce the notion of a linked domain and prove that a non-manipulable social choice function defined on such a domain must be dictatorial. This result not only generalizes the Gibbard-Satterthwaite Theorem but also demonstrates that the equivalence between dictatorship and non-manipulability is far more robust than suggested by that theorem. We provide an application of this result in a particular model of voting. We also provide a necessary condition for a domain to be dictatorial and use it to characterize dictatorial domains in the cases where the number of alternatives is three. Received: July 12, 2000; revised version: March 21, 2002 RID="*" ID="*" The authors would like to thank two anonymous referees for their detailed comments. Correspondence to: A. Sen     

The strategy-proof provision of public goods under congestion and crowding preferences

We examine the strategy-proof provision of excludable public goods when agents care about the number of other consumers. We show that strategy-proof and efficient social choice functions satisfying an outsider independence condition must always assign a fixed number of consumers, regardless of individual desires to participate. A hierarchical rule selects participants and a generalized median rule selects the level of the public good. Under heterogeneity in agents’ views on the optimal number of consumers, strategy-proof, efficient, and outsider independent social choice functions are much more limited and in an important case must be dictatorial.     

An extreme point characterization of random strategy-proof social choice functions: The two alternative case

We show that every strategy-proof random social choice function is a convex combination of strategy-proof deterministic social choice functions in a two-alternative voting model. This completely characterizes all strategy-proof random social choice functions in this setting.     

Extraneous Alternatives And Strategy-Proofness

It is well known that the Gibbard–Satterthwaite theorem cannot be circumvented by adding extraneous alternatives that are included in the individual preference information but are never selected. We generalize this by proving that, for any domain on which every strategy-proof rule is dictatorial, the addition of extraneous alternatives will not permit the construction of a non-dictatorial and strategy-proof rule if the new domain is a product set. We show how this result, and our other theorem, can be applied to seven families of social choice situations, including those in which more than one alternative is selected.     

A Democracy Principle and Strategy-Proofness

In some social choice applications we want more than one alternative to be selected in some situations. This allows the construction of strategy-proof social choice rules that are not dictatorial. But if we also require x alone to be selected if it is at the top of some ordering that is submitted by more than half of the individuals then the rule cannot be strategy-proof. We prove this for rules that sometimes select one alternative, and sometimes two, but never more than two.     

Preference revelation with a limited number of indifference classes

Suppose that g is a strategy-proof social choice rule on the domain of all profiles of complete and transitive binary relations that have exactly m indifference classes. If and the range of g has three or more members, then g is dictatorial. If m = 2, then for any set X of feasible alternatives, there exist non-dictatorial and strategy-proof rules that are sensitive to the preferences of every individual and which have X as range.     

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 allocation mechanisms for pure public goods economies when preferences are monotonic

Summary. A fundamental problem in public finance is that of allocating a␣given budget to financing the provision of public goods (education, transportation, police, etc.). In this paper it is established that when␣admissible preferences are those representable by continuous and increasing utility functions, then strategy-proof allocation mechanisms whose (undominated) range contains three or more outcomes are dictatorial on the set of profiles of strictly increasing utility functions, a dense subset of the domain in the topologies commonly used in this context. If admissible utility functions are further restricted to be strictly increasing, or if mechanisms are required to be non-wasteful, then strategy-profness leads to (full) dictatorship. Received: August 14, 1995; revised version: September 25, 1997     

On strategy-proofness and symmetric single-peakedness

We characterize the class of strategy-proof social choice functions on the domain of symmetric single-peaked preferences. This class is strictly larger than the set of generalized median voter schemes (the class of strategy-proof and tops-only social choice functions on the domain of single-peaked preferences characterized by Moulin, 1980) since, under the domain of symmetric single-peaked preferences, generalized median voter schemes can be disturbed by discontinuity points and remain strategy-proof on the smaller domain. Our result identifies the specific nature of these discontinuities which allow to design non-onto social choice functions to deal with feasibility constraints.     

Strategy-proof allocation mechanisms for economies with public goods

We show that strategy-proof allocation mechanisms for economies with public goods are dictatorial—i.e., they always select an allocation in their range that maximizes the welfare of the same single individual (the dictator). Further, strategy-proof and efficient allocation mechanisms are strongly dictatorial—i.e., they select the dictator’s preferred allocation on the entire feasible set. Thus, our results reveal the extent to which the conflict between individual incentives and other properties that may be deemed desirable (e.g., fairness, equal treatment, distributive justice) pervades resource allocation problems.     

Decomposable Strategy-Proof Social Choice Functions

This article shows that a social choice function defined on a domain of separable preferences which satisfies a relatively weak domain-richness condition on a product set of alternatives is (i) strategy-proof and only depends on the tops of the individual preferences if and only if (ii) the range of the social choice function is a product set and the social choice function can be decomposed into the product of one-dimensional, strategy-proof, nontop-insensitive social choice functions.
JEL Classification Number: D71.     

Individual versus group strategy-proofness: When do they coincide?

A social choice function is group strategy-proof on a domain if no group of agents can manipulate its final outcome to their own benefit by declaring false preferences on that domain. There are a number of economically significant domains where interesting rules satisfying individual strategy-proofness can be defined, and for some of them, all these rules turn out to also satisfy the stronger requirement of group strategy-proofness. We provide conditions on domains guaranteeing that for all rules defined on them, individual and group strategy-proofness become equivalent. We also provide a partial answer regarding the necessity of our conditions.     

The computational complexity of random serial dictatorship

In social choice settings with linear preferences, random dictatorship is known to be the only social decision scheme satisfying strategyproofness and ex post efficiency. When also allowing indifferences, random serial dictatorship (RSD) is a well-known generalization of random dictatorship that retains both properties. RSD has been particularly successful in the special domain of random assignment where indifferences are unavoidable. While executing RSD is obviously feasible, we show that computing the resulting probabilities is #P-complete, and thus intractable, both in the context of voting and assignment.     

A dictatorial domain for monotone social choice functions

We give a dictatorial domain for monotone and unanimous social choice functions.     

Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions

Consider a committee which must select one alternative from a set of three or more alternatives. Committee members each cast a ballot which the voting procedure counts. The voting procedure is strategy-proof if it always induces every committee member to cast a ballot revealing his preference. I prove three theorems. First, every strategy-proof voting procedure is dictatorial. Second, this paper's strategy-proofness condition for voting procedures corresponds to Arrow's rationality, independence of irrelevant alternatives, non-negative response, and citizens' sovereignty conditions for social welfare functions. Third, Arrow's general possibility theorem is proven in a new manner.     

A strategy-proofness characterization of majority rule

Summary. A feasible alternative x is a strong Condorcet winner if for every other feasible alternative y there is some majority coalition that prefers x to y. Let (resp., denote the set of all profiles of linear (resp., merely asymmetric) individual preference relations for which a strong Condorcet winner exists. Majority rule is the only non-dictatorial and strategy-proof social choice rule with domain , and majority rule is the only strategy-proof rule with domain . Received: August 29, 2000; revised version: November 13, 2002 RID="*" ID="*"We are grateful to Wulf Gaertner and our two referees for insightful comments on a previous draft. Correspondence to: D. E. Campbell     

Impossibility Theorems with Interpersonally Comparable Welfare Levels: The "Extended Sympathy Approach" Reconsidered

We re-examine a type of interpersonal welfare comparison, called the "extended sympathy" approach, which Arrow (1977), Hammond (1976) and Roberts (1980a) introduced in order to escape from Arrovian impossibility theorems. In particular, we extend the positional dictatorship theorem due to Roberts to the case where the domain of social choice rules satisfies the axiom of identity. We show that there is a positional dictator if the rule with the domain satisfies independence, Suppes unanimity and monotonicity
JEL Classification Numbers: 022, 025, 026     

A unifying impossibility theorem

This paper identifies and illuminates a common impossibility principle underlying a number of impossibility theorems in social choice. We consider social choice correspondences assigning a choice set to each non-empty subset of social alternatives. Three simple axioms are imposed as follows: unanimity, independence of preferences over infeasible alternatives, and choice consistency with respect to choices out of all possible alternatives. With more than three social alternatives and the universal preference domain, any social choice correspondence that satisfies our axioms is serially dictatorial. A number of known impossibility theorems—including Arrow’s Impossibility Theorem, the Muller–Satterthwaite Theorem, and the impossibility theorem under strategic candidacy—follow as corollaries.     

How competition affects schools' performances: Does specification matter?

If the number of individuals is odd, majority rule is the only non-dictatorial strategy-proof social choice rule on the domain of linear orders that admit a Condorcet winner (Campbell and Kelly, 2003). This paper shows that the claim is false when the number of individuals is even, and provides a counterpart to the theorem for the even case.