同时满足公平与无嫉妒，突破了传统公平分配的局限。
Simultaneous Envy and Equitability Guarantees
- 提出新算法实现无嫉妒与等价性双重保障
- 七人以内二元物品可保证解存在
- 适用于需要多重公平保障的资源分配场景
近期公平分配研究聚焦于同时满足紧密相关的公平概念，或在事前与事后世界中实现单一公平标准。本文研究两个根本不同的公平概念——无嫉妒与等价性之间的兼容性。针对仅含不可分物品或仅含不可分任务的场景，我们分析其松弛形式的同时满足性及其复杂性，揭示了两种场景间的显著差异。我们证明，即使在归一化、可加性估值下，EF1+EQ1也可能不存在。主要算法结果为：对于最多七名参与者的归一化二元物品，可计算出一个满足EF1+EQ1的分配方案。与此形成鲜明对比的是，二元任务对任意数量参与者均能实现更强的EFX+EQX保障，且无需归一化。此外，我们首次探讨跨概念的事前-事后保障问题，探究随机分配能否在事前满足某一公平标准的同时，保持事后的另一公平保障。
原文摘要 · Abstract (English)
Recent work in fair division has focused on either simultaneously satisfying closely related fairness notions or achieving a single notion across the ex-ante and ex-post worlds. We study the compatibility of two fundamentally different fairness notions: envy-freeness and equitability. For indivisible goods-only and chores-only settings, we study the existence and complexity of simultaneously satisfying their relaxations, revealing sharp contrasts between the two settings. We show that EF1+EQ1 may fail to exist even for normalized, additive valuations. Our main algorithmic result computes an EF1+EQ1 allocation for normalized binary goods with at most seven agents. In sharp contrast, binary chores admit the stronger EFX+EQX guarantee for any number of agents, even without normalization. We further initiate the study of cross-notion ex-ante--ex-post guarantees, asking whether randomized allocations can provide ex-ante guarantees for one notion while preserving ex-post guarantees for another.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。