We revisit the classic problem of fair division from a mechanism design perspective and provide an elegant truthful mechanism that yields surprisingly good approximation guarantees for the widely used solution of Proportional Fairness. This solution, which is closely related to Nash bargaining and the competitive equilibrium, is known to be not implementable in a truthful fashion, which has been its main drawback. To alleviate this issue, we propose a new mechanism, which we call the Partial Allocation mechanism, that discards a carefully chosen fraction of the allocated resources in order to incentivize the agents to be truthful in reporting their valuations. This mechanism introduces a way to implement interesting truthful outcomes in settings where monetary payments are not an option. For a multi-dimensional domain with an arbitrary number of agents and items, and for the very large class of homogeneous valuation functions, we prove that our mechanism provides every agent with at least a 1 e � 0.368 fraction of her Proportionally Fair valuation. To the best of our knowledge, this is the first result that gives a constant factor approximation to every agent for the Proportionally Fair solution. To complement this result, we show that no truthful mechanism can guarantee more than 0.5 approximation, even for the restricted class of additive linear valuations. In addition to this, we uncover a connection between the Partial Allocation mechanism and VCG-based mechanism design. We also ask whether better approximation ratios are possible in more restricted settings. In particular, motivated by the massive privatization auction in the Czech republic in the early 90s we provide another mechanism for additive linear valuations that works really well when all the items are highly demanded.
Our setting is closely related to the large topic of fair division or cake-cutting @cite_20 @cite_29 @cite_36 @cite_43 @cite_40 , which has been studied since the 1940's, using the @math interval as the standard representation of a cake. Each agent's preferences take the form of a valuation function over this interval, and then the valuations of unions of subintervals are additive. Note that the class of homogeneous valuation functions of degree one takes us beyond this standard cake-cutting model. Leontief valuations for example, allow for complementarities in the valuations, and then the valuations of unions of subintervals need not be additive. On the other hand, the additive linear valuations setting that we focus on in is very closely related to cake-cutting with piecewise constant valuation functions over the @math interval. Other common notions of fairness that have been studied in this literature are, proportionality It is worth distinguishing the notion of PF from that of proportionality by noting that the latter is a much weaker notion, directly implied by the former. , envy-freeness, and equitability @cite_20 @cite_29 @cite_36 @cite_43 @cite_40 .
@cite_36 @cite_29 @cite_43 @cite_40 @cite_20
1977246877 2022749618 1577069963 1600130330
The challenge of dividing an asset fairly, from cakes to more important properties, is of great practical importance in many situations. Since the famous Polish school of mathematicians (Steinhaus, Banach, and Knaster) introduced and described algorithms for the fair division problem in the 1940s, the concept has been widely popularized. This book gathers into one readable and inclusive source a comprehensive discussion of the state of the art in cake-cutting problems for both the novice and the professional. It offers a complete treatment of all cake-cutting algorithms under all the considered definitions of "fair" and presents them in a coherent, reader-friendly manner. Robertson and Webb have brought this elegant problem to life for both the bright high school student and the professional researcher. Cutting a cake, dividing up the property in an estate, determining the borders in an international dispute - such problems of fair division are ubiquitous. Fair Division treats all these problems and many more through a rigorous analysis of a variety of procedures for allocating goods (or 'bads' like chores), or deciding who wins on what issues, when there are disputes. Starting with an analysis of the well-known cake-cutting procedure, 'I cut, you choose', the authors show how it has been adapted in a number of fields and then analyze fair-division procedures applicable to situations in which there are more than two parties, or there is more than one good to be divided. In particular they focus on procedures which provide 'envy-free' allocations, in which everybody thinks he or she has received the largest portion and hence does not envy anybody else. They also discuss the fairness of different auction and election procedures. 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. 0. Preface 1. Notation and preliminaries 2. Geometric object #1a: the individual pieces set (IPS) for two players 3. What the IPS tells us about fairness and efficiency in the two-player context 4. The general case of n players 5. What the IPS and the FIPS tell us about fairness and efficiency in the n-player context 6. Characterizing Pareto optimality: introduction and preliminary ideas 7. Characterizing Pareto optimality I: the IPS and optimization of convex combinations of measures 8. Characterizing Pareto optimality II: partition ratios 9. Geometric object #2: The Radon-Nikodym set (RNS) 10. Characterizing Pareto optimality III: the RNS, Weller's construction, and w-association 11. The shape of the IPS 12. The relationship between the IPS and the RNS 13. Other issues involving Weller's construction, partition ratios, and Pareto optimality 14. Strong Pareto optimality 15. Characterizing Pareto optimality using hyperreal numbers 16. The multi-cake individual pieces set (MIPS): symmetry restored.