כתבה
arXiv cs.LG ·
EF1-Constrained Nash Social Welfare
EF1-Constrained Nash Social Welfare with Identical Additive Valuations: Complexity, Guarantees, and Experiments
חוקרים את האלוקציה של סחורות בלתי ניתנות לחלוקה בין סוכנים עם ערכים נוספים זהים, במיקוד על EF1 ו-Nash Social Welfare. הם מציעים את PriorityNet, מסגרת לימוד תגמול עמוק.
תקציר מקורי באנגליתarXiv:2609.03846v2 Announce Type: replace-cross Abstract: We study the allocation of indivisible goods among agents with identical additive valuations, focusing on envy-freeness up to one good (EF1) and Nash social welfare (NSW). Since every maximum-NSW allocation is EF1 under additive valuations, the associated threshold problem inherits the known strong NP-hardness of NSW maximization under identical additive valuations and is strongly NP-complete. We therefore focus on welfare guarantees satisfied by arbitrary EF1 allocations. Although every such allocation is known to achieve an $e^{-1/e}$-approximation to the unrestricted optimal NSW, we identify conditions yielding stronger guarantees. Under uniform valuations, every EF1 allocation is NSW-optimal. Under an $\varepsilon$-small-item co
קרא במקור המקורי
arxiv.org
פתח כתבה מקורית