证明特定图结构下可高效构造无嫉妒分配，解决公平分配难题。
EFX Allocation In (Multi)Hypergraphs
- 用高阶图建模资源与人关系，限制价值仅存在于边端点间。
- 当图的围长≥4时，任意单调估值下均存在可多项式构造的EFX分配。
- 适用于多超图场景，适合研究公平分配与组合优化的学者。
我们研究在异质单调估值下对不可分物品的公平分配问题，以无嫉妒至任意物品（EFX）为公平标准。寻找是否存在始终满足EFX的分配，即使对于具有加性估值的参与者，仍是公平分配领域的重大开放问题。Christodoulou等人（2023）引入了（多）超图设置：参与者和物品分别由图的顶点和边表示，且只有边的端点对边有非零边际价值。本文证明：对于围长至少为4的超图，以及具有通用单调估值的参与者，总存在一个可多项式时间构造的EFX分配。我们将该方法推广至多超图情形：只要存在一个顶点，其关联边的重数不超过边大小减2，则该类多超图上也总存在一个EFX分配，但此时构造需伪多项式时间。
原文摘要 · Abstract (English)
We study fair allocations of indivisible goods among agents with heterogeneous monotone valuations. As fair we consider the allocations that are envy-free-up-to-any-good (EFX). Finding if EFX alloca- tions always exist, even for agents with additive valuations, is a major open problem in Fair Division. Christodoulou et al. (2023) introduced the (multi-hyper)graph setting, where agents and goods are represented by vertices and edges of a graph, respectively, and only the endpoints of an edge may have non-zero marginal value for it. We show that for hypergraphs with girth at least 4 and agents with general monotone valuations there always exists an EFX allocation and can be constructed in polynomial time. We generalize our approach to also show that multi-hypergraphs with girth (on the simple hypergraph) at least 4 always admit an EFX allocation, as long as there exists a single vertex whose incident edges have multiplicity at most the size of that edge minus 2; our construction in this case needs pseudo-polynomial time.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。