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     

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.     

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.     

Strategy-proof allocation mechanisms for economies with an indivisible good

We consider economies with a single indivisible good and money. We characterize the set of mechanisms that satisfy strategy-proofness, individual rationality, equal compensation, and demand monotonicity. There are three types of mechanisms which have the following properties: (i) they determine the allocation of monetary compensation depending on who receives the indivisible good; (ii) they allocate the indivisible good to one of the pre-specified (one or two) agent(s); and (iii) they disregard preferences of agents other than the pre-specified agent(s). This result implies that the presence of an indivisible good induces serious asymmetry in mechanisms. Received: 26 March 1996 / Accepted: 23 September 1997     

The Home Office and random allocation experiments

By examining the history of the random experiment in the Home Office in the United Kingdom, this article demonstrates that research is not an altogether rational process and that fashion, personality, and politics are at least as important as science and evidence when setting research and policy programs and determining methodologies. The article also shows that even in 1970, the research world was a village and that issues and fashions on one side of it could determine the outcome of decisions on the other side, even though they had no direct relevance. On a more optimistic note, the article shows how the fashions go in cycles so that if you could not get the research funded in the last cycle, just wait 20 years for the cycle to come around and try again.     

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     

The undercut procedure: an algorithm for the envy-free division of indivisible items

We propose a procedure for dividing a set of indivisible items between two players. We assume that each player’s preference over subsets of items is consistent with a strict ranking of the items, and that neither player has information about the other’s preferences. Our procedure ensures an envy-free division—each player receives a subset of items that it values more than the other player’s complementary subset—given that an envy-free division of “contested items,” which the players would choose at the same time, is possible. We show that the possibility of one player’s undercutting the other’s proposal, and implementing the reduced subset for himself or herself, makes the proposer “reasonable,” and generally leads to an envy-free division, even when the players rank items exactly the same. Although the undercut procedure is manipulable and its envy-free allocation may be Pareto-inferior, each player’s maximin strategy is to be truthful. Applications of the procedure are discussed briefly.     

Probabilistic assignment of indivisible goods with single-peaked preferences

We consider the problem of assigning indivisible goods among a group of agents with lotteries when the preference profile is single-peaked. Unfortunately, even on this restricted domain of preferences, equal treatment of equals, stochastic dominance efficiency, and stochastic dominance strategy-proofness are incompatible.     

A simple procedure for finding equitable allocations of indivisible goods

The paper investigates how far a particular procedure, called the “descending demand procedure,” can take us in finding equitable allocations of indivisible goods. Both interpersonal and intrapersonal criteria of equitability are considered. It is shown that the procedure generally fares well on an interpersonal criterion of “balancedness”; specifically, the resulting allocations are Pareto-optimal and maximize the well-being of the worst-off individual. As a criterion of intrapersonal equitability, the property of envy-freeness is considered. To accommodate envy-freeness, a modification of the basic procedure is suggested. With two individuals, the modified procedure is shown to select the envy-free allocations that are balanced, i.e. the allocations that maximize the well-being of the worse-off individual among all envy-free allocations. Received: 3 March 2000/Accepted: 27 November 2000     

Money-egalitarian-equivalent and gain-maximin allocations of indivisible items with monetary compensation

Suppose that a certain quantity M of money and a finite number of indivisible items are to be distributed among n people, all of whom have equal claims on the whole. Different allocations are presented using various criteria of fairness in the special case where each player's utility function is additively separable. An allocation is “money-egalitarian-equivalent” (MEE) if each player's monetary valuation of his or her bundle is a fixed constant. We show that there is an essentially unique allocation that is MEE and Pareto-optimal; it is also envy-free. Alternatively, the “gain” of a player may be defined as the difference between how the player evaluates his bundle and an exact nth part of the whole according to his numerical evaluation of the whole. A “gain-maximin” criterion would maximize the minimum gain obtained by any player. We show that Knaster's procedure finds an allocation which is optimal under the gain-maximin criterion. That allocation is not necessarily envy-free, so we also find the envy-free allocation that is optimal under the gain-maximin criterion among all envy-free allocations. It turns out that, even though there exist allocations that are simultaneously envy-free and Pareto-optimal, this optimal allocation may fail to be Pareto-optimal, and it may also violate monotonicity criteria. Received: 30 September 1996/Accepted: 6 March 2002 The author would like to thank Professor William Thomson for a discussion on this subject; and he would like to thank the anonymous referees, who made many substantive suggestions for improving this paper – shortening it, streamlining the arguments, improving the terminology, making further ties with the literature, and improving the exposition.     

The allocation of money in cross-class families

This paper examines the patterns of income allocation in cross-class families; that is, in families in which the wife is employed in higher level white-collar or professional employment, and the husband in manual work. Following the work of Jan Pahl (1982 and 1983) families are categorised according to their system of money management. The majority of families here employ either a ‘one purse’system based upon joint family funds, or an independent system based upon separate bank accounts. In addition, couples who use an ‘allowance’system, a shared system, or a variant of the independent system with only one-earner are discussed. Whenever possible, qualitative reports from the families interviewed are drawn upon. The paper reveals ways in which gender-specific behaviour may be observed through the study of families’allocative systems. In particular, the wives’propensity to assume responsibility for food shopping, regardless of the couples’sources of income or allocative pattern chosen, is demonstrated. In addition, however, the source of income – specifically cash payments to the husbands – is seen to have an independent effect upon the couples’perceptions of money within the family. The paper concludes with speculation as to why the majority of these affluent families employ a system of joint family funds.     

Characteristic properties of list proportional representation systems

In this paper, three characterizations are given of a rule that models list systems of proportional representation the plurality ranking rule. It is shown that a social preference rule is the plurality ranking rule if and only if it satisfies three independent conditions: consistency, faithfulness, and first score cancellation. It is also shown that first score cancellation is implied by neutrality, anonymity, and topsonlyness. This means a second characterization is found, containing deeper axioms than the previous one. A third characterization contains the notion of top monotonicity. In order to motivate topsonlyness, we show that a scoring seat allocation rule is proof against party fragmentation if and only if it is topsonly. Various other properties of the plurality ranking rule are related to its characterist properties.     

On the complexity of achieving proportional representation

We demonstrate that winner selection in two prominent proportional representation voting systems is a computationally intractable problem—implying that these systems are impractical when the assembly is large. On a different note, in settings where the size of the assembly is constant, we show that the problem can be solved in polynomial time.     

The informational basis of the theory of fair allocation

The theory of fair allocation is often favourably contrasted with the social choice theory in the search for escape routes from Arrow’s impossibility theorem. Its success is commonly attributed to the fact that it is modest in its goal vis-à-vis social choice theory, since it does not aspire for a full-fledged ordering of options, and settles with a subset of ‘fair’ options. We show that its success may rather be attributable to a broadened informational basis thereof. To substantiate this claim, we compare the informational basis of the theory of fair allocation with the informational requirements of social choice theory.This paper is derived from a part of an earlier draft of our paper entitled ‘Informational requirements for social choice in economic environments’. The authors thank A. Trannoy, an associate editor and three referees for comments, and participants at seminars in University of Cergy-Pontoise, University of Rochester, Hitotsubashi University, and Waseda University, and the 5th International Meeting of the Society for Social Choice and Welfare in Alicante. Financial support from the Ministry of Education of Japan through Grant-in-Aid No. 10045010 (‘Economic Institutions and Social Norms: Evolution and Transformation’) and the 21st Century Center of Excellence Project on the Normative Evaluation and Social Choice of Contemporary Economic Systems is gratefully acknowledged.     

Fair division of indivisible items between two people with identical preferences: Envy-freeness, Pareto-optimality, and equity

This paper focuses on the fair division of a set of indivisible items between two people when both have the same linear preference order on the items but may have different preferences over subsets of items. Surprisingly, divisions that are envy-free, Pareto-optimal, and ensure that the less well-off person does as well as possible (i.e., are equitable) can often be achieved. Preferences between subsets are assumed to satisfy axioms of qualitative probability without implying the existence of additive utilities, which is treated as a special case. Algorithms that render fair division practicable are proposed, and their vulnerability to strategic manipulation is investigated. Received: 18 May 1998/Accepted: 2 March 1999     

The importance of survival units for Norbert Elias's figurational perspective

In this paper, we argue that Norbert Elias's concept of survival unit is a distinctive part of the development of his figurational sociology and one of the most consistent contributions to relational thinking. The survival unit is a particular form of figuration which provides security and the material foundations for life such as food and shelter. Every human being is born into a survival unit. This unit is a relational concept which cannot be conceived outside a relationship with other survival units.
By introducing the concept of survival unit Elias overcomes one of the key problems in relational sociology: how to demarcate primary social relations. Elias argues that human societies from very early on have been divided into survival units. These survival units are demarcated and constituted in their relationship to other survival units. Consequently, their boundaries are generated in a confrontation with other survival units.
This relationship can be peaceful or conflict ridden but in the last resort it can end with violent confrontation. Only the survival unit with the ability to defend a domain of sovereignty will survive. This observation places Elias among the few sociologists with an understanding of the role of warfare in social relationships.     

A majorization comparison of apportionment methods in proportional representation

From the inception of the proportional representation movement it has been an issue whether larger parties are favored at the expense of smaller parties in one apportionment of seats as compared to another apportionment. A number of methods have been proposed and are used in countries with a proportional representation system. These apportionment methods exhibit a regularity of order, as discussed in the present paper, that captures the preferential treatment of larger versus smaller parties. This order, namely majorization, permits the comparison of seat allocations in two apportionments. For divisor methods, we show that one method is majorized by another method if and only if their signpost ratios are increasing. This criterion is satisfied for the divisor methods with power-mean rounding, and for the divisor methods with stationary rounding. Majorization places the five traditional apportionment methods in the order as they are known to favor larger parties over smaller parties: Adams, Dean, Hill, Webster, and Jefferson. Received: 5 August 2000/Accepted: 24 October 2001     

A spatial model of political competition and proportional representation

 A spatial model of party competition is studied in which: (i) Parties are supposed to have ideology. By this we mean that their goal is to maximize the welfare of their constituencies. (ii) The policy implemented after the election does not need to coincide with the one proposed by the winner. The policy implemented should be a compromise that considers the proposals made by the different parties. In the case of proportional representation this compromise is modeled as a convex combination of the proposed policies with weights proportional to the number of votes obtained by each party. We provide some existence theorems and compare the equilibrium in our model with the equilibrium that exists under some probabilistic models. It is also shown that proportional representation will create incentives for the parties to announce radical platforms. Received: 17 May 1994/Accepted: 5 March 1996