arXiv:2609.03846v1 cs.GT

동일한 가법 가치평가 하에서의 EF1 제약 내시 사회후생: 복잡도, 보장, 그리고 실험

EF1-Constrained Nash Social Welfare with Identical Additive Valuations: Complexity, Guarantees, and Experiments

Zih-Sian Yang, Yi-Hao Chen, Yu-Te Kuan, Cheng-Jui Wu, Chuang-Chieh Lin, Po-An Chen

제출 2026-09-03

한국어 초록

우리는 동일한 가법(additive) 가치평가를 가진 에이전트들 사이에서 분할 불가능한 재화를 배분하는 문제를 연구하며, 한 재화 제거 시 시기 없음(envy-freeness up to one good, EF1)과 내시 사회후생(Nash social welfare, NSW)에 초점을 맞춘다. 가법 가치평가 하에서는 NSW를 최대화하는 모든 배분이 EF1이므로, 이에 대응하는 임계값 문제는 동일한 가법 가치평가 하에서 NSW 최대화가 갖는 것으로 알려진 강한 NP-난해성을 그대로 물려받으며 강한 의미의 NP-완전(strongly NP-complete)이다. 따라서 우리는 임의의 EF1 배분이 만족하는 후생 보장에 초점을 맞춘다. 임의의 EF1 배분이 제약 없는 최적 NSW에 대해 $e^{-1/e}$-근사를 달성한다는 사실은 이미 알려져 있지만, 우리는 더 강한 보장을 제공하는 조건들을 규명한다. 균일한(uniform) 가치평가 하에서는 모든 EF1 배분이 NSW 최적이다. $\varepsilon$-소형 아이템(small-item) 조건 하에서는 모든 EF1 배분이 명시적인 근사 비율 $ρ_n(\varepsilon)$을 달성하며, 고정된 $n$에 대해 $\varepsilon\to 0$일 때 $ρ_n(\varepsilon) = 1-O(\varepsilon^2)$을 만족한다. 나아가 모든 아이템 할당 이후에도 EF1이 유지되어야 한다는 더 강한 순차적 요구 조건을 고려한다. 이 설정을 위해 우리는 근위 정책 최적화(Proximal Policy Optimization)로 학습되고 전향적(prospective) EF1 행동 마스킹을 갖춘 심층 강화학습 프레임워크인 \emph{PriorityNet}을 제안한다. 이 마스크는 모든 결정을 EF1을 보존하는 할당으로 제한하여, 사후 보정 없이도 구성적으로 접두 문맥(prefix) 단위의 EF1을 보장한다. 오프라인 및 무작위 순서 온라인 환경 각각에서 3,000개의 테스트 인스턴스($n\in[2,20]$, $m\in[5,100]$)에 걸쳐, PriorityNet은 평균 정규화 $\operatorname{NSW}$ 값으로 각각 $0.9911$과 $0.9701$을 달성한다. 오프라인 최장 처리 시간(Longest Processing Time, LPT) 및 온라인 최소 가치 묶음(least-valued-bundle) 기준선과 비교하면, 인스턴스별 승-패 비율 차이는 각각 $+27.10\%$와 $+17.87\%$이며, 오프라인 기준선의 평균 정규화 후생과는 소수점 넷째 자리까지 일치하고 온라인 평균은 $0.9694$에서 $0.9701$로 소폭 향상된다.

원문 초록

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 condition, every EF1 allocation achieves an explicit approximation ratio $ρ_n(\varepsilon)$ satisfying $ρ_n(\varepsilon) = 1-O(\varepsilon^2)$ as $\varepsilon\to 0$ for fixed $n$. We further consider the stronger sequential requirement that EF1 be maintained after every item assignment. For this setting, we propose \emph{PriorityNet}, a deep reinforcement learning framework trained using Proximal Policy Optimization and equipped with prospective EF1 action masking. The mask restricts every decision to assignments that preserve EF1, thereby guaranteeing prefix-wise EF1 by construction without post-processing repair. Across 3,000 test instances in each of the offline and random-order online regimes ($n\in[2,20]$ and $m\in[5,100]$), PriorityNet attains mean normalized $\operatorname{NSW}$ values of $0.9911$ and $0.9701$, respectively. Relative to offline Longest Processing Time (LPT) and online least-valued-bundle baselines, it achieves instance-wise win-minus-loss rates of $+27.10\%$ and $+17.87\%$, while matching the offline baseline's mean normalized welfare to four decimal places and modestly improving the online mean from $0.9694$ to $0.9701$.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2609.03846v1제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.