Fair Division of Mixed Divisible and Indivisible Goods

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