Fair Division of Mixed Divisible and Indivisible Goods

Abstract

We study the problem of fair division when the resources contain both divisible and indivisible goods. Classic fairness notions such as envy-freeness (EF) and envy-freeness up to one good (EF1) cannot be directly applied to the mixed goods setting. In this work, we propose a new fairness notion envy-freeness for mixed goods (EFM), which is a direct generalization of both EF and EF1 to the mixed goods setting. We prove that an EFM allocation always exists for any number of agents. We also propose efficient algorithms to compute an EFM allocation for two agents and for $n$ agents with piecewise linear valuations over the divisible goods. Finally, we relax the envy-free requirement, instead asking for $\epsilon$-envy-freeness for mixed goods ($\epsilon$-EFM), and present an algorithm that finds an $\epsilon$-EFM allocation in time polynomial in the number of agents, the number of indivisible goods, and $1/\epsilon$.

arXiv commentAppears in the 34th AAAI Conference on Artificial Intelligence (AAAI), 2020

References in corpus (5)

• Approximation Algorithms for Computing Maximin Share Allocations
• Maximum Nash Welfare and Other Stories About EFX
• Fair Division of Mixed Divisible and Indivisible Goods
• Monotonicity and Competitive Equilibrium in Cake-cutting
• Truthful Fair Division without Free Disposal

Cited by in corpus (9)

• Fair Division of Indivisible Goods: Recent Progress and Open Questions
• Fair Division of Mixed Divisible and Indivisible Goods
• Maximin Fairness with Mixed Divisible and Indivisible Goods
• Mixed Fair Division: A Survey
• Almost Envy-Freeness for Groups: Improved Bounds via Discrepancy Theory
• Approval-Based Voting with Mixed Goods
• Envy-freeness and maximum Nash welfare for mixed divisible and indivisible goods
• Fair Multi-Cake Cutting
• Fair Division with Subjective Divisibility