Approximate Maximin Shares for Groups of Agents

Abstract

We investigate the problem of fairly allocating indivisible goods among interested agents using the concept of maximin share. Procaccia and Wang showed that while an allocation that gives every agent at least her maximin share does not necessarily exist, one that gives every agent at least $2/3$ of her share always does. In this paper, we consider the more general setting where we allocate the goods to groups of agents. The agents in each group share the same set of goods even though they may have conflicting preferences. For two groups, we characterize the cardinality of the groups for which a constant factor approximation of the maximin share is possible regardless of the number of goods. We also show settings where an approximation is possible or impossible when there are several groups.

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

References in corpus (4)

• On Truthful Mechanisms for Maximin Share Allocations
• Asymptotic Existence of Fair Divisions for Groups
• Truthful Allocation Mechanisms Without Payments: Characterization and Implications on Fairness
• Asymptotic Existence of Proportionally Fair Allocations

Cited by in corpus (14)

• Fair Division of Indivisible Goods: Recent Progress and Open Questions
• Multiple Birds with One Stone: Beating $1/2$ for EFX and GMMS via Envy Cycle Elimination
• Maximum Nash Welfare and Other Stories About EFX
• Almost Envy-Freeness in Group Resource Allocation
• The Price of Fairness for Indivisible Goods
• Democratic Fair Allocation of Indivisible Goods
• Closing Gaps in Asymptotic Fair Division
• Fair Cake-Cutting among Families
• When Do Envy-Free Allocations Exist?
• Computing an Approximately Optimal Agreeable Set of Items
• Assigning a Small Agreeable Set of Indivisible Items to Multiple Players
• Maximin Fairness with Mixed Divisible and Indivisible Goods
• Almost Envy-Freeness for Groups: Improved Bounds via Discrepancy Theory
• Ordinal Maximin Guarantees for Group Fair Division