Almost Envy-Freeness in Group Resource Allocation
arXiv:1901.08463 · doi:10.1016/j.tcs.2020.07.008
Abstract
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.
arXiv commentAppears in the 28th International Joint Conference on Artificial Intelligence (IJCAI), 2019
References in corpus (10)
- Maximum Nash Welfare and Other Stories About EFX
- Fairly Allocating Contiguous Blocks of Indivisible Items
- Asymptotic Existence of Fair Divisions for Groups
- Fair Division Under Cardinality Constraints
- Approximate Maximin Shares for Groups of Agents
- Envy-free Relaxations for Goods, Chores, and Mixed Items
- Assigning a Small Agreeable Set of Indivisible Items to Multiple Players
- Computing an Approximately Optimal Agreeable Set of Items
- On the Number of Almost Envy-Free Allocations
- Envy-Free Cake-Cutting among Families
Cited by in corpus (19)
- Fair Division of Indivisible Goods: Recent Progress and Open Questions
- Weighted Envy-Freeness in Indivisible Item Allocation
- Maximum Nash Welfare and Other Stories About EFX
- The Price of Fairness for Indivisible Goods
- Finding Fair and Efficient Allocations When Valuations Don't Add Up
- On Maximum Weighted Nash Welfare for Binary Valuations
- Closing Gaps in Asymptotic Fair Division
- The Price of Connectivity in Fair Division
- (Almost Full) EFX Exists for Four Agents (and Beyond)
- Fair allocation of a multiset of indivisible items
- Fairly Allocating Many Goods with Few Queries
- Mixed Fair Division: A Survey
- Ordinal Maximin Share Approximation for Goods
- Almost Envy-Freeness for Groups: Improved Bounds via Discrepancy Theory
- Cutting a Cake Fairly for Groups Revisited
- Multi-Agent Systems for Computational Economics and Finance
- Approximate Group Fairness for Clustering
- Your College Dorm and Dormmates: Fair Resource Sharing with Externalities
- Ordinal Maximin Guarantees for Group Fair Division