We consider fair allocation of indivisible items under additive utilities. We show that there exists a strongly polynomial-time algorithm that always computes an allocation satisfying Pareto ...optimality and proportionality up to one item even if the utilities are mixed and the agents have asymmetric weights. The result does not hold if either of Pareto optimality or PROP1 is replaced with slightly stronger concepts.
We consider the classic problem of fairly allocating indivisible goods among agents with additive valuation functions and explore the connection between two prominent fairness notions: maximum Nash ...welfare (MNW) and envy-freeness up to any good (EFX). We establish that an MNW allocation is always EFX as long as there are at most two possible values for the goods, whereas this implication is no longer true for three or more distinct values. As a notable consequence, this proves the existence of EFX allocations for these restricted valuation functions. While the efficient computation of an MNW allocation for two possible values remains an open problem, we present a novel algorithm for directly constructing EFX allocations in this setting. Finally, we study the question of whether an MNW allocation implies any EFX guarantee for general additive valuation functions under a natural new interpretation of approximate EFX allocations.
Allocating resources to individuals in a fair manner has been a topic of interest since ancient times, with most of the early mathematical work on the problem focusing on resources that are ...infinitely divisible. Over the last decade, there has been a surge of papers studying computational questions regarding the indivisible case, for which exact fairness notions such as envy-freeness and proportionality are hard to satisfy. One main theme in the recent research agenda is to investigate the extent to which their relaxations, like maximin share fairness (MMS) and envy-freeness up to any good (EFX), can be achieved. In this survey, we present a comprehensive review of the recent progress made in the related literature by highlighting different ways to relax fairness notions, common algorithm design techniques, and the most interesting questions for future research.
In this paper, we study the classic problem of fairly allocating indivisible items with the extra feature that the items lie on a line. Our goal is to find a fair allocation that is contiguous, ...meaning that the bundle of each agent forms a contiguous block on the line. While allocations satisfying the classical fairness notions of proportionality, envy-freeness, and equitability are not guaranteed to exist even without the contiguity requirement, we show the existence of contiguous allocations satisfying approximate versions of these notions that do not degrade as the number of agents or items increases. We also study the efficiency loss of contiguous allocations due to fairness constraints.
Fair Enough Kurokawa, David; Procaccia, Ariel D.; Wang, Junxing
Journal of the ACM,
03/2018, Volume:
65, Issue:
2
Journal Article
Peer reviewed
We consider the problem of fairly allocating indivisible goods, focusing on a recently introduced notion of fairness called maximin share guarantee : each player’s value for his allocation should be ...at least as high as what he can guarantee by dividing the items into as many bundles as there are players and receiving his least desirable bundle. Assuming additive valuation functions, we show that such allocations may not exist, but allocations guaranteeing each player 2/3 of the above value always exist. These theoretical results have direct practical implications.
We study the problem of fairly allocating indivisible goods between groups of agents using the recently introduced relaxations of envy-freeness. We consider the existence of fair allocations under ...different assumptions on the valuations of the agents. In particular, our results cover cases of arbitrary monotonic, responsive, and additive valuations, while for the case of binary valuations we fully characterize the cardinalities of two groups of agents for which a fair allocation can be guaranteed with respect to both envy-freeness up to one good (EF1) and envy-freeness up to any good (EFX). Moreover, we introduce a new model where the agents are not partitioned into groups in advance, but instead the partition can be chosen in conjunction with the allocation of the goods. In this model, we show that for agents with arbitrary monotonic valuations, there is always a partition of the agents into two groups of any given sizes along with an EF1 allocation of the goods. We also provide an extension of this result to any number of groups.
PDF
