論文の概要: EF1-Constrained Nash Social Welfare with Identical Additive Valuations: Complexity, Guarantees, and Experiments

• arxiv url: http://arxiv.org/abs/2609.03846v2
• Date: Thu, 10 Sep 2026 06:41:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-11 19:20:15.674687
• Title: EF1-Constrained Nash Social Welfare with Identical Additive Valuations: Complexity, Guarantees, and Experiments
• Title（参考訳）: EF1-Constrained Nash Social Welfare with Identical Additive Valuations: Complexity, Guarantees, Experiments
• Abstract要約: 同一付加価値のエージェント間での異種商品の割り当てについて検討する。 我々は、任意のEF1割り当てで満たされた福祉保証に焦点を当てる。
• 参考スコア（独自算出の注目度）: 4.5274244793371325
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 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$.
• Abstract（参考訳）: 本研究では,同一の付加価値を持つエージェント間での異種商品の配分について検討し,一善(EF1)とナッシュ社会福祉(NSW)に焦点をあてた。 すべての最大NSW割り当ては加法評価の下でEF1であるため、関連するしきい値問題はNSWの最大化の既知の強いNP硬度を同一の加法評価で継承し、NP完全である。 したがって、任意のEF1割り当てで満たされた福祉保証に焦点をあてる。 そのような割り当てはすべて、制限のない最適NSWに対して$e^{-1/e}$-approximationを達成することが知られているが、より強い保証をもたらす条件を特定する。 均一な評価では、EF1の割り当てはすべてNSW最適化である。 1-O(\varepsilon^2)$ as $\varepsilon\to 0$ for fixed $n$. EF1 アロケーションは、$ρ_n(\varepsilon)= 1-O(\varepsilon^2)$を満足する明示的な近似比$ρ_n(\varepsilon)$を達成する。 さらに、アイテムの割り当て毎にEF1が維持されるという、より強いシーケンシャルな要求についても検討する。 そこで本研究では,近似ポリシー最適化を用いた深層強化学習フレームワークである \emph{PriorityNet} を提案する。 マスクはEF1を保存する代入に全ての決定を制限し、前置的なEF1を後処理の修理なしに構成によって保証する。 オフラインおよびランダムオーダーのオンラインレシスタンス($n\in[2,20]$と$m\in[5,100]$)の3000を超えるテストインスタンスにおいて、プライオリティNetは、それぞれ0.9911$と0.9701$の値で正規化された$\operatorname{NSW}$の平均値を得る。 オフラインのLongest Processing Time (LPT) やオンラインの最小バンドルベースラインとは対照的に、オフラインのベースラインの平均正規化福祉を4つの10の場所へ、オンライン平均を0.9694ドルから0.9701ドルに微妙に改善しながら、インスタンス単位のウィン・ミナス・ロスレートが$+27.10\%$と$+17.87\%$を達成している。

関連論文リスト

• Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids: From Robust Offline Optimization to Full-Bandit Learning [55.29259818039367]
  オフラインアルゴリズムに任意の制御値オラクルが与えられるとき, 一般のマトロイドに対する非負のサブモジュラー対象について検討する。 本アルゴリズムは,非単調な目的に対して1/e$,単調な目的に対して1/e$の制限係数を保持する。 結果として、オフラインからオフラインへの還元は、一般的なマトロイド制約のサブモジュラー報酬に対するシングルバンドCMABアルゴリズムをもたらす。
  論文  参考訳（メタデータ） (2026-08-12T14:54:15Z)
• Multi-Agent Stage-wise Conservative Linear Bandits [2.2557806157585834]
  マルチエージェントネットワーク設定における線形帯域幅問題について検討する。 エージェントは段階的に保守的な制約を満たす必要がある。 我々は,行動選択とコンセンサス構築フェーズの交互に行うエピソードアルゴリズムMA-SCLUCBを提案する。
  論文  参考訳（メタデータ） (2025-10-01T07:29:18Z)
• Online Fair Division for Personalized $2$-Value Instances [51.278096593080456]
  オンラインフェアディビジョン(オンラインフェアディビジョン)では,商品が一度に1つずつ到着し,定額のエージェントが配置されている。 善が現れると、各エージェントの持つ値が明らかになり、エージェントの1つに即時かつ不可逆的に割り当てられなければならない。 我々は、よく知られた公平性の概念に関して、最悪の場合の保証を得る方法を示す。
  論文  参考訳（メタデータ） (2025-05-28T09:48:16Z)
• Smoothed Normalization for Efficient Distributed Private Optimization [54.197255548244705]
  フェデレートされた学習は、参加者のプライバシを備えた機械学習モデルを可能にする。 トレーニングやフィードバックのない問題に対して、差分にプライベートな分散手法は存在しない。 証明可能な収束保証付き分散アルゴリズム$alpha$-$sf NormEC$を導入する。
  論文  参考訳（メタデータ） (2025-02-19T07:10:32Z)
• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  我々は$f$-divergence-regularized offline policy learningを分析する。 逆Kullback-Leibler (KL) の発散に対して、単極集中性の下での最初の$tildeO(epsilon-1)$サンプル複雑性を与える。 これらの結果は,$f$-divergence-regularized policy learningの包括的理解に向けて大きな一歩を踏み出したものと考えられる。
  論文  参考訳（メタデータ） (2025-02-09T22:14:45Z)
• Resource Allocation under the Latin Square Constraint [3.8028747063484585]
  我々は、$n$のラウンドで$n$のエージェント間で$n$の分割不可能なアイテムを割り当てる問題を提起する。 この制約は、各エージェントがラウンド毎に1つ以上のアイテムを受信し、各アイテムを最大1回受信することを保証します。 スケジューリング、リソース管理、実験的設計のような現実世界のアプリケーションは、アロケーションにおける公平性やバランス性を満たすためにラテン四角い制約を必要とする。
  論文  参考訳（メタデータ） (2025-01-11T10:53:48Z)
• Dividing Good and Better Items Among Agents with Bivalued Submodular Valuations [20.774185319381985]
  本稿では,2値のサブモジュラー評価を持つエージェント間で,分割不可能な商品の集合を適切に割り当てる問題について検討する。 我々は、レキシミンとMNWの割り当てが1つの利益まで自由になされることは保証されていないことを示す。
  論文  参考訳（メタデータ） (2023-02-06T19:41:28Z)
• Towards Painless Policy Optimization for Constrained MDPs [46.12526917024248]
  我々は、無限の地平線における政策最適化、$gamma$-discounted constrained Markov decision process (CMDP)について研究する。 我々の目標は、小さな制約違反で大きな期待された報酬を達成する政策を返却することである。 本稿では,任意のアルゴリズムに対して,報酬の準最適性と制約違反を拘束できる汎用的原始双対フレームワークを提案する。
  論文  参考訳（メタデータ） (2022-04-11T15:08:09Z)
• The Fundamental Price of Secure Aggregation in Differentially Private Federated Learning [34.630300910399036]
  我々は、$varepsilon$ Central DPの下で最高の精度を得るために必要な基本的な通信コストを特徴付ける。 我々の結果は、$tildeOleft( min(n2varepsilon2, d) right)$ bits per client が十分かつ必要であることを示している。 これにより、最先端のSecAgg分散DPスキームに対して大幅に改善される。
  論文  参考訳（メタデータ） (2022-03-07T22:56:09Z)
• Nearly Minimax Optimal Reward-free Reinforcement Learning [88.75843804630772]
  本稿では、特にバッチ強化学習に適した報酬不要強化学習フレームワークと、複数の報酬関数に対するポリシーを必要とするシナリオについて検討する。 textbfStaged textbfSampling + textbfTruncated textbfPlanning (algoname) という新しい効率的なアルゴリズムを提供しています。
  論文  参考訳（メタデータ） (2020-10-12T17:51:19Z)
• Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method [54.93433440034386]
  実現可能な$epsilon$-suboptimalソリューションは、$O(epsilon-1)$ POコールと最適な$O(epsilon-2)$ FOコールのみを使用します。 提案手法は,POおよびLMOコールのコストがかかる問題に対して,最先端技術に対する大幅な高速化を実現するものであることを確認した。
  論文  参考訳（メタデータ） (2020-10-05T08:16:56Z)
• Safe Learning under Uncertain Objectives and Constraints [66.05180398174286]
  我々は、テキスト不明で安全クリティカルな制約の下で、非テクスト無知かつ安全クリティカルな最適化問題を考察する。 このような問題は、ロボティクス、製造、医療などの様々な領域で自然に発生する。 我々の分析の重要な要素は、安全な最適化の文脈で収縮と呼ばれる手法を導入し、適用することである。
  論文  参考訳（メタデータ） (2020-06-23T20:51:00Z)
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
  制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。 本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-03-01T17:47:03Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。