Fair Division Under Cardinality Constraints

Abstract

We consider the problem of fairly allocating indivisible goods, among agents, under cardinality constraints and additive valuations. In this setting, we are given a partition of the entire set of goods---i.e., the goods are categorized---and a limit is specified on the number of goods that can be allocated from each category to any agent. The objective here is to find a fair allocation in which the subset of goods assigned to any agent satisfies the given cardinality constraints. This problem naturally captures a number of resource-allocation applications, and is a generalization of the well-studied (unconstrained) fair division problem. The two central notions of fairness, in the context of fair division of indivisible goods, are envy freeness up to one good (EF1) and the (approximate) maximin share guarantee (MMS). We show that the existence and algorithmic guarantees established for these solution concepts in the unconstrained setting can essentially be achieved under cardinality constraints. Specifically, we develop efficient algorithms which compute EF1 and approximately MMS allocations in the constrained setting. Furthermore, focusing on the case wherein all the agents have the same additive valuation, we establish that EF1 allocations exist and can be computed efficiently even under laminar matroid constraints.

22 pages. A part of these results is accepted at the 27th International Joint Conference on Artificial Intelligence (IJCAI), 2018. The proof of Lemma 5 in the earlier version had a bug. To address the issue and in lieu of general matroids, the current version provides a proof of this result specialized for Laminar matroids

References in corpus (2)

• Fair Allocation of Indivisible Goods: Improvement and Generalization
• Fair Division of a Graph

Cited by in corpus (13)

• Weighted Envy-Freeness in Indivisible Item Allocation
• Almost Envy-Freeness in Group Resource Allocation
• The Price of Fairness for Indivisible Goods
• Almost Envy-Free Allocations with Connected Bundles
• Finding Fair and Efficient Allocations When Valuations Don't Add Up
• The Price of Connectivity in Fair Division
• Assigning a Small Agreeable Set of Indivisible Items to Multiple Players
• Existence and Computation of Maximin Fair Allocations Under Matroid-Rank Valuations
• The Constrained Round Robin Algorithm for Fair and Efficient Allocation
• Computing an Approximately Optimal Agreeable Set of Items
• On the Number of Almost Envy-Free Allocations
• An Improved Approximation Algorithm for Maximin Shares
• Indivisible Mixed Manna: On the Computability of MMS + PO Allocations