论文标题
在词典偏好下的商品和杂务的混合物相当分裂
Fairly Dividing Mixtures of Goods and Chores under Lexicographic Preferences
论文作者
论文摘要
我们研究具有\ emph {词素图}偏好的代理商中不可分割的商品和杂务的公平分配 - 累加估值的子类。与仅商品环境形成鲜明对比的是，我们表明，满足\ emph {eymph {Envy-fo to Athon Item}（EFX）的分配可能不存在\ Emph {Abjocy {客观}商品和家务的混合。据我们所知，这种负面结果提供了\ emph {first} efx的反例（任何亚域的添加剂估值）。为了补充这种不存在的结果，我们确定了一类具有（可能是主观的）混合项目的实例，其中EFX和Pareto最佳分配始终存在并且可以有效地计算。当公平要求放松到\ emph {maximin share}（mms）时，我们将显示\ emph {any}混合实例的积极存在和计算。从更广泛的角度来看，我们的工作研究了混合项目和仅杂货的实例的公平和有效分配的存在和计算，并突出了这些问题的额外难度 - {à} - vis kis-fores of货物。
We study fair allocation of indivisible goods and chores among agents with \emph{lexicographic} preferences -- a subclass of additive valuations. In sharp contrast to the goods-only setting, we show that an allocation satisfying \emph{envy-freeness up to any item} (EFX) could fail to exist for a mixture of \emph{objective} goods and chores. To our knowledge, this negative result provides the \emph{first} counterexample for EFX over (any subdomain of) additive valuations. To complement this non-existence result, we identify a class of instances with (possibly subjective) mixed items where an EFX and Pareto optimal allocation always exists and can be efficiently computed. When the fairness requirement is relaxed to \emph{maximin share} (MMS), we show positive existence and computation for \emph{any} mixed instance. More broadly, our work examines the existence and computation of fair and efficient allocations both for mixed items as well as chores-only instances, and highlights the additional difficulty of these problems vis-{à}-vis their goods-only counterparts.
