Strategy-proof allocation of indivisible goods

Strategy-proof allocation of a finite number of indivisible goods among a finite number of individuals is considered. The main result is that in a pure distributional case, a mechanism is strategy-proof, nonbossy and neutral if and only if it is serially dictatorial. If the indivisible goods are initially owned by the individuals, a mechanism is strategy-proof, individually rational and Pareto consistent if and only if it is the core mechanism. Received: 15 September 1997/Accepted: 12 May 1998     

On monotonicity in economies with indivisible goods

We consider the problem of fair allocation in economies with indivisible objects that may or may not be desirable (for instance, activities that may or may not be pleasurable but have to be carried out unless there are not enough agents for that). We search for efficient solutions satisfying two additional properties. First, each agent should find his bundle at least as desirable as the bundle that would be assigned to him in the hypothetical economy in which all agents have preferences identical to his, under equal treatment of equals and efficiency. In a preliminary step, we show that there is no logical relation between this requirement and no-envy, and between it and egalitarian-equivalence. We also establish the existence of efficient allocations satisfying it. The second property, object monotonicity, says that the availability of additional objects either has a negative impact on everyone's welfare, or it has a positive impact on everyone's welfare. We show that there is no object-monotonic selection from the correspondence that associates with each economy its set of efficient allocations meeting an even weaker version of the bound.I am grateful to Atila Abdulkadiroglu, Koichi Tadenuma, and a referee for their very helpful comments.     

Asymmetrically fair rules for an indivisible good problem with a budget constraint

We study a particular restitution problem where there is an indivisible good (land or property) over which two agents have rights: the dispossessed agent and the owner. A third party, possibly the government, seeks to resolve the situation by assigning rights to one and compensate the other. There is also a maximum amount of money available for the compensation. We characterize a family of asymmetrically fair rules that are immune to strategic behavior, guarantee minimal welfare levels for the agents, and satisfy the budget constraint.     

The replacement principle in economies with indivisible goods

 We consider the problem of allocating a list of indivisible goods and some amount of an infinitely divisible good among agents with equal rights on these resources, and investigate the implications of the following requirement on allocation rules: when the preferences of some of the agents change, all agents whose preferences are fixed should (weakly) gain, or they should all (weakly) lose. This condition is an application of a general principle of solidarity discussed in Thomson (1990b) under the name “replacement principle”. We look for selections from the no-envy solution satisfying this property. We show that in the general case, when the number of objects is arbitrary, there is no such selection. However, in the one-object case (a single prize), up to Pareto-indifference, there is only one selection from the no-envy solution satisfying the property. Such a solution always selects an envy-free allocation at which the winner of the prize is indifferent between his bundle and the losers’ common bundle. Received: 15 May 1995 / Accepted: 5 June 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.     

Queue allocation of indivisible goods

A model with a finite number of indivisible goods (houses) and the same number of individuals is considered. The allocation of houses among the individuals according to a queue order is analysed. First an allocation mechanism is constructed where it is a dominant strategy for the individuals to truthfully report their preferences. Second it is demonstrated that in order to obtain the desired allocation, the individuals must not in general report their complete ranking of the houses, but only their maximal elements in recursively defined choice sets.Financial support from Jan Wallander's Foundation for Research in the Social Sciences is gratefully acknowledged.A first version of this paper was presented at ESEM in Cambridge 1991.     

Coalitionally strategy-proof rules in allotment economies with homogeneous indivisible goods

We consider the allotment problem of homogeneous indivisible goods among agents with single-peaked and risk-averse von Neumann–Morgenstern expected utility functions. We establish that a rule satisfies coalitional strategy-proofness, same-sideness, and strong symmetry if and only if it is the uniform probabilistic rule. By constructing an example, we show that if same-sideness is replaced by respect for unanimity, this statement does not hold even with the additional requirements of no-envy, anonymity, at most binary, peaks-onlyness and continuity. We would like to thank the associate editor and two anonymous referees whose comments and suggestions significantly improve this paper. We are also grateful to Masaki Aoyagi, Kazuhiko Hashimoto, Hervé Moulin, Hiroo Sasaki, Koji Takamiya, William Thomson, Takuma Wakayama as well as other participants at the Eighth International Meeting of the Society for Social Choice and Welfare in Istanbul, the 2006 Autumn Annual Meeting of the Japanese Economic Association in Osaka, and Yokohama National University Seminar of Economic Theory for their helpful comments. We acknowledge financial supports from the Japan Society for the Promotion of Science via the Research Fellowship for Young Scientist (Hatsumi) and the Grant-in-Aid for Scientific Research (Serizawa).     

Inefficiency of strategy-proof allocation mechanisms in pure exchange economies

In this paper I prove that in the standard model of 2×n (n2) pure exchange economies there is no allocation mechanism that is efficient, non-inversely-dictatorial, and strategy-proof. This strengthens two previous results on this subject by Hurwicz and by Dasgupta, Hammond, and Maskin.I thank Alvin Klevorick, William Thomson, and an anonymous referee of the journal for many helpful comments.     

The proportional random allocation of indivisible units

Indivisible units are randomly allocated among agents with a claim/demand on the resources. The available resources fall short of the sum of individual claims.  The proportional method distributes units sequentially, and the probability of receiving a unit at any step is proportional to the unsatisfied claims.  We characterize the family of probabilistic rationing methods meeting the three axioms Consistency, Lower and Upper Composition. It contains the proportional method, all deterministic fixed priority methods, and the priority compositions of proportional methods. The proportional method is the only fair method in the family. Received: 30 November 1999/Accepted: 15 November 2000     

Identical preferences lower bound solution and consistency in economies with indivisible goods

We consider the problem of allocating a finite set of indivisible goods and a single infinitely divisible good among a group of agents, and we study a solution, called the Identical Preferences Lower Bound solution, in the presence of consistency properties. This solution is not consistent. We prove that its maximal consistent subsolution is the No-envy solution. Our main result is that the minimal consistent extension of the intersection of the Identical Preferences Lower Bound solution with the Pareto solution is the Pareto solution. This result remains true in the restricted domain when all the indivisible goods are identical, but not when there is a unique indivisible good.This paper was developed during my stay at Rochester University in the summer of 1992. I would like to express my special thanks to Professor William Thomson for all his help and advice. Iam also grateful to my supervisor Luis Corchón, to Koichi Tadenuma and to the anonymous referees for their helpful comments. The remaining errors are my exclusive responsibility. Financial support from the DGCYT under project PB 91-0756 and the Instituto Valenciano de Investigaciones Económicas are gratefully acknowledged.     

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.     

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.     

Equilibrium in abstract political economies: with an application to a public good economy with voting

Consider an abstract political economy which has a collective choice rule together with strategic interactions among players. We prove that there exists an equilibrium in such an economy by synthesizing an equilibrium existence theorem in generalized games by Shafer and Sonnenschein (1975) and a voting core existence theorem in simple games by Schofield (1984, 1989). The theorem can be applied to a public good economy where public good provisions are determined by a class of voting rule.Thanks are due to David Austen-Smith, Jeffrey Banks, Marcus Berliant, Steve Ching, Ryo-Ichi Nagahisa, Mary Beth Savio, Norman Schofield, and Tomoichi Shinotsuka. Detailed comments from an anonymous referee of the journal are gratefully acknowledged. Errors are, of course, my own.     

Fair and group strategy-proof good allocation with money

We completely characterize the class of fair and group strategy-proof mechanisms. We consider two notions of fairness, anonymity in welfare and no-envy. Both fairness axioms, when applied with strategy-proofness, imply decision efficiency, and lead to the same class of group strategy-proof mechanisms (where the group size is restricted to two). We find that the only feasible mechanism satisfying a mild zero transfer axiom, in this class, is the Pivotal mechanism.     

An algorithm for envy-free allocations in an economy with indivisible objects and money

This paper studies envy-free allocations for economies with indivisible objects, quasi-linear utility functions, and an amount of money. We give a polynomially bounded algorithm for finding envy-free allocations. Connectedness of envy-graphs, which are used in the algorithm, characterizes the extreme points of the polytopes of sidepayments corresponding with envy-free allocations. Received: 22 October 1997/Accepted: 19 January 1999     

Axiomatization of ratio equilibria in public good economies

Using consistency properties, we characterize the cost-sharing scheme arising from the ratio equilibrium concept for economies with public goods. The characterization turns out to be surprisingly simple and direct. In contrast to most axiomatic characterizations based on reduced games and consistency properties, our characterization requires that in the reduced game, the players take as given the proportions of the costs paid by the members of the complementary player set, rather than their utility levels. Received: 4 July 1996/Accepted: 28 March 2001     

Strategy-proof voting schemes with continuous preferences

We prove that all nondictatorial voting schemes whose range has more than two alternatives will be manipulable, when their domain is restricted to the set of all continuous preferences over alternatives. Our result neither implies nor is implied by the original Gibbard-Satterthwaite theorem, except if the number of alternatives is finite, when they coincide. A new, direct line of reasoning is used in the proof. It is presented in an introductory section, which may be useful in classroom situations.The work of S. Barberà is partially supported by Research Grant PB 86-0613, from the Dirección General de la Investigación Científica y Técnica, Spanish Ministry of Education.