Asymptotic Existence of Fair Divisions for Groups

Abstract

The problem of dividing resources fairly occurs in many practical situations and is therefore an important topic of study in economics. In this paper, we investigate envy-free divisions in the setting where there are multiple players in each interested party. While all players in a party share the same set of resources, each player has her own preferences. Under additive valuations drawn randomly from probability distributions, we show that when all groups contain an equal number of players, a welfare-maximizing allocation is likely to be envy-free if the number of items exceeds the total number of players by a logarithmic factor. On the other hand, an envy-free allocation is unlikely to exist if the number of items is less than the total number of players. In addition, we show that a simple truthful mechanism, namely the random assignment mechanism, yields an allocation that satisfies the weaker notion of approximate envy-freeness with high probability.

To appear in the 10th International Symposium on Algorithmic Game Theory (SAGT), 2017

References in corpus (2)

• On Truthful Mechanisms for Maximin Share Allocations
• Asymptotic Existence of Proportionally Fair Allocations

Cited by in corpus (18)

• Fairly Allocating Contiguous Blocks of Indivisible Items
• Almost Envy-Freeness in Group Resource Allocation
• Democratic Fair Allocation of Indivisible Goods
• Approximate Maximin Shares for Groups of Agents
• Closing Gaps in Asymptotic Fair Division
• Fair Cake-Cutting among Families
• Envy-Free Classification
• When Do Envy-Free Allocations Exist?
• Assigning a Small Agreeable Set of Indivisible Items to Multiple Players
• Computing an Approximately Optimal Agreeable Set of Items
• Efficient Fair Division with Minimal Sharing
• Almost Envy-Freeness for Groups: Improved Bounds via Discrepancy Theory
• Cutting a Cake Fairly for Groups Revisited
• Envy-Free and Pareto-Optimal Allocations for Agents with Asymmetric Random Valuations
• Your College Dorm and Dormmates: Fair Resource Sharing with Externalities
• Asymptotic Analysis of Weighted Fair Division
• Asymptotic Fair Division: Chores Are Easier Than Goods
• Ordinal Maximin Guarantees for Group Fair Division