Asymptotic Existence of Proportionally Fair Allocations

Abstract

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.

Cited by in corpus (9)

• Fairly Allocating Contiguous Blocks of Indivisible Items
• Asymptotic Existence of Fair Divisions for Groups
• Approximate Maximin Shares for Groups of Agents
• Closing Gaps in Asymptotic Fair Division
• When Do Envy-Free Allocations Exist?
• Envy-Free and Pareto-Optimal Allocations for Agents with Asymmetric Random Valuations
• Asymptotic Analysis of Weighted Fair Division
• Complexity of Round-Robin Allocation with Potentially Noisy Queries
• Asymptotic Fair Division: Chores Are Easier Than Goods