論文の概要: The Cost of EFX: Generalized-Mean Welfare and Complexity Dichotomies with Few Surplus Items

• arxiv url: http://arxiv.org/abs/2601.12849v1
• Date: Mon, 19 Jan 2026 09:02:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-21 22:47:22.82328
• Title: The Cost of EFX: Generalized-Mean Welfare and Complexity Dichotomies with Few Surplus Items
• Title（参考訳）: EFXのコスト: 一般平均福祉と余剰品数が少ない複雑さの二分の一
• Authors: Eugene Lim, Tzeh Yuan Neoh, Nicholas Teh,
• Abstract要約: EFX(envy-freeness up any good)は、分類不可能な商品を割り当てる中心的公正の概念であるが、その存在は一般には未解決である。 本研究では,一般的に研究されている実用主義(p=1),ナッシュ(p-mean)の福祉,平等主義(p rightarrow -infty$)の目標を仮定する一般二コトミ・平均的福祉とEFXの相互作用について検討する。
• 参考スコア（独自算出の注目度）: 13.603504120117016
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Envy-freeness up to any good (EFX) is a central fairness notion for allocating indivisible goods, yet its existence is unresolved in general. In the setting with few surplus items, where the number of goods exceeds the number of agents by a small constant (at most three), EFX allocations are guaranteed to exist, shifting the focus from existence to efficiency and computation. We study how EFX interacts with generalized-mean ($p$-mean) welfare, which subsumes commonly-studied utilitarian ($p=1$), Nash ($p=0$), and egalitarian ($p \rightarrow -\infty$) objectives. We establish sharp complexity dichotomies at $p=0$: for any fixed $p \in (0,1]$, both deciding whether EFX can attain the global $p$-mean optimum and computing an EFX allocation maximizing $p$-mean welfare are NP-hard, even with at most three surplus goods; in contrast, for any fixed $p \leq 0$, we give polynomial-time algorithms that optimize $p$-mean welfare within the space of EFX allocations and efficiently certify when EFX attains the global optimum. We further quantify the welfare loss of enforcing EFX via the price of fairness framework, showing that for $p > 0$, the loss can grow linearly with the number of agents, whereas for $p \leq 0$, it is bounded by a constant depending on the surplus (and for Nash welfare it vanishes asymptotically). Finally we show that requiring Pareto-optimality alongside EFX is NP-hard (and becomes $Σ_2^P$-complete for a stronger variant of EFX). Overall, our results delineate when EFX is computationally costly versus structurally aligned with welfare maximization in the setting with few surplus items.
• Abstract（参考訳）: あらゆる善 (EFX) へのエンビーフリーネスは、不可分な商品を割り当てる中心的公正性の概念であるが、その存在は一般には未解決である。 商品の数がエージェント数を超える余剰品が少ない場合(ほとんどの場合3つ)、EFXの割り当ては存在を保証し、焦点を存在から効率と計算に移す。 EFXは一般的に研究される実用主義的(p=1$)、ナッシュ(p=0$)、平等主義(p \rightarrow -\infty$)の目的を仮定する一般平均的(p=1$)福祉とどのように相互作用するかを研究する。 固定された$p \in (0,1]$に対して、EFXがグローバルな$p$-meanの最適化を達成できるかどうかを判断し、EFXの割り当てを最大化する$p$-meanの福祉を最大化する$p$-meanの福祉はNPハードである。 フェアネスフレームワークの価格でEFXを強制する際の福祉損失を定量化し、$p > 0$ではエージェント数とともに直線的に減少し、$p \leq 0$では余剰量に応じて一定に制限される(ナッシュの福祉については漸近的に消滅する)ことを示す。 最後に、EFXと共にパレート最適性を要求することはNPハードであること(EFXのより強い変種に対して$Σ_2^P$-completeとなる)を示す。 総じて,EFXは計算コストがかかる場合と,余剰項目が少ない場合の福祉の最大化と構造的に整合している場合とを関連づけた。

関連論文リスト

• Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
  我々は、すべての労働者が同一の分布にアクセスする均質な(すなわちd.d.)場合であっても、すべての労働者が非バイアス付き境界 LDeltaepsilon2,$$$$$ のポリ対数的により良いポリ対数を求める集中型分散学習環境を考える。
  論文  参考訳（メタデータ） (2025-06-30T13:27:39Z)
• Resource Allocation under the Latin Square Constraint [3.8028747063484585]
  我々は、$n$のラウンドで$n$のエージェント間で$n$の分割不可能なアイテムを割り当てる問題を提起する。 この制約は、各エージェントがラウンド毎に1つ以上のアイテムを受信し、各アイテムを最大1回受信することを保証します。 スケジューリング、リソース管理、実験的設計のような現実世界のアプリケーションは、アロケーションにおける公平性やバランス性を満たすためにラテン四角い制約を必要とする。
  論文  参考訳（メタデータ） (2025-01-11T10:53:48Z)
• Pushing the Frontier on Approximate EFX Allocations [14.101164748526159]
  本研究では, 付加的評価関数を持つエージェント群に対して, 分割不可能な商品群を割り当てる問題について検討する。 正確なEFXアロケーションが存在することが分かっている設定の厳密な一般化のために、我々は存在結果を得る。 この結果から, 近似EFXアロケーションの存在と計算のフロンティアを推し進めることができた。
  論文  参考訳（メタデータ） (2024-06-18T09:01:37Z)
• Dividing Good and Better Items Among Agents with Bivalued Submodular Valuations [20.774185319381985]
  本稿では,2値のサブモジュラー評価を持つエージェント間で,分割不可能な商品の集合を適切に割り当てる問題について検討する。 我々は、レキシミンとMNWの割り当てが1つの利益まで自由になされることは保証されていないことを示す。
  論文  参考訳（メタデータ） (2023-02-06T19:41:28Z)
• Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Reward [66.81579829897392]
  我々はPessimistic vAlue iteRaTionとrEward Decomposition (PARTED)という新しいオフライン強化学習アルゴリズムを提案する。 PartEDは、最小2乗ベースの報酬再分配を通じて、ステップごとのプロキシ報酬に軌道を分解し、学習したプロキシ報酬に基づいて悲観的な値を実行する。 私たちの知る限りでは、PartEDは、トラジェクティブな報酬を持つ一般のMDPにおいて、証明可能な効率のよい最初のオフラインRLアルゴリズムである。
  論文  参考訳（メタデータ） (2022-06-13T19:11:22Z)
• (Almost) Envy-Free, Proportional and Efficient Allocations of an Indivisible Mixed Manna [10.933894827834825]
  エージェントの集合に分割不可能な項目の集合を公平かつ効率的に割り当てることの課題について検討する。 公平性の概念として、エンビーフリーネスと比例性の最も強い緩和性を考える。
  論文  参考訳（メタデータ） (2022-02-06T01:29:50Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimally [58.463668865380946]
  状態空間 $mathcalS$ を用いたエピソードマルコフ決定過程 (MDPs) における模擬学習の統計的限界について検討する。 rajaraman et al (2020) におけるmdアルゴリズムを用いた準最適性に対する上限 $o(|mathcals|h3/2/n)$ を定式化する。 Omega(H3/2/N)$ $mathcalS|geq 3$ であるのに対して、未知の遷移条件はよりシャープレートに悩まされる。
  論文  参考訳（メタデータ） (2021-02-25T15:50:19Z)
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
  制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。 本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-03-01T17:47:03Z)

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

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