两人的公平分配中，7个物品内可同时实现无嫉妒与最优，8个则不行。
Fair Division with Strictly Increasing Valuations: A Tight Threshold for Two-Agent EF1 and PO
- 通过严格递增的偏好值，证明7个物品内可兼顾公平与效率
- 8个物品时存在反例：所有公平分配均非最优
- 适用于研究公平分配机制的设计者和算法博弈论学者
我们研究严格正边际价值是否能恢复不可分物品下无嫉妒至多一个物品（EF1）与帕累托最优（PO）的兼容性。对于两人情形，我们确定了物品数量的精确阈值：任意不超过七个物品、且具有严格递增估值的实例，均存在同时满足EF1与PO的分配，无需子模性假设。相反，我们构造了一个八物品实例，其估值为归一化、整数、严格递增且子模，其中每个EF1分配均被严格帕累托支配。因此，八件物品是两人反例的必要且充分条件。最后，我们强化了Chandramouleeswaran和Nimbhorkar（2026）的三人情形下NP难性结果：即使零边际值仅限于八个固定的人物对（全部涉及同一人），判定是否存在EF1与PO分配依然为NP难。
原文摘要 · Abstract (English)
We study whether strictly positive marginal values restore the compatibility of envy-freeness up to one good (EF1) and Pareto optimality (PO) for indivisible goods. For two agents, we identify the exact threshold in the number of goods. Every instance with at most seven goods and strictly increasing valuations admits an allocation that is both EF1 and PO, without any submodularity assumption. In contrast, we construct an eight-good instance with normalized, integer-valued, strictly increasing, submodular valuations in which every EF1 allocation is strictly Pareto dominated. Thus, eight goods are necessary and sufficient for a two-agent counterexample. Finally, we strengthen the three-agent NP-hardness result of Chandramouleeswaran and Nimbhorkar (2026): deciding whether an EF1 and PO allocation exists remains NP-hard for normalized, integer-valued, monotone submodular valuations even when zero marginals are confined to eight fixed agent-good pairs, all involving a single agent.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。