Democratic Fair Allocation of Indivisible Goods

Abstract

We study the problem of fairly allocating indivisible goods to groups of agents. Agents in the same group share the same set of goods even though they may have different preferences. Previous work has focused on unanimous fairness, in which all agents in each group must agree that their group's share is fair. Under this strict requirement, fair allocations exist only for small groups. We introduce the concept of democratic fairness, which aims to satisfy a certain fraction of the agents in each group. This concept is better suited to large groups such as cities or countries. We present protocols for democratic fair allocation among two or more arbitrarily large groups of agents with monotonic, additive, or binary valuations. For two groups with arbitrary monotonic valuations, we give an efficient protocol that guarantees envy-freeness up to one good for at least $1/2$ of the agents in each group, and prove that the $1/2$ fraction is optimal. We also present other protocols that make weaker fairness guarantees to more agents in each group, or to more groups. Our protocols combine techniques from different fields, including combinatorial game theory, cake cutting, and voting.

Appears in the 27th International Joint Conference on Artificial Intelligence and the 23rd European Conference on Artificial Intelligence (IJCAI-ECAI), 2018

References in corpus (11)

• Fairly Allocating Contiguous Blocks of Indivisible Items
• Asymptotic Existence of Fair Divisions for Groups
• Approximate Maximin Shares for Groups of Agents
• Fair allocation of combinations of indivisible goods and chores
• Social Integration in Two-Sided Matching Markets
• Fair Cake-Cutting among Families
• Assigning a Small Agreeable Set of Indivisible Items to Multiple Players
• Computing an Approximately Optimal Agreeable Set of Items
• Redividing the Cake
• Lecture Notes on Fair Division
• Discrete Envy-free Division of Necklaces and Maps

Cited by in corpus (13)

• Fair Division of Indivisible Goods: Recent Progress and Open Questions
• Weighted Envy-Freeness in Indivisible Item Allocation
• The Price of Fairness for Indivisible Goods
• Finding Fair and Efficient Allocations When Valuations Don't Add Up
• Closing Gaps in Asymptotic Fair Division
• The Price of Connectivity in Fair Division
• Computing Welfare-Maximizing Fair Allocations of Indivisible Goods
• Competitive Equilibrium For Almost All Incomes: Existence and Fairness
• How to Cut a Cake Fairly: A Generalization to Groups
• On the Number of Almost Envy-Free Allocations
• Almost Envy-Freeness for Groups: Improved Bounds via Discrepancy Theory
• Approximate Group Fairness for Clustering
• Ordinal Maximin Guarantees for Group Fair Division