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.     

Top-Pair and Top-Triple Monotonicity

We say that a social choice function (SCF) satisfies Top-k Monotonicity if the following holds. Suppose the outcome of the SCF at a preference profile is one of the top k-ranked alternatives for voter i. Let the set of these k alternatives be denoted by B. Suppose that i’s preference ordering changes in such a way that the set of first k-ranked alternatives remains the set B. Then the outcome at the new profile must belong to B. This definition of monotonicity arises naturally from considerations of set “improvements” and is weaker than the axioms of strong positive association and Maskin Monotonicity. Our main results are that if there are two voters then a SCF satisfies unanimity and Top-2 or Top-pair Monotonicity if and only if it is dictatorial. If there are more than two voters, then Top-pair Monotonicity must be replaced by Top-3 Monotonicity (or Top-triple Monotonicity) for the analogous result. Our results demonstrate that connection between dictatorship and “improvement” axioms is stronger than that suggested by the Muller–Satterthwaite result (Muller and Satterthwaite in J Econ Theory 14:412–418, 1977) and the Gibbard–Sattherthwaite theorem.     

Informational geometry of social choice

 Elementary geometry is used to understand, extend and resolve basic informational difficulties in choice theory. This includes axiomatic conclusions such as Arrow’s Theorem, Chichilnisky’s dictator, and the Gibbard–Satterthwaite result. In this manner new results about positional voting methods are outlined, and difficulties with axiomatic approach are discussed. A topological result about “dictatorial” behavior is offered. Received: 15 December 1993/Accepted: 22 April 1996     

Strategy-proof allocation of multiple public goods

This paper characterizes strategy-proof social choice functions (SCFs), the outcome of which are multiple public goods. Feasible alternatives belong to subsets of a product set . The SCFs are not necessarily “onto”, but the weaker requirement, that every element in each category of public goods A _k is attained at some preference profile, is imposed instead. Admissible preferences are arbitrary rankings of the goods in the various categories, while a separability restriction concerning preferences among the various categories is assumed. It is found that the range of the SCF is uniquely decomposed into a product set in general coarser than the original product set, and that the SCF must be dictatorial on each component B _l . If the range cannot be decomposed, a form of the Gibbard–Satterthwaite theorem with a restricted preference domain is obtained.     

Generalizing the Gibbard–Satterthwaite theorem: partial preferences,the degree of manipulation,and multi-valuedness

The Gibbard–Satterthwaite (GS) theorem is generalized in three ways: First, it is proved that the theorem is still valid when individual preferences belong to a convenient class of partial preferences; second, it is shown that every non-dictatorial surjective social choice function (SCF) is not only manipulable, but it can be manipulated in such a way that some individual obtains either his best or second best alternative; third, we prove a variant of the theorem where the outcomes of the SCF are subsets of the set of alternatives of an a priori fixed size. In addition, all results are proved not only for finite, but also for countably infinite sets of alternatives.     

‘One and a Half Dimensional’ Preferences and Majority Rule

I examine a model of majority rule in which alternatives are described by two characteristics: (1) their position in a standard, left-right dimension, and (2) their position in a good-bad dimension, over which voters have identical preferences. I show that when voters’ preferences are single-peaked and concave over the first dimension, majority rule is transitive, and the majority’s preferences are identical to the median voter’s. Thus, Black’s (The theory of committees and elections, 1958) theorem extends to such a “one and a half” dimensional framework. Meanwhile, another well-known result of majority rule, Downs’ (An economic theory of democracy, 1957) electoral competition model, does not extend to the framework. The condition that preferences can be represented in a one-and-a-half-dimensional framework is strictly weaker than the condition that preferences be single-peaked and symmetric. The condition is strictly stronger than the condition that preferences be order-restricted, as defined by Rothstein (Soc Choice Welf 7:331–342;1990).     

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.     

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.     

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.     

Dictatorial domains in preference aggregation

We call a domain of preference orderings “dictatorial” if there exists no Arrovian (Pareto optimal, IIA and non-dictatorial) social welfare function defined over that domain. In a finite world of alternatives where indifferences are ruled out, we identify a condition which implies the dictatoriality of a domain. This condition, to which we refer as “being essentially saturated”, is fairly weak. In fact, independent of the number of alternatives, there exists an essentially saturated (hence dictatorial) domain which consists of precisely six orderings. Moreover, this domain exhibits the superdictatoriality property, i.e., every superdomain of it is also dictatorial. Thus, given m alternatives, the ratio of the size of a superdictatorial domain to the size of the full domain may be as small as 6/m!, converging to zero as m increases.     

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.     

Negatively interdependent preferences

We develop a theory of representation of interdependent preferences that reflect the widely acknowledged phenomenon of keeping up with the Joneses (i.e. of those preferences which maintain that well-being depend on “relative standing” in the society as well as on material consumption). The principal ingredient of our analysis is the assumption that individuals desire to occupy a (subjectively) better position than their peers. This is quite a primitive starting point in that it does not give any reference to what is actually regarded as “status” in the society. We call this basic postulate negative interdependence, and study its implications. In particular, combining this assumption with some other basic postulates that are widely used in a number of other branches of the theory of individual choice, we axiomatize the relative income hypothesis, and obtain an operational representation of interdependent preferences. Received: 7 December 1998/Accepted: 24 August 1999     

On the multi-preference approach to evaluating opportunities

The purpose of the paper is to provide a general framework for analyzing “preference for opportunities.” Based on two simple axioms a fundamental result due to Kreps is used in order to represent rankings of opportunity sets in terms of multiple preferences. The paper provides several refinements of the basic representation theorem. In particular, a condition of “closedness under compromise” is suggested in order to distinguish the flexibility interpretation of the model from normative interpretations which play a crucial role in justifying the intrinsic value of opportunities. Moreover, the paper clarifies the link between the multiple preference approach and the “choice function” approach to evaluating opportunities. In particular, it is shown how the well-known Aizerman/Malishevski result on rationalizability of choice functions can be obtained as a corollary from the more general multiple preference representation of a ranking of opportunity sets. Received: 3 September 1996 / Accepted: 18 August 1997     

The structure of fuzzy preferences: Social choice implications

It has been shown that, with an alternative factorization of fuzzy weak preferences into symmetric and antisymmetric components, one can prove a fuzzy analogue of Arrow's Impossibility Theorem even when the transitivity requirements on individual and social preferences are very weak. It is demonstrated here that the use of this specification of strict preference, however, requires preferences to also be strongly connected. In the absence of strong connectedness, another factorization of fuzzy weak preferences is indicated, for which nondictatorial fuzzy aggregation rules satisfying the weak transitivity requirement can still be found. On the other hand, if strong connectedness is assumed, the fuzzy version of Arrow's Theorem still holds for a variety of weak preference factorizations, even if the transitivity condition is weakened to its absolute minimum. Since Arrow's Impossibility Theorem appeared nearly half a century ago, researchers have been attempting to avoid Arrow's negative result by relaxing various of his original assumptions. One approach has been to allow preferences – those of individuals and society or just those of society alone – to be “fuzzy.” In particular, Dutta [4] has shown that, to a limited extent, one can avoid the impossibility result (or, more precisely, the dictatorship result) by using fuzzy preferences, employing a particularly weak version of transitivity among the many plausible (but still distinct) definitions of transitivity that are available for fuzzy preferences. Another aspect of exact preferences for which the extension to the more general realm of fuzzy preferences is ambiguous is the factorization of a weak preference relation into a symmetric component (indifference) and an antisymmetric component (strict preference). There are several ways to do this for fuzzy weak preferences, all of them equivalent to the traditional factorization in the special case when preferences are exact, but quite different from each other when preferences are fuzzy (see, for example, [3]). A recent paper in this journal [1], by A. Banerjee, argues that the choice of definitions for indifference and strict preference, given a fuzzy weak preference, can also have “Arrovian” implications. In particular, [1] claims that Dutta's version of strict preference presents certain intuitive difficulties and recommends a different version, with its own axiomatic derivation, for which the dictatorship results reappear even with Dutta's weak version of transitivity. However, the conditions used to derive [1]'s version of strict preference imply a restriction on how fuzzy the original weak preference can be, namely, that the fuzzy weak preference relation must be strongly connected. Without this restriction, I will show that the rest of [1]'s conditions imply yet a third version of strict preference, for which Dutta's possibility result under weak transitivity still holds. On the other hand, if one accepts the strong connectedness required in order for it to be valid, I show that [1]'s dictatorship theorem can in fact be strengthened to cover any version of transitivity for fuzzy preferences, no matter how weak, and further, that this dictatorship result holds for any “regular” formulation of strict preference, including the one originally used by Dutta. Received: 13 May 1996 / Accepted: 13 January 1997     

Strategy-proofness versus efficiency on restricted domains of exchange economies

 Strategy-proofness has been shown to be a strong property, particularly on large domains of preferences. We therefore examine the existence of strategy-proof and efficient solutions on restricted, 2-person domains of exchange economies. On the class of 2-person exchange economies in which agents have homothetic, strictly convex preferences we show, as Zhou (1991) did for a larger domain, that such a solution is necessarily dictatorial. As this proof requires preferences exhibiting high degrees of complementarity, our search continues to a class of linear preferences. Even on this “small” domain, the same negative result holds. These two results are extended to many superdomains, including Zhou’s. Received: 9 June 1995/Accepted: 8 January 1996     

Extended Pareto rules and relative utilitarianism

This paper introduces the “Extended Pareto” axiom on Social Welfare Functions and gives a characterization of the axiom when it is assumed that the Social Welfare Functions that satisfy it in a framework of preferences over lotteries also satisfy the restrictions (on the domain and range of preferences) implied by the von-Neumann Morgenstern axioms. With the addition of 2 other axioms: “Anonymity” and a weak version of Arrow's Independence of Irrelevant Alternatives axiom: “Weak IIA” it is shown that there is a unique Social Welfare Function called “Relative Utilitarianism” that consists of normalising individual utilities between 0 and 1 and adding them. Received: 7 June 1994 / Accepted: 28 April 1997     

Coalitionally strategyproof functions depend only on the most-preferred alternatives

In a framework allowing infinitely many individuals, I prove that coalitionally strategyproof social choice functions satisfy “tops only.” That is, they depend only on which alternative each individual prefers the most, not on which alternative she prefers the second most, the third,…, or the least. The functions are defined on the domain of profiles measurable with respect to a Boolean algebra of coalitions. The unrestricted domain of profiles is an example of such a domain. I also prove an extension theorem. Received: 10 August 1998/Accepted: 3 May 1999     

An extension of the Moulin No Show Paradox for voting correspondences

In this article, we analyse the possibility of extending the Moulin theorem to Condorcet voting correspondences. Moulin (1988) established that every Condorcet voting function suffers from the No Show Paradox, or Abstention Paradox, which means that in some voting situations some voters would achieve a better result by abstaining (in other words, could manipulate the election by abstaining). This problem is similar to that of extending the Gibbard–Satterthwaite theorem on voting manipulation through casting an insincere ballot to voting correspondences. The main result of the paper states that for every Condorcet voting correspondence there are situations in which every optimistic or pessimistic voter with some preferences could manipulate the election by abstaining. Another result states, by counterexample, that some Condorcet voting correspondences are free from the Abstention Paradox from the point of view of other types of voters.     

Characterizing best–worst voting systems in the scoring context

An increasing body of theoretical and empirical work on discrete choice considers a choice design in which a person is asked to select both the best and the worst alternative in an available set of alternatives, in contrast to more traditional tasks, such as where the person is asked to: select the best alternative; select the worst alternative; rank the alternatives. Here we consider voting systems motivated by such “best–worst” choice; characterize a class of “best–worst” voting systems in terms of a set of axioms in the context of scoring rules; and discuss briefly possible extensions to approval–disapproval systems.     

Referenda as a Catch-22

The result of a referendum delivers a significant amount of information about social preferences to each composite member of the society. This paper argues that, beyond this obvious fact, the choice of an authority not to offer a referendum, although permitted to do so, may enhance the information individuals posses about social preferences as well. The addition of a referendum option in the rules of a game, that is, by enabling the authority to offer referenda at will, results in an assured re-election of the authorities that implement socially beneficial policies and reduces the likelihood of the re-election of the authorities that implement socially detrimental policies. In a sense, by allowing an authority to offer referenda, an inescapable Catch-22 is introduced in the game, which inhibits the re-election of a measure of “bad” authorities and, thus, confirms that one of the main benefits of a democratic institution is the preservation of “good” authorities in power. It is, finally, demonstrated that non-binding referenda are more influential (in the directions described above) than binding referenda as far as the authority’s re-election prospect is concerned.