Fugu-MT 論文翻訳(概要): Pushing the Frontier on Approximate EFX Allocations

論文の概要: Pushing the Frontier on Approximate EFX Allocations

arxiv url: http://arxiv.org/abs/2406.12413v1
Date: Tue, 18 Jun 2024 09:01:37 GMT
ステータス: 処理完了
システム内更新日: 2024-06-19 19:46:52.541232
Title: Pushing the Frontier on Approximate EFX Allocations
Title（参考訳）: 近似EFXアロケーションにおけるフロンティアの推進
Authors: Georgios Amanatidis, Aris Filos-Ratsikas, Alkmini Sgouritsa,
Abstract要約: 本研究では, 付加的評価関数を持つエージェント群に対して, 分割不可能な商品群を割り当てる問題について検討する。正確なEFXアロケーションが存在することが分かっている設定の厳密な一般化のために、我々は存在結果を得る。この結果から, 近似EFXアロケーションの存在と計算のフロンティアを推し進めることができた。
参考スコア（独自算出の注目度）: 14.101164748526159
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study the problem of allocating a set of indivisible goods to a set of agents with additive valuation functions, aiming to achieve approximate envy-freeness up to any good ($\alpha$-EFX). The state-of-the-art results on the problem include that (exact) EFX allocations exist when (a) there are at most three agents, or (b) the agents' valuation functions can take at most two values, or (c) the agents' valuation functions can be represented via a graph. For $\alpha$-EFX, it is known that a $0.618$-EFX allocation exists for any number of agents with additive valuation functions. In this paper, we show that $2/3$-EFX allocations exist when (a) there are at most \emph{seven agents}, (b) the agents' valuation functions can take at most \emph{three values}, or (c) the agents' valuation functions can be represented via a \emph{multigraph}. Our results can be interpreted in two ways. First, by relaxing the notion of EFX to $2/3$-EFX, we obtain existence results for strict generalizations of the settings for which exact EFX allocations are known to exist. Secondly, by imposing restrictions on the setting, we manage to beat the barrier of $0.618$ and achieve an approximation guarantee of $2/3$. Therefore, our results push the \emph{frontier} of existence and computation of approximate EFX allocations, and provide insights into the challenges of settling the existence of exact EFX allocations.
Abstract（参考訳）: 本研究では, 付加価値関数を持つエージェント群に対して, 分割不可能な商品群を割り当てることの問題点について検討する。この問題の最先端の成果には、(実際に)EFXアロケーションが存在することが含まれる。 (a)少なくとも3人の代理人がいる、または b) エージェントの価額関数は、最大2つの値を取ることができるか、 (c) エージェントの値関数をグラフで表すことができる。 $\alpha$-EFX の場合、0.618$-EFX は付加的な評価関数を持つ任意のエージェントに対して存在することが知られている。本稿では,2/3$-EFXのアロケーションが存在することを示す。 (a)少なくとも 'emph{seven agent} がある。 b) エージェントの付値関数は、ほとんどの \emph{ three value} で取ることができるか、または c) エージェントの値関数は \emph{multigraph} で表すことができる。私たちの結果は2つの方法で解釈できる。まず、EFXの概念を2/3$-EFXに緩和することにより、正確なEFX割り当てが存在することが分かっている設定の厳密な一般化のための存在結果を得る。第二に、設定に制限を課すことで、0.618ドルという障壁を乗り越え、近似保証が2/3ドルに達する。そこで本研究では, 近似EFXアロケーションの存在と計算のemph{frontier}を推し進め, 正確なEFXアロケーションの存在を確定する上での課題について考察する。

関連論文リスト

$\textit{X}^2$-DFD: A framework for e${X}$plainable and e${X}$tendable Deepfake Detection [52.14468236527728]
3つのコアモジュールからなる新しいフレームワークX2$-DFDを提案する。最初のモジュールであるモデル特徴評価(MFA)は、MLLMに固有の偽機能の検出能力を計測し、これらの機能の下位ランキングを提供する。第2のモジュールであるStrong Feature Strengthening (SFS)は、上位機能に基づいて構築されたデータセット上でMLLMを微調整することで、検出と説明機能を強化する。第3のモジュールであるWak Feature Supplementing (WFS)は、外部専用の機能を統合することで、低階機能における微調整MLLMの機能を改善する。
論文参考訳（メタデータ） (2024-10-08T15:28:33Z)
Refined Sample Complexity for Markov Games with Independent Linear Function Approximation [49.5660193419984]
マルコフゲーム(MG)はマルチエージェント強化学習(MARL)の重要なモデルである本稿では、WangらによるAVLPRフレームワークを改良し(2023年)、最適部分ギャップの悲観的推定を設計する。マルチエージェントの呪いに取り組み、最適な$O(T-1/2)収束率を達成し、同時に$textpoly(A_max)$依存性を避ける最初のアルゴリズムを与える。
論文参考訳（メタデータ） (2024-02-11T01:51:15Z)
EFX Allocations Exist for Binary Valuations [0.0]
公正な分割問題と公平な基準を満たす割り当ての存在について、あらゆる項目(EFX)まで検討する。全く異なる手法を用いることで、この存在を必ずしも部分モジュラーでない一般二項評価にまで拡張する。 EFXアロケーションを計算するための時間アルゴリズムを提案する。
論文参考訳（メタデータ） (2023-08-10T11:28:31Z)
Dividing Good and Better Items Among Agents with Bivalued Submodular Valuations [20.774185319381985]
本稿では,2値のサブモジュラー評価を持つエージェント間で,分割不可能な商品の集合を適切に割り当てる問題について検討する。我々は、レキシミンとMNWの割り当てが1つの利益まで自由になされることは保証されていないことを示す。
論文参考訳（メタデータ） (2023-02-06T19:41:28Z)
On the Identifiability and Estimation of Causal Location-Scale Noise Models [122.65417012597754]
位置スケール・異方性雑音モデル(LSNM)のクラスについて検討する。症例によっては, 因果方向が同定可能であることが示唆された。我々は,LSNMの2つの推定器を提案し,その1つは(非線形)特徴写像に基づく推定器と,1つはニューラルネットワークに基づく推定器を提案する。
論文参考訳（メタデータ） (2022-10-13T17:18:59Z)
(Almost) Envy-Free, Proportional and Efficient Allocations of an Indivisible Mixed Manna [10.933894827834825]
エージェントの集合に分割不可能な項目の集合を公平かつ効率的に割り当てることの課題について検討する。公平性の概念として、エンビーフリーネスと比例性の最も強い緩和性を考える。
論文参考訳（メタデータ） (2022-02-06T01:29:50Z)
Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness [16.187873844872637]
付加価値関数を持つ戦略エージェントの集合に、分割不可能な商品の集合をかなり割り当てるという問題を考察する。我々の主なゴールは、全てのインスタンスに純粋なナッシュ平衡を持つメカニズムが存在するかどうかを探ることである。対応するアロケーションは EFX だけでなく、最大シェアフェアネスも満足していることを示します。
論文参考訳（メタデータ） (2021-09-17T16:57:20Z)
Weighted QMIX: Expanding Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning [66.94149388181343]
本稿では,MARLのためのQ$-learningアルゴリズムの新バージョンを提案する。 Q*$をアクセスしても、最適なポリシーを回復できることを示します。また,プレデレータープリとマルチエージェントのStarCraftベンチマークタスクの性能向上を実証した。
論文参考訳（メタデータ） (2020-06-18T18:34:50Z)
VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback [104.06766271716774]
本研究では,エージェントが自己の価値を知らない場合に,マルチラウンドの福祉最大化機構設計問題について検討する。まず、福祉に対する後悔の3つの概念、各エージェントの個々のユーティリティ、メカニズムの3つの概念を定義します。当社のフレームワークは価格体系を柔軟に制御し、エージェントと販売者の後悔のトレードオフを可能にする。
論文参考訳（メタデータ） (2020-04-19T18:00:58Z)
Finding Fair and Efficient Allocations When Valuations Don't Add Up [25.962505544590947]
エージェント評価がマトロイドのランク関数である場合、社会的に最適な(実用的社会福祉の最大化)手法は、1つの項目(EF1)までのうらやましい自由度が存在し、計算的に抽出可能であることを示す。これは、ナッシュの福祉を最大化する割り当てがEF1であると確立された付加的評価によって仮定されない最初の評価関数クラスである。
論文参考訳（メタデータ） (2020-03-16T07:42:27Z)
Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
論文参考訳（メタデータ） (2020-03-01T17:47:03Z)

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

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