arXiv 2512.22552
초록 정보가 없습니다.
이 이메일 도메인이 관측된 논문 2건
초록 정보가 없습니다.
EF1-Constrained Nash Social Welfare with Identical Additive Valuations: Complexity, Guarantees, and Experiments
우리는 동일한 가법(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$로 소폭 향상된다.