Recently, the problem of allocating one resource per agent with initial endowments () has seen a renewed interest: indeed, while in the general domain Top Trading Cycle is known to be the only procedure guaranteeing Pareto-optimality, individual rationality, and strategy proofness, the situation differs in single-peaked domains. Bade (2019) presented the Crawler, an alternative procedure enjoying the same properties (with the additional advantage of being implementable in obviously dominant strategies); while (2015) showed that allowing mutually beneficial swap-deals among the agents was already enough to guarantee Pareto-optimality. In this paper we significantly deepen our understanding of this decentralized procedures: we show in particular that the single-peaked domains happen to be maximal'' if one wishes to guarantee this convergence property. Interestingly, we also observe that the set of allocations reachable by swap-deals always contains the outcome of the Crawler. To further investigate how these different mechanisms compare, we pay special attention to the average and minimum rank of the resource obtained by the agents in the outcome allocation. We provide theoretical bounds on the loss potentially induced by these procedures with respect to these criteria, and complement these results with an extensive experimental study which shows how different variants of swap dynamics behave. In fact, even the simplest dynamics exhibit very good results, and it is possible to further guide the process towards our objectives, if one is ready to sacrifice a bit in terms of decentralization. On our way, we also show that a simple variant of the Crawler allows to check efficiently that an allocation is Pareto-optimal in single-peaked domains.
The theory of fair division has been introduced by @cite_27 who defined "the Problem of Fair Division". This seminal work has led to an extensive literature in economics (see @cite_3 @cite_26 or @cite_24 for complete surveys). Most of these works focus on settings with divisible resources and or allow for monetary transfers between the agents. @cite_4 and @cite_22 are among the first ones to consider indivisible resources. While in the former an additional divisible resource plays the role of money, in the latter all the resources are assumed to be indivisible.
@cite_26 @cite_4 @cite_22 @cite_3 @cite_24 @cite_27
1577069963 2152907289 2029467699 2885811088
The concept of fair division is as old as civil society itself. Aristotle's "equal treatment of equals" was the first step toward a formal definition of distributive fairness. The concept of collective welfare, more than two centuries old, is a pillar of modern economic analysis. Reflecting fifty years of research, this book examines the contribution of modern microeconomic thinking to distributive justice. Taking the modern axiomatic approach, it compares normative arguments of distributive justice and their relation to efficiency and collective welfare. The book begins with the epistemological status of the axiomatic approach and the four classic principles of distributive justice: compensation, reward, exogenous rights, and fitness. It then presents the simple ideas of equal gains, equal losses, and proportional gains and losses. The book discusses three cardinal interpretations of collective welfare: Bentham's "utilitarian" proposal to maximize the sum of individual utilities, the Nash product, and the egalitarian leximin ordering. It also discusses the two main ordinal definitions of collective welfare: the majority relation and the Borda scoring method. The Shapley value is the single most important contribution of game theory to distributive justice. A formula to divide jointly produced costs or benefits fairly, it is especially useful when the pattern of externalities renders useless the simple ideas of equality and proportionality. The book ends with two versatile methods for dividing commodities efficiently and fairly when only ordinal preferences matter: competitive equilibrium with equal incomes and egalitarian equivalence. The book contains a wealth of empirical examples and exercises. Abstract An economic model of trading in commodities that are inherently indivisible, like houses, is investigated from a game-theoretic point of view. The concepts of balanced game and core are developed, and a general theorem of Scarf's is applied to prove that the market in question has a nonempty core, that is, at least one outcome that no subset of traders can improve upon. A number of examples are discussed, and the final section reviews a series of other models involving indivisible commodities, with references to the literature. Governments and institutions, perhaps even more than markets, determine who gets what in our society. They make the crucial choices about who pays the taxes, who gets into college, who gets medical care, who gets drafted, where the hazardous waste dump is sited, and how much we pay for public services. Debate about these issues inevitably centres on the question of whether the solution is "fair". In "Equity: In Theory and Practice", H. Peyton Young offers a systematic explanation of what we mean by fairness in distributing public resources and burdens, and applies the theory to actual cases. Young begins by reviewing some of the major theories of social justice, showing that none of them explains how societies resolve distributive problems in practice. He then suggests an alternative approach to analyzing fairness in concrete situations: equity, he argues, does not boil down to a single formula, but represents a balance between competing principles of need, desert, and social utility. The studies Young uses to illustrate his approach include the design of income tax schedules, priority schemes for allocating scarce medical resources, formulas for distributing political representation, and criteria for setting fees for public services. Each represents a unique blend of historical perspective, rigorous analysis, and an emphasis on practical solutions. In fair division of indivisible goods, using sequences of sincere choices (or picking sequences) is a natural way to allocate the objects. The idea is as follows: at each stage, a designated agent picks one object among those that remain. Another intuitive way to obtain an allocation is to give objects to agents in the first place, and to let agents exchange them as long as such "deals" are beneficial. This paper investigates these notions, when agents have additive preferences over objects, and unveils surprising connections between them, and with other efficiency and fairness notions. In particular, we show that an allocation is sequenceable if and only if it is optimal for a certain type of deals, namely cycle deals involving a single object. Furthermore, any Pareto-optimal allocation is sequenceable, but not the converse. Regarding fairness, we show that an allocation can be envy-free and non-sequenceable, but that every competitive equilibrium with equal incomes is sequenceable. To complete the picture, we show how some domain restrictions may affect the relations between these notions. Finally, we experimentally explore the links between the scales of efficiency and fairness.