Fair Division of Mixed Divisible and Indivisible Goods

We study the problem of fair division when the set of resources contains 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 this 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 with additive valuations. We also propose efficient algorithms to compute an EFM allocation for two agents with general additive valuations and for n agents with piecewise linear valuations over the divisible goods. Finally, we relax the envy-freeness requirement, instead asking for ǫ-envy-freeness for mixed goods (ǫ-EFM), and present an efficient algorithm that finds an ǫ-EFM allocation. * A preliminary version appeared in Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI) [Bei et al., 2020b]. Compared to the conference version, this journal version fixes a bug in the proof of Theorem 3.6 and includes a new section (Section 6) that discusses how to combine the newly proposed fairness notion together with economic efficiency considerations.