Fair division has long been an important problem in the economics literature. In this note, we consider the existence of proportionally fair allocations of indivisible goods, i.e., allocations of indivisible goods in which every agent gets at least her proportionally fair share according to her own utility function. We show that when utilities are additive and utilities for individual goods are drawn independently at random from a distribution, proportionally fair allocations exist with high probability if the number of goods is a multiple of the number of agents or if the number of goods grows asymptotically faster than the number of agents.
We now make some comments on the relation between our results and those of @cite_11 concerning envy-free allocations. As we will later elaborate, proportional fairness is a weaker notion of fairness than envy-freeness, i.e., envy-free allocations are also proportionally fair when utilities are additive. showed that under additive utilities, envy-free allocations are unlikely to exist when the number of goods is larger than the number of agents by a linear fraction. Theorem contrasts that result by showing that proportionally fair allocations are likely to exist even when the number of goods is the same as the number of agents.
@cite_11
2403056628
The fair division of indivisible goods has long been an important topic in economics and, more recently, computer science. We investigate the existence of envyfree allocations of indivisible goods, that is, allocations where each player values her own allocated set of goods at least as highly as any other player's allocated set of goods. Under additive valuations, we show that even when the number of goods is larger than the number of agents by a linear fraction, envy-free allocations are unlikely to exist.We then show that when the number of goods is larger by a logarithmic factor, such allocations exist with high probability. We support these results experimentally and show that the asymptotic behavior of the theory holds even when the number of goods and agents is quite small. We demonstrate that there is a sharp phase transition from nonexistence to existence of envy-free allocations, and that on average the computational problem is hardest at that transition.