論文の概要: Guaranteeing Maximin Shares: Some Agents Left Behind

• arxiv url: http://arxiv.org/abs/2105.09383v1
• Date: Wed, 19 May 2021 20:17:42 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-22 01:03:24.313686
• Title: Guaranteeing Maximin Shares: Some Agents Left Behind
• Title（参考訳）: マキシミン株の保証:一部のエージェントが残した
• Authors: Hadi Hosseini and Andrew Searns
• Abstract要約: 最適な近似アルゴリズムが一定数以上のエージェントを満足できないことを示し、MMSの存在と計算を1つのエージェントを除いて議論する。 私たちの結果の重要な意味は、$textMMSlceil3n/2rceil$、すなわち、エージェントが商品を$lceilfrac32nrceil$バンドルに分割することで受け取る値を保証するアロケーションの存在である。
• 参考スコア（独自算出の注目度）: 18.960425204405038
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The maximin share (MMS) guarantee is a desirable fairness notion for allocating indivisible goods. While MMS allocations do not always exist, several approximation techniques have been developed to ensure that all agents receive a fraction of their maximin share. We focus on an alternative approximation notion, based on the population of agents, that seeks to guarantee MMS for a fraction of agents. We show that no optimal approximation algorithm can satisfy more than a constant number of agents, and discuss the existence and computation of MMS for all but one agent and its relation to approximate MMS guarantees. We then prove the existence of allocations that guarantee MMS for $\frac{2}{3}$ of agents, and devise a polynomial time algorithm that achieves this bound for up to nine agents. A key implication of our result is the existence of allocations that guarantee $\text{MMS}^{\lceil{3n/2}\rceil}$, i.e., the value that agents receive by partitioning the goods into $\lceil{\frac{3}{2}n}\rceil$ bundles, improving the best known guarantee of $\text{MMS}^{2n-2}$. Finally, we provide empirical experiments using synthetic data.
• Abstract（参考訳）: マクシミンシェア(mms)保証は、不可分な商品を割り当てるための望ましい公正概念である。 MMSアロケーションは常に存在するわけではないが、全てのエージェントがその最大シェアのごく一部を受け取ることを保証するためにいくつかの近似技術が開発されている。 我々は,少数のエージェントに対してMSを保証しようとするエージェントの集団に基づく,別の近似概念に焦点をあてる。 最適近似アルゴリズムは定数以上のエージェントを満足できないことを示し, 1つのエージェントを除くすべてのエージェントに対するmmsの存在と計算と近似mms保証との関係について論じる。 次に、$\frac{2}{3}$のエージェントに対するMMSを保証するアロケーションの存在を証明し、最大9個のエージェントに対してこの境界を達成する多項式時間アルゴリズムを考案する。 この結果の鍵となる意味は、$\text{mms}^{\lceil{3n/2}\rceil}$、すなわち、商品を$\lceil{\frac{3}{2}n}\rceil$バンドルに分割することによってエージェントが受け取る値、$\text{mms}^{2n-2}$の最もよく知られた保証を改善する割り当ての存在である。 最後に,合成データを用いた実験を行う。

関連論文リスト

• Agent-Temporal Credit Assignment for Optimal Policy Preservation in Sparse Multi-Agent Reinforcement Learning [14.003793644193605]
  マルチエージェント環境では、エージェントはスパースや遅れたグローバル報酬のために最適なポリシーを学ぶのに苦労することが多い。 本稿では,エージェント・テンポラル・アジェント・リワード再分配(TAR$2$)を導入し,エージェント・テンポラル・クレジット割り当て問題に対処する新しいアプローチを提案する。 TAR$2$は、粗末なグローバル報酬をタイムステップ固有の報酬に分解し、エージェント固有の報酬を計算します。
  論文  参考訳（メタデータ） (2024-12-19T12:05:13Z)
• Cooperative Multi-Agent Constrained Stochastic Linear Bandits [2.099922236065961]
  N$エージェントのネットワークがローカルに通信し、期待されるコストを所定の閾値$tau$で保持しながら、全体的な後悔を最小限に抑える。 我々は、textitMA-OPLBと呼ばれる安全な分散上信頼度有界アルゴリズムを提案し、そのT$ラウンドの後悔に基づく高い確率を確立する。 我々の後悔の限界は次数$ MathcalOleft(fracdtau-c_0fraclog(NT)2sqrtNsqrtTlog (1/|lambda|)であることを示す。
  論文  参考訳（メタデータ） (2024-10-22T19:34:53Z)
• 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)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Byzantine-Resilient Decentralized Multi-Armed Bandits [25.499420566469098]
  エージェント間の情報混合ステップを不整合および極端な値の切り離しで融合するアルゴリズムを開発する。 このフレームワークは、コンピュータネットワークの攻撃者をモデル化したり、攻撃的なコンテンツをレコメンデーターシステムに攻撃したり、金融市場のマニピュレータとして利用することができる。
  論文  参考訳（メタデータ） (2023-10-11T09:09:50Z)
• Multi-agent Deep Covering Skill Discovery [50.812414209206054]
  本稿では,複数エージェントの結合状態空間の予測被覆時間を最小化し,マルチエージェントオプションを構築するマルチエージェントDeep Covering Option Discoveryを提案する。 また、MARLプロセスにマルチエージェントオプションを採用するための新しいフレームワークを提案する。 提案アルゴリズムは,アテンション機構とエージェントの相互作用を効果的に把握し,マルチエージェントオプションの同定に成功した。
  論文  参考訳（メタデータ） (2022-10-07T00:40:59Z)
• Robust Learning of Optimal Auctions [84.13356290199603]
  本研究では、入札者の評価値のサンプルを逆向きに破損させたり、逆向きに歪んだ分布から引き出すことができる場合に、サンプルから収益-最適マルチバイダオークションを学習する問題について検討する。 我々は,コルモゴロフ-スミルノフ距離における元の分布に対して$alpha$-closeの「全ての真の分布」に対して,収入がほぼ同時に最適であるメカニズムを学習できる新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-07-13T17:37:21Z)
• Multi-agent Policy Optimization with Approximatively Synchronous Advantage Estimation [55.96893934962757]
  マルチエージェントシステムでは、異なるエージェントの警察を共同で評価する必要がある。 現在の方法では、バリュー関数やアドバンテージ関数は非同期に評価される対実関節アクションを使用する。 本研究では,近似的に同期する利点推定を提案する。
  論文  参考訳（メタデータ） (2020-12-07T07:29:19Z)
• Distributed Bandits: Probabilistic Communication on $d$-regular Graphs [5.33024001730262]
  我々は、$d$-regular graphで定義されたネットワーク上の確率と通信するエージェントに対して、分散マルチエージェントのマルチアームバンディット問題について検討する。 エージェントベースの手法がグループ後悔の最小化にどのように貢献するかを解析し、新しいアッパー信頼境界(UCB)に基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-11-16T04:53:54Z)
• Robust Multi-Agent Multi-Armed Bandits [26.26185074977412]
  最近の研究によると、$Kの武器を持った盗賊の独立した事例に直面しているエージェントが、後悔を減らすために協力できることが示されている。 我々は、悪質なエージェントの振る舞いを仮定することなく、$m$が$K$よりも小さいと仮定すると、このアルゴリズムに対するコラボレーションは本当に後悔を減らせることを示した。
  論文  参考訳（メタデータ） (2020-07-07T22:27:30Z)
• VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback [104.06766271716774]
  本研究では,エージェントが自己の価値を知らない場合に,マルチラウンドの福祉最大化機構設計問題について検討する。 まず、福祉に対する後悔の3つの概念、各エージェントの個々のユーティリティ、メカニズムの3つの概念を定義します。 当社のフレームワークは価格体系を柔軟に制御し、エージェントと販売者の後悔のトレードオフを可能にする。
  論文  参考訳（メタデータ） (2020-04-19T18:00:58Z)

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

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