揭示公平分配中PMMS与EFX的本质差异,给出三类情形下可实现的高效算法。
Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division
- 构造三主体实例证明PMMS分配不存在,首次严格区分PMMS与EFX
- 在个性化双值、二元可分、成对需求等三类场景下,均存在多项式时间算法
- 结果适用于物品、任务及混合资源分配,无需单调性假设
我们研究不可分物品的公平分配问题,深入探讨被广泛视为公平分配核心难题的EFX问题,以及比EFX更强的PMMS问题。首先,我们构造了一个包含三个参与方、两个单调估值和一个加性估值的实例,其中不存在任何PMMS分配。由于在相同条件下已知存在EFX分配,这确立了PMMS与EFX之间的正式分离。我们证明了三种重要特殊情形下公平分配的存在性:对于个性化双值估值(每位参与者对每项物品的估值仅取两个值),存在EFX分配;当较大值可被较小值整除时,同样存在PMMS分配;对于二元值且满足MMS可行性条件的估值(每个物品集合的价值为0或1),也存在PMMS分配。值得注意的是,该结果不依赖于估值的单调性,因此适用于任务和混合物资分配。最后,我们研究了一类称为成对需求的估值,它扩展了经典单位需求模型,允许每位参与者从至多两项物品中获得价值,并证明在此情形下存在PMMS分配。所有证明均为构造性,并给出了多项式时间算法。
原文摘要 · Abstract (English)
We study the fair division of indivisible items and provide new insights into the EFX problem, which is widely regarded as the central open question in fair division, and the PMMS problem, a strictly stronger variant of EFX. Our first result constructs a three-agent instance with two monotone valuations and one additive valuation in which no PMMS allocation exists. Since EFX allocations are known to exist under these assumptions, this establishes a formal separation between EFX and PMMS. We prove existence of fair allocations for three important special cases. We show that EFX allocations exist for personalized bivalued valuations, where for each agent $i$ there exist values $a_i > b_i$ such that agent $i$ assigns value $v_i(\{g\}) \in \{a_i, b_i\}$ to each good $g$. We establish an analogous existence result for PMMS allocations when $a_i$ is divisible by $b_i$. We also prove that PMMS allocations exist for binary-valued MMS-feasible valuations, where each bundle $S$ has value $v_i(S) \in \{0, 1\}$. Notably, this result holds even without assuming monotonicity of valuations and thus applies to the fair division of chores and mixed manna. Finally, we study a class of valuations called pair-demand valuations, which extend the well-studied unit-demand valuations to the case where each agent derives value from at most two items, and we show that PMMS allocations exist in this setting. Our proofs are constructive, and we provide polynomial-time algorithms for all three existence results.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。