Strategy-proofness on Euclidean spaces

 In this paper we characterize strategy-proof voting schemes on Euclidean spaces. A voting scheme is strategy-proof whenever it is optimal for every agent to report his best alternative. Here the individual preferences underlying these best choices are separable and quadratic. It turns out that a voting scheme is strategy-proof if and only if (α) its range is a closed Cartesian subset of Euclidean space, (β) the outcomes are at a minimal distance to the outcome under a specific coordinatewise veto voting scheme, and (γ) it satisfies some monotonicity properties. Neither continuity nor decomposability is implied by strategy-proofness, but these are satisfied if we additionally impose Pareto-optimality or unanimity. Received: 18 October 1993/Accepted: 2 February 1996     

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.     

Maximal Domain for Strategy-proof Rules in Allotment Economies

We consider the problem of allocating an amount of a perfectly divisible good among a group of n agents. We study how large a preference domain can be to allow for the existence of strategy-proof, symmetric and efficient allocation rules when the amount of the good is a variable. This question is qualified by an additional requirement that a domain should include a minimally rich domain. We first characterize the uniform rule (Bennasy in The economics of market disequilibrium, Academic, New York, 1982) as the unique strategy-proof, symmetric, and efficient rule on a minimally rich domain when the amount of the good is fixed. Then, exploiting this characterization, we establish the following: there is a unique maximal domain that includes a minimally rich domain and allows for the existence of strategy-proof, symmetric, and efficient rules when the amount of good is a variable. It is the single-plateaueddomain.     

Inefficiencies on linking decisions

It has recently been shown that by linking collective decisions the incentive costs can become negligible and, at the limit, ex ante efficiency can be achieved. In a voting situation this implies that the agents’ intensity of preferences can be taken into account even in the absence of monetary transfers. Rather than considering a limiting result we want to analyse what can be achieved while we consider a finite number of linked decisions. We first characterise the set of implementable mechanisms and show that ex ante efficiency can never be achieved. We then proceed to relax the efficiency requirement and prove that, even when we just require unanimity, the mechanism cannot be sensitive to the agents’ intensity of preference when the domain of preferences is unrestricted.     

A NONEQUILIBRIUM ANALYSIS OF UNANIMITY RULE, MAJORITY RULE, AND PARETO

It is widely held that in the absence of transaction costs unanimity rule is more effective at producing Pareto improvements and Pareto optimal outcomes than majority rule. We compare unanimity rule and majority rule in their ability to adhere to the Pareto criterion and to select Pareto-optimal alternatives using a single-dimensional spatial voting model without rational proposals. This produces two interesting results. First, if proposals are random, then majority rule is almost always more adept at selecting Pareto-optimal alternatives than unanimity rule. Second, if individuals propose their ideal points, then majority rule selects Pareto-optimal outcomes at least as well as unanimity rule. These results contrast with equilibrium analyses, which typically show that unanimity rule is the best voting procedure for maintaining Pareto optimality. (JEL D7 , C61 )     

An impossibility theorem for matching problems

This paper studies the possibility of strategy-proof rules yielding satisfactory solutions to matching problems. Alcalde and Barberá (Econ Theory 4:417–435, 1994) and Sönmez (Econ Des 1:365–380, 1994) show that efficient and individually rational matching rules are manipulable. We pursue the possibility of strategy-proof matching rules by relaxing efficiency to the weaker condition of respect for unanimity. First, we prove that a strategy-proof rule exists that is individually rational and respects unanimity. However, this rule is unreasonable in the sense that mutually best pairs of agents are matched on only rare occasions. In order to explore the possibility of better matching rules, we introduce a natural condition of “respect for 2-unanimity.” Respect for 2-unanimity states that a mutually best pair of agents should be matched, and an agent wishing to being unmatched should be unmatched. Our second result is negative. Secondly, we prove that no strategy-proof rule exists that respects 2-unanimity. This result implies Roth (Math Oper Res 7:617–628, 1962; J Econ Theory 36:277–288, 1985) showing that stable rules are manipulable.     

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.     

A characterization of strategy-proof social choice functions for economies with pure public goods

We characterize strategy-proof social choice functions when individuals have strictly quasi-concave, continuous and satiated utility functions on convex subsets of IR ^m , representing preferences for the provision of m pure public goods. When specialized to the case m=1, these assumptions amount to requiring that preferences are single peaked, and for such a domain there exists a wide class of strategy-proof social choice functions. These were studied by Moulin (1980) under strong additional assumptions. Our first results characterize the complete class, after an appropriate extension of the single-peakedness condition. The new characterization retains the flavour of Moulin's elegant representation theorem. For the general m-dimensional case, previous results have shown that there is no efficient, strategy-proof, nondictatorial social choice function, even within the domain restrictions under consideration (Border and Jordan 1983; Zhou 1991). In fact, Zhou's powerful result indicates that nondictatorial strategy-proof s.c.f.'s will have a range of dimension one. This allows us to conclude with a complete characterization of all strategy-proof s.c.f.'s on IR ^m , because restrictions of preferences from our admissible class to one dimensional subsets satisfy the slightly generalized notion of single-peakedness that is used in our characterization for the case m=1. We feel that a complete knowledge of the class of strategy-proof mechanisms, in this as well as in other contexts, is an important step in the analysis of the trade-offs between strategy-proofness and other performance criteria, like efficiency.This paper was written while both authors were visiting GREMAQ, Université des Sciences Sociales de Toulouse. We are thankful for its hospitality and good research atmosphere. Barberà's work is supported by the Instituto de Estudios Fiscales and by research grant PB89-0294 from the Secretaría de Estado de Universidades e Investigación, Spain. Jackson acknowledges the support of NSF grant SES8921409. We thank Jacques Crémer, Beth Allen, John Weymark and two anonymous referees for helpful comments on earlier drafts.     

On the selection of the same winner by all scoring rules

Different scoring rules can result in the selection of any of the k competing candidates, given the same preference profile, (Saari DG 2001, Chaotic elections! A mathematician looks at voting. American Mathematical Society, Providence, R.I.). It is also possible that a candidate, and even a Condorcet winning candidate, cannot be selected by any scoring rule, (Saari DG 2000 Econ Theory 15:55–101). These findings are balanced by Saari’s result (Saari DG 1992 Soc Choice Welf 9(4):277–306) that specifies the necessary and sufficient condition for the selection of the same candidate by all scoring rules. This condition is, however, indirect. We provide a sufficient condition that is stated directly in terms of the preference profile; therefore, its testability does not require the verdict of any voting rule.     

Strategy-proof Cardinal Decision Schemes

This paper analyses strategy-proof mechanisms or decision schemes which map profiles of cardinal utility functions to lotteries over a finite set of outcomes. We provide a new proof of Hylland’s theorem which shows that the only strategy-proof cardinal decision scheme satisfying a weak unanimity property is the random dictatorship. Our proof technique assumes a framework where individuals can discern utility differences only if the difference is at least some fixed number which we call the grid size. We also prove a limit random dictatorship result which shows that any sequence of strategy-proof and unanimous decision schemes defined on a sequence of decreasing grid sizes approaching zero must converge to a random dictatorship. We are most grateful to an Associate Editor and two referees for very helpful comments on an earlier version of the paper. An erratum to this article can be found at     

A characterization of strategy-proof voting rules for separable weak orderings

We consider the problem of choosing a subset of a finite set of indivisible objects (public projects, facilities, laws, etc.) studied by Barberà et al. (1991). Here we assume that agents preferences are separable weak orderings. Given such a preference, objects are partitioned into three types, goods, bads, and nulls. We focus on voting rules, which rely only on this partition rather than the full information of preferences. We characterize voting rules satisfying strategy-proofness (no one can ever be better off by lying about his preference) and null-independence (the decision on each object should not be dependent on the preference of an agent for whom the object is a null). We also show that serially dictatorial rules are the only voting rules satisfying efficiency as well as the above two axioms. We show that the separable domain is the unique maximal domain over which each rule in the first characterization, satisfying a certain fairness property, is strategy-proof. I am grateful to Professor William Thomson for helpful comments and suggestions. I also thank Professor John Duggan, Christopher Chambers, and seminar participants in Department of Economics, University of Rochester. I thank anonymous referees for their detailed comments and suggestions that helped me a great deal to develop the earlier version of this paper. All remaining errors are mine.     

An incompatibility between recursive unanimity and strategy-proofness in two-sided matching problems

In this article, we study the incompatibilities for the properties on matching rules in two-sided many-to-one matching problems under responsive preferences. We define a new property called respect for recursive unanimity. This property requires that if every agent matches with its first choice among its really possible choices that are based on a recursive procedure like the well-known top trading cycles algorithm, then we should respect it. More precisely, given a matching problem, we exclude the agents whose first choices are satisfied without any discrepancy among them, and consider the restricted matching problems of the remaining agents. If we reach a state in which all agents are excluded by repeating this procedure, then we should respect the outcome. This property is weaker than stability and is stronger than respect for unanimity (that is also known as weak unanimity). We show that there are no strategy-proof matching rules that respect recursive unanimity.     

Note on social choice allocation in exchange economies with Cobb–Douglas preferences

We show that in a pure exchange economy with two agents and a finite number of goods, there exists no strategy-proof, Pareto-efficient, and non-dictatorial social choice allocation function on any local Cobb–Douglas preference domain. This is a slight extension of a result proved by Hashimoto (2008).     

Generalized average rules as stable Nash mechanisms to implement generalized median rules

We consider a problem in which a policy is chosen from a one-dimensional set over which voters have single-peaked preferences. While Moulin (Public Choice 35:437–455, 1980) and others subsequent works have focused on strategy-proof rules, Renault and Trannoy (Mimeo 2011) and Renault and Trannoy (J Pub Econ Theory 7:169–199, 2005) have shown that the average rule implements a generalized median rule in Nash equilibria and provide an interpretation of the parameters in Moulin’s rule. In this article, we first extend their result by showing that a wide range of voting rules which includes the average rule can implement Moulin’s rule in Nash equilibria. Moreover, we show additionally that within this class, generalized average rules are Cournot stable. That is, from any strategy profile, any best response path must converge to a Nash equilibrium.     

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.     

Domains, ranges and strategy-proofness: the case of single-dipped preferences

We characterize the set of all individual and group strategy-proof rules on the domain of all single-dipped preferences on a line. For rules defined on this domain, and on several of its subdomains, we explore the implications of these strategy-proofness requirements on the maximum size of the rules’ range. We show that when all single-dipped preferences are admissible, the range must contain two alternatives at most. But this bound changes as we consider different subclasses of single-dipped preferences: we provide examples of subdomains admitting strategy-proof rules with larger ranges. We establish exact bounds on the maximal size of strategy-proof functions on each of these domains, and prove that the relationship between the sizes of the subdomains and those of the ranges of strategy-proof functions on them need not be monotonic. Our results exhibit a sharp contrast between the structure of strategy-proof rules defined on subdomains of single-dipped preferences and those defined on subsets of single-peaked ones.     

Topological aggregation of preferences: the case of a continuum of agents

 This paper studies the topological approach to social choice theory initiated by G. Chichilnisky (1980), extending it to the case of a continuum of agents. The social choice rules are continuous anonymous maps defined on preference spaces which respect unanimity. We establish that a social choice rule exists for a continuum of agents if and only if the space of preferences is contractible. We provide also a topological characterization of such rules as generalized means or mathematical expectations of individual preferences. Received: 30 November 1994/Accepted: 22 April 1996     

How the size of a coalition affects its chances to influence an election

Since voting rules are prototypes for many aggregation procedures, they also illuminate problems faced by economics and decision sciences. In this paper we are trying to answer the question: How large should a coalition be to have a chance to influence an election? We answer this question for all scoring rules and multistage elimination rules, under the Impartial Anonymous Culture assumption. We show that, when the number of participating agents n tends to infinity, the ratio of voting situations that can be influenced by a coalition of k voters to all voting situations is no greater than $D_{m} \frac{k}{n}Since voting rules are prototypes for many aggregation procedures, they also illuminate problems faced by economics and decision sciences. In this paper we are trying to answer the question: How large should a coalition be to have a chance to influence an election? We answer this question for all scoring rules and multistage elimination rules, under the Impartial Anonymous Culture assumption. We show that, when the number of participating agents n tends to infinity, the ratio of voting situations that can be influenced by a coalition of k voters to all voting situations is no greater than , where D _m is a constant which depends only on the number m of alternatives but not on k and n. Recent results on individual manipulability in three alternative elections show that this estimate is exact for k=1 and m=3.

Arkadii SlinkoEmail:

     

The original Borda count and partial voting

In a Borda count, bc, M. de Borda suggested the last preference cast should receive 1 point, the voter’s penultimate ranking should get 2 points, and so on. Today, however, points are often awarded to (first, second,..., last) preferences cast as per (n, n?1, ..., 1) or more frequently, (n ?1, n?2,..., 0). If partial voting is allowed, and if a first preference is to be given n or n ? 1 points regardless of how many preferences the voter casts, he/she will be incentivised to rank only one option/candidate. If everyone acts in this way, the bc metamorphoses into a plurality vote... which de Borda criticized at length. If all the voters submit full ballots, the outcome—social choice or ranking—will be the same under any of the above three counting procedures. In the event of one or more persons submitting a partial vote, however, outcomes may vary considerably. This preliminary paper suggests research should consider partial voting. The author examines the consequences of the various rules so far advocated and then purports that M. de Borda, in using his formula, was perhaps more astute than the science has hitherto recognised.     

Limiting distributions for continuous state Markov voting models

This paper proves the existence of a stationary distribution for a class of Markov voting models. We assume that alternatives to replace the current status quo arise probabilistically, with the probability distribution at time t+1 having support set equal to the set of alternatives that defeat, according to some voting rule, the current status quo at time t. When preferences are based on Euclidean distance, it is shown that for a wide class of voting rules, a limiting distribution exists. For the special case of majority rule, not only does a limiting distribution always exist, but we obtain bounds for the concentration of the limiting distribution around a centrally located set. The implications are that under Markov voting models, small deviations from the conditions for a core point will still leave the limiting distribution quite concentrated around a generalized median point. Even though the majority relation is totally cyclic in such situations, our results show that such chaos is not probabilistically significant.We acknowledge the support of NSF Grants #SOC79-21588, SES-8106215 and SES-8106212.