A maximal domain of preferences for strategy-proof,efficient, and simple rules in the division problem

The division problem consists of allocating an amount M of a perfectly divisible good among a group of n agents. Sprumont (1991) showed that if agents have single-peaked preferences over their shares, the uniform rule is the unique strategy-proof, efficient, and anonymous rule. Ching and Serizawa (1998) extended this result by showing that the set of single-plateaued preferences is the largest domain, for all possible values of M, admitting a rule (the extended uniform rule) satisfying strategy-proofness, efficiency and symmetry. We identify, for each M and n, a maximal domain of preferences under which the extended uniform rule also satisfies the properties of strategy-proofness, efficiency, tops-onlyness, and continuity. These domains (called partially single-plateaued) are strictly larger than the set of single-plateaued preferences. However, their intersection, when M varies from zero to infinity, coincides with the set of single-plateaued preferences.An earlier version of this paper circulated under the title A maximal domain of preferences for tops-only rules in the division problem. We are grateful to an associate editor of this journal for comments that helped to improve the presentation of the paper and to Matt Jackson for suggesting us the interest of identifying a maximal domain of preferences for tops-only rules. We are also grateful to Dolors Berga, Flip Klijn, Howard Petith, and a referee for helpful comments. The work of Alejandro Neme is partially supported by Research Grant 319502 from the Universidad Nacional de San Luis. The work of Jordi Massó is partially supported by Research Grants BEC2002-02130 from the Spanish Ministerio de Ciencia y Tecnología and 2001SGR-00162 from the Generalitat de Catalunya, and by the Barcelona Economics Program of CREA from the Generalitat de Catalunya. The paper was partially written while Alejandro Neme was visiting the UAB unde r a sabbatical fellowship from the Generalitat de Catalunya.     

The replacement principle for the provision of multiple public goods on tree networks

This article considers the provision of two public goods on tree networks where each agent has a single-peaked preference. We show that if there are at least four agents, then no social choice rule exists that satisfies efficiency and replacement-domination. In fact, these properties are incompatible, even if agents’ preferences are restricted to a smaller domain of symmetric single-peaked preferences. However, for rules on an interval, we prove that Miyagawa’s (Soc Choice Welf 18:527–541, 2001) characterization that only the left-peaks rule and the right-peaks rule satisfy both of these properties also holds on the domain of symmetric single-peaked preferences. Moreover, if agents’ peak locations are restricted to either the nodes or the endpoints of trees, rules exist on a subclass of trees. We provide a characterization of a family of such rules for this tree subclass.     

A characterization of the uniform rule with several commodities and agents

We consider a problem of allocating infinitely divisible commodities among a group of agents. More specifically, there are several commodities to be allocated and agents have continuous, strictly convex, and separable preferences. We establish that a rule satisfies strategy-proofness, unanimity, weak symmetry, and nonbossiness if and only if it is the uniform rule. This result extends to the class of continuous, strictly convex, and multidimensional single-peaked preferences.     

Dominant strategy implementation with a convex product space of valuations

A necessary and sufficient condition for dominant strategy implementability when preferences are quasilinear is that, for every individual i and every choice of the types of the other individuals, all k-cycles in i’s allocation graph have nonnegative length for every integer k ≥ 2. Saks and Yu (Proceedings of the 6th ACM conference on electronic commerce (EC’05), pp 286–293, 2005) have shown that when the number of outcomes is finite and i’s valuation type space is convex, nonnegativity of the length of all 2-cycles is sufficient for the nonnegativity of the length of all k-cycles. In this article, it is shown that if each individual’s valuation type space is a full-dimensional convex product space and a mild domain regularity condition is satisfied, then (i) the nonnegativity of all 2-cycles implies that all k-cycles have zero length and (ii) all 2-cycles having zero length is necessary and sufficient for dominant strategy implementability.     

Strategic requirements with indifference: single-peaked versus single-plateaued preferences

We concentrate on the problem of the provision of one pure public good whenever agents that form the society have either single-plateaued preferences or single-peaked preferences over the set of alternatives. We are interested in comparing the relationships between different nonmanipulability notions under these two domains. On the single-peaked domain, under strategy-proofness, non-bossiness is equivalent to convexity of the range. Thus, minmax rules are the only strategy-proof non-bossy rules. On the single-plateaued domain, only constant rules are non-bossy or Maskin monotonic; but strategy-proofness and weak non-bossiness are equivalent to weak Maskin monotonicity. Moreover, strategy-proofness and plateau-invariance guarantee convexity of the range. We thank Salvador Barberà, Matthew Jackson, Bettina Klaus, Jordi Massó, John Weymark, and two anonymous referees and the Associate Editor for helpful comments and suggestions. We also thank the participants in the 3rd Workshop on Social Decisions that took place in Málaga in November 2007. Dolors Berga acknowledges the financial support by the Spanish Ministry of Education and Science through Research Grants SEJ2004-03276 and SEJ2007-60671 and also by the Generalitat de Catalunya through Research Grant 2005SGR-213 and the Barcelona Economics Program (CREA). Bernardo Moreno gratefully acknowledges financial support from Junta de Andalucía through grant SEJ522 and the Spanish Ministry of Science and Technology through grant SEC2005-04805.     

Single-peaked preferences with several commodities

We consider the problem of allocating m commodities among n agents with single-peaked preferences. When m≥2 and n=2 any strategy-proof and efficient solution is dictatorial. We propose an extension of the Uniform Rule that (in the two-agents case) is the only one that satisfies strategy-proofness, envy-freeness, and a weak requirement related to efficiency. Alternatively, the envy-freeness property may be replaced by weak-anonymity. Received: 7 November 1997/Accepted: 1 August 2000     

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.     

On the manipulability of approval voting and related scoring rules

We characterize all preference profiles at which the approval (voting) rule is manipulable, under three extensions of preferences to sets of candidates: by comparison of worst candidates, best candidates, or by comparison based on stochastic dominance. We perform a similar exercise for k-approval rules, where voters approve of a fixed number k of candidates. These results can be used to compare (k-)approval rules with respect to their manipulability. Analytical results are obtained for the case of two voters, specifically, the values of k for which the k-approval rule is minimally manipulable—has the smallest number of manipulable preference profiles—under the various preference extensions are determined. For the number of voters going to infinity, an asymptotic result is that the k-approval rule with k around half the number of candidates is minimally manipulable among all scoring rules. Further results are obtained by simulation and indicate that k-approval rules may improve on the approval rule as far as manipulability is concerned.     

The sensitivity of weight selection for scoring rules to profile proximity to single-peaked preferences

Niemi (Am Polit Sci Rev 63:488–497, 1969) proposed a simple measure of the cohesiveness of a group of n voters’ preferences that reflects the proximity of their preferences to single-peakedness. For three-candidate elections, this measure, k, reduces to the minimum number of voters who rank one of the candidates as being least preferred. The current study develops closed form representations for the conditional probability, PASW(n,IAC|k), that all weighted scoring rules will elect the Condorcet winner in an election, given a specified value of k. Results show a very strong relationship between PASW(n,IAC|k) and k, such that the determination of the voting rule to be used in an election becomes significantly less critical relative to the likelihood of electing the Condorcet winner as voters in a society have more structured preferences. As voters’ preferences become more unstructured as measured by their distance from single-peakedness, it becomes much more likely that different voting rules will select different winners.A preliminary version of this paper was presented at the European Public Choice Society Conference in Berlin, Germany, April 15–18, 2004.     

Maximal domain for strategy-proof probabilistic rules in economies with one public good

We consider the problem of choosing a level of a public good on an interval of the real line among a group of agents. A probabilistic rule chooses a probability distribution over the interval for each preference profile. We investigate strategy-proof probabilistic rules in the case where distributions are compared based on stochastic dominance relations. First, on a “minimally rich domain”, we characterize the so-called probabilistic generalized median rules (Ehlers et al., J Econ Theory 105:408–434, 2002) by means of stochastic-dominance (sd) strategy-proofness and ontoness. Next, we study how much we can enlarge a domain to allow for the existence of sd-strategy-proof probabilistic rules that satisfy ontoness and the no-vetoer condition. We establish that the domain of “convex” preferences is the unique maximal domain including a minimally rich domain for these properties.     

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.     

Strategy-proof division with single-peaked preferences and individual endowments

We consider the problem of (re)allocating the total endowment of an infinitely divisible commodity among agents with single-peaked preferences and individual endowments. We propose an extension of the so-called uniform rule and show that it is the unique rule satisfying Pareto optimality, strategy-proofness, reversibility, and an equal-treatment condition. The resulting rule turns out to be peaks-only and individually rational: the allocation assigned by the rule depends only on the peaks of the preferences, and no agent is worse off than at his individual endowment. Received: 8 September 1995/Accepted: 30 October 1996     

Fair allocation of indivisible goods: the two-agent case

One must allocate a finite set of indivisible goods among two agents without monetary compensation. We impose Pareto-efficiency, anonymity, a weak notion of no-envy, a welfare lower bound based on each agent’s ranking of the subsets of goods, and a monotonicity property w.r.t. changes in preferences. We prove that there is a rule satisfying these axioms. If there are three goods, it is the only rule, together with one of its subcorrespondences, satisfying each fairness axiom and not discriminating between goods.     

Unequivocal majority and Maskin-monotonicity

The unequivocal majority of a social choice rule is a number of agents such that whenever at least this many agents agree on the top alternative, then this alternative (and only this) is chosen. The smaller the unequivocal majority is, the closer it is to the standard (and accepted) majority concept. The question is how small can the unequivocal majority be and still permit the Nash-implementability of the social choice rule; i.e., its Maskin-monotonicity. We show that the smallest unequivocal majority compatible with Maskin-monotonicity is n- ë \fracn-1m û{n-\left\lfloor \frac{n-1}{m} \right\rfloor} , where n ≥ 3 is the number of agents and m ≥ 3 is the number of alternatives. This value is equal to the minimal number required for a majority to ensure the non-existence of cycles in pairwise comparisons. Our result has a twofold implication: (1) there is no Condorcet consistent social choice rule satisfying Maskin-monotonicity and (2) a social choice rule satisfies k-Condorcet consistency and Maskin-monotonicity if and only if k 3 n- ë \fracn-1m û{k\geq n-\left\lfloor \frac{n-1}{m}\right\rfloor}.     

The relation between monotonicity and strategy-proofness

The Muller–Satterthwaite Theorem (J Econ Theory 14:412–418, 1977) establishes the equivalence between Maskin monotonicity and strategy-proofness, two cornerstone conditions for the decentralization of social choice rules. We consider a general model that covers public goods economies as in Muller–Satterthwaite (J Econ Theory 14:412–418, 1977) as well as private goods economies. For private goods economies, we use a weaker condition than Maskin monotonicity that we call unilateral monotonicity. We introduce two easy-to-check preference domain conditions which separately guarantee that (i) unilateral/Maskin monotonicity implies strategy-proofness (Theorem 1) and (ii) strategy-proofness implies unilateral/Maskin monotonicity (Theorem 2). We introduce and discuss various classical single-peaked preference domains and show which of the domain conditions they satisfy (see Propositions 1 and 2 and an overview in Table 1). As a by-product of our analysis, we obtain some extensions of the Muller–Satterthwaite Theorem as summarized in Theorem 3. We also discuss some new “Muller–Satterthwaite preference domains” (e.g., Proposition 3).     

Social threshold aggregations

A problem of axiomatic construction of a social decision function is studied for the case when individual opinions of agents are given as m-graded preferences with arbitrary integer m ≥ 3. It is shown that the only rule satisfying the introduced axioms of Pairwise Compensation, Pareto Domination and Noncompensatory Threshold and Contraction is the threshold rule.     

The core of social choice problems with monotone preferences and a feasibility constraint

We consider collective choice with agents possessing strictly monotone, strictly convex and continuous preferences over a compact and convex constraint set contained in ₊^k . If it is non-empty the core will lie on the efficient boundary of the constraint set and any policy not in the core is beaten by some policy on the efficient boundary. It is possible to translate the collective choice problem on this efficient boundary to another social choice problem on a compact and convex subset of ₊^c (c<k) with strictly convex and continuous preferences. In this setting the dimensionality results in Banks (1995) and Saari (1997) apply to the dimensionality of the boundary of the constraint set (which is lower than the dimensionality of the choice space by at least one). If the constraint set is not convex then the translated lower dimensional problem does not necessarily involve strict convexity of preferences but the dimensionality of the problem is still lower. Broadly, the results show that the homogeneity afforded by strict monotonicity of preferences and a compact constraint set makes generic core emptyness slightly less common. One example of the results is that if preferences are strictly monotone and convex on ² then choice on a compact and convex constraint exhibits a version of the median voter theorem.I thank Donald Saari for helpful comments on an earlier version of this paper.     

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.     

Identification of domain restrictions over which acyclic, continuous-valued, and positive responsive social choice rules operate

We consider a social choice problem in various economic environments consisting of n individuals, 4≤n<+∞, each of which is supposed to have classical preferences. A social choice rule is a function associating with each profile of individual preferences a social preference that is assumed to be complete, continuous and acyclic over the alternatives set. The class of social choice rules we deal with is supposed to satisfy the two conditions; binary independence and positive responsiveness. A new domain restriction for the social choice rules is proposed and called the classical domain that is weaker than the free triple domain and holds for almost all economic environments such as economies with private and/or public goods. In this paper we explore what type of classical domain that admits at least one social choice rule satisfying the mentioned conditions to well operate over the domain. The results we obtained are very negative: For any classical domain admitting at least one social choice rule to well operate, the domain consists only of just one profile.     

Equity and the Vickrey allocation rule on general preference domains

We consider the problem of allocating multiple units of an indivisible good among a group of agents in which each agent demands at most one unit of the good and money payment or receipt is required. Under general preference domains that may contain non quasi-linear preferences, the Vickrey allocation rule is characterized by axioms for equity and continuity without use of efficiency: namely, the Vickrey rule is the only rule that satisfies strategy-proofness, weak envy-freeness for equals, non-imposition, and continuity of welfare.