研究不可分物品公平分配中EFX解的最少数量及变体，揭示其存在性阈值。
Understanding EFX Allocations: Counting and Variants
- 分析物品略多于人数时的EFX分配数量，探索存在性边界。
- 证明二元加性价值下WEFX可多项式时间计算，两人为首例常数近似。
- 提出适用于广义单调估值的EFX+新变体，拓展公平分配理论。
envy-freeness up to any good (EFX) 是不可分物品公平分配中一个受欢迎且重要的公平性属性，其普遍存在的问题至今仍悬而未决。本文研究给定实例中EFX分配的最小数量，认为这一方法能为EFX分配的存在性和计算提供深刻洞见。我们聚焦于物品数量仅略多于参与者的受限情形，并将分析扩展至加权EFX（WEFX）以及一种针对一般单调估值的新变体EFX+。在此过程中，我们确定了满足这些公平性概念的分配存在的过渡阈值。值得注意的是，我们解决了WEFX的开放问题：在二元加性估值下证明其可多项式时间计算，并为两人情形建立了首个常数因子近似算法。
原文摘要 · Abstract (English)
Envy-freeness up to any good (EFX) is a popular and important fairness property in the fair allocation of indivisible goods, of which its existence in general is still an open question. In this work, we investigate the problem of determining the minimum number of EFX allocations for a given instance, arguing that this approach may yield valuable insights into the existence and computation of EFX allocations. We focus on restricted instances where the number of goods slightly exceeds the number of agents, and extend our analysis to weighted EFX (WEFX) and a novel variant of EFX for general monotone valuations, termed EFX+. In doing so, we identify the transition threshold for the existence of allocations satisfying these fairness notions. Notably, we resolve open problems regarding WEFX by proving polynomial-time computability under binary additive valuations, and establishing the first constant-factor approximation for two agents.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。