論文の概要: Fair Division with Strictly Increasing Valuations: A Tight Threshold for Two-Agent EF1 and PO

• arxiv url: http://arxiv.org/abs/2607.23367v1
• Date: Sat, 25 Jul 2026 21:17:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-28 22:34:15.0843
• Title: Fair Division with Strictly Increasing Valuations: A Tight Threshold for Two-Agent EF1 and PO
• Title（参考訳）: 厳格な値の上昇を伴う公正部門:二元EF1とPOの厳格な閾値
• Abstract要約: 我々は、厳密な正の限界値が1つの利益までエンビーフリーネスの互換性を回復するかどうかを考察する。 我々は、正規化、整数値、厳格化、部分モジュラー評価を持つ8つの良いインスタンスを構築する。
• 参考スコア（独自算出の注目度）: 11.208733293527795
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study whether strictly positive marginal values restore the compatibility of envy-freeness up to one good (EF1) and Pareto optimality (PO) for indivisible goods. For two agents, we identify the exact threshold in the number of goods. Every instance with at most seven goods and strictly increasing valuations admits an allocation that is both EF1 and PO, without any submodularity assumption. In contrast, we construct an eight-good instance with normalized, integer-valued, strictly increasing, submodular valuations in which every EF1 allocation is strictly Pareto dominated. Thus, eight goods are necessary and sufficient for a two-agent counterexample. Finally, we strengthen the three-agent NP-hardness result of Chandramouleeswaran and Nimbhorkar (2026): deciding whether an EF1 and PO allocation exists remains NP-hard for normalized, integer-valued, monotone submodular valuations even when zero marginals are confined to eight fixed agent-good pairs, all involving a single agent.
• Abstract（参考訳）: 厳密な正の辺縁値が、一品(EF1)と分割可能な商品に対するパレート最適性(PO)の適合性を回復するかどうかを考察する。 2つのエージェントに対して、商品数の正確なしきい値を特定する。 最低でも7つの財と厳密なバリュエーションを持つ全てのインスタンスは、サブモジュラリティの仮定なしにEF1とPOの両方のアロケーションを許容する。 対照的に、正規化、整数値付き、厳密に増加し、全てのEF1割り当てが厳密にパレートされる部分モジュラーのバリュエーションを持つ8つの良いインスタンスを構築する。 したがって、8つの商品は2エージェントの反例に十分必要である。 最後に、Chandramouleeswaran と Nimbhorkar (2026): EF1 と PO の割り当てが存在するかどうかを判定し、ゼロ限界が8つの固定されたエージェント-グッドペアに制限された場合でも、正規化、整数値、単調なサブモジュラー評価に対して NP-hard を継続する。

関連論文リスト

• Aggregate in the Advantage, Not the Ratio: A Canonical-Form Analysis of Cooperative Multi-Agent Policy Optimization [5.703301837612397]
  隣人」とは、身体的近接だけでなく、互いに影響を及ぼす作用も指す。 決定は2つの次元(利点と比率)に沿って行う必要がある。 設計原理はあいまいである: 隣人を有利に集約し、結合近傍にサイズを拡大し、エージェント当たりの比率を維持する。
  論文  参考訳（メタデータ） (2026-07-20T13:20:29Z)
• AI-Assisted Discovery of Convex Relaxations via Dual Agents [56.60366723277675]
  すべての許容関数に対して下界が成り立ち、より強い境界を与える凸緩和から従うことを示す。 理論は各エージェントを検証し、反例を検索し、報告されたすべての境界はインターバルにおける明示的な二重実現可能な点によって認証される。
  論文  参考訳（メタデータ） (2026-06-30T06:10:25Z)
• Preserving Disagreement: Architectural Heterogeneity and Coherence Validation in Multi-Agent Policy Simulation [0.0]
  政策シミュレーションにおいて,大規模言語モデル(LLM)を用いたマルチエージェント検討システムの提案が進んでいる。 評価エージェントは、割り当てられた値の観点に関わらず、同じ選択肢に収束する。 我々は、三段階の審議フレームワークであるAI Councilを提示し、2つの介入をテストするための2つの政策シナリオにわたる120の審議を行う。
  論文  参考訳（メタデータ） (2026-04-29T11:47:28Z)
• Almost Asymptotically Optimal Active Clustering Through Pairwise Observations [59.20614082241528]
  そこで本研究では, ノイズと能動的に収集された応答を用いて, M$アイテムを未知数の$K$個別グループにクラスタリングするための新しい分析フレームワークを提案する。 クラスタリングの精度に対する望ましい信頼性を達成するのに必要なクエリ数の基本的下位境界を確立する。 我々は、一般化された同値比統計の計算可能な変種を開発し、その下限に対する性能ギャップを正確に推定できることを実証的に示す。
  論文  参考訳（メタデータ） (2026-02-05T14:16:47Z)
• Online Fair Division for Personalized $2$-Value Instances [51.278096593080456]
  オンラインフェアディビジョン(オンラインフェアディビジョン)では,商品が一度に1つずつ到着し,定額のエージェントが配置されている。 善が現れると、各エージェントの持つ値が明らかになり、エージェントの1つに即時かつ不可逆的に割り当てられなければならない。 我々は、よく知られた公平性の概念に関して、最悪の場合の保証を得る方法を示す。
  論文  参考訳（メタデータ） (2025-05-28T09:48:16Z)
• Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback [75.29048190099523]
  オンライン勾配降下(OGD)は、強い凸性や単調性仮定の下では二重最適であることが知られている。 本稿では,これらのパラメータの事前知識を必要としない完全適応型OGDアルゴリズム,textsfAdaOGDを設計する。
  論文  参考訳（メタデータ） (2023-10-21T18:38:13Z)
• Dividing Good and Better Items Among Agents with Bivalued Submodular Valuations [20.774185319381985]
  本稿では,2値のサブモジュラー評価を持つエージェント間で,分割不可能な商品の集合を適切に割り当てる問題について検討する。 我々は、レキシミンとMNWの割り当てが1つの利益まで自由になされることは保証されていないことを示す。
  論文  参考訳（メタデータ） (2023-02-06T19:41:28Z)
• Greedy based Value Representation for Optimal Coordination in Multi-agent Reinforcement Learning [64.05646120624287]
  LVDとMVDの結合Q値関数を導出する。 最適な整合性を確保するために、最適なノードは独自のSTNである必要がある。 本手法は,様々なベンチマーク実験において,最先端のベースラインよりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-11-22T08:14:50Z)
• (Almost) Envy-Free, Proportional and Efficient Allocations of an Indivisible Mixed Manna [10.933894827834825]
  エージェントの集合に分割不可能な項目の集合を公平かつ効率的に割り当てることの課題について検討する。 公平性の概念として、エンビーフリーネスと比例性の最も強い緩和性を考える。
  論文  参考訳（メタデータ） (2022-02-06T01:29:50Z)
• Monotonic Improvement Guarantees under Non-stationarity for Decentralized PPO [66.5384483339413]
  我々は,MARL(Multi-Agent Reinforcement Learning)における分散政策の最適化のための新しい単調改善保証を提案する。 本研究では,訓練中のエージェント数に基づいて,独立した比率を限定することにより,信頼領域の制約を原則的に効果的に実施可能であることを示す。
  論文  参考訳（メタデータ） (2022-01-31T20:39:48Z)
• Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness [16.187873844872637]
  付加価値関数を持つ戦略エージェントの集合に、分割不可能な商品の集合をかなり割り当てるという問題を考察する。 我々の主なゴールは、全てのインスタンスに純粋なナッシュ平衡を持つメカニズムが存在するかどうかを探ることである。 対応するアロケーションは EFX だけでなく、最大シェアフェアネスも満足していることを示します。
  論文  参考訳（メタデータ） (2021-09-17T16:57:20Z)
• Finding Fair and Efficient Allocations When Valuations Don't Add Up [25.962505544590947]
  エージェント評価がマトロイドのランク関数である場合、社会的に最適な(実用的社会福祉の最大化)手法は、1つの項目(EF1)までのうらやましい自由度が存在し、計算的に抽出可能であることを示す。 これは、ナッシュの福祉を最大化する割り当てがEF1であると確立された付加的評価によって仮定されない最初の評価関数クラスである。
  論文  参考訳（メタデータ） (2020-03-16T07:42:27Z)

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

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