論文の概要: Resource Allocation to Agents with Restrictions: Maximizing Likelihood
with Minimum Compromise
- arxiv url: http://arxiv.org/abs/2209.05170v1
- Date: Mon, 12 Sep 2022 11:58:19 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-13 13:08:41.549569
- Title: Resource Allocation to Agents with Restrictions: Maximizing Likelihood
with Minimum Compromise
- Title(参考訳): 制限のあるエージェントへのリソース割り当て: 最小妥協による可能性の最大化
- Authors: Yohai Trabelsi, Abhijin Adiga, Sarit Kraus, S.S. Ravi
- Abstract要約: 原理は、各エージェントが何らかの確率でリソースにマッチするように、ランダムに最大マッチングを選択することを示す。
エージェントは、制限を一定の範囲内で変更することで、マッチする可能性を改善したいと考えています。
本研究では,合成データセットと2つの新しい実世界のデータセットについて実験的に評価した。
- 参考スコア(独自算出の注目度): 28.2469613376685
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Many scenarios where agents with restrictions compete for resources can be
cast as maximum matching problems on bipartite graphs. Our focus is on resource
allocation problems where agents may have restrictions that make them
incompatible with some resources. We assume that a Principle chooses a maximum
matching randomly so that each agent is matched to a resource with some
probability. Agents would like to improve their chances of being matched by
modifying their restrictions within certain limits. The Principle's goal is to
advise an unsatisfied agent to relax its restrictions so that the total cost of
relaxation is within a budget (chosen by the agent) and the increase in the
probability of being assigned a resource is maximized. We establish hardness
results for some variants of this budget-constrained maximization problem and
present algorithmic results for other variants. We experimentally evaluate our
methods on synthetic datasets as well as on two novel real-world datasets: a
vacation activities dataset and a classrooms dataset.
- Abstract(参考訳): 制約のあるエージェントがリソースを競う多くのシナリオは、二部グラフの最大マッチング問題としてキャストできる。
我々の焦点はリソース割り当ての問題であり、エージェントはリソースとの互換性を損なうような制限を課す可能性がある。
各エージェントがリソースと何らかの確率でマッチするように、原則がランダムに最大マッチングを選択すると仮定する。
エージェントは、一定の範囲内で制限を変更することで、マッチする可能性を改善したい。
原則の目的は、不満足なエージェントに制限を緩和するよう助言し、緩和の総コストが予算の範囲内(エージェントによる調停)であり、リソースを割り当てる確率の増大が最大になるようにすることである。
我々は,この予算制約付き最大化問題のいくつかの変種に対してハードネス結果を確立し,他の変種に対してアルゴリズム的結果を与える。
提案手法は, 総合データセットと, 休暇活動データセットと教室データセットの2つの新しい実世界データセットについて実験的に評価した。
関連論文リスト
- Best Arm Identification with Resource Constraints [6.236743421605786]
資源制約付きベストアーム識別(BAIwRC)問題について検討する。
エージェントは、各アームプルにリソースが消費されるリソース制約の下で、最適なアームを特定することを目的としている。
資源集約アルゴリズム(SH-RR)を設計・解析する。
論文 参考訳(メタデータ) (2024-02-29T12:17:54Z) - DePAint: A Decentralized Safe Multi-Agent Reinforcement Learning
Algorithm considering Peak and Average Constraints [1.2617078020344619]
本稿では分散環境でのマルチエージェントポリシー最適化の問題に対処する。
モーメントに基づく分散型政策勾配法であるDePaintを提案し,その解法を提案する。
私たちの知る限りでは、これは、ピークと平均的な制約の両方を考慮に入れた、プライバシ保護で完全に分散化されたマルチエージェント強化学習アルゴリズムとしては初めてのものです。
論文 参考訳(メタデータ) (2023-10-22T16:36:03Z) - Cooperative Thresholded Lasso for Sparse Linear Bandit [6.52540785559241]
本稿では,マルチエージェント・スパース文脈線形帯域問題に対処する新しい手法を提案する。
疎線形帯域における行単位の分散データに対処する最初のアルゴリズムである。
後悔を最小限に抑えるために効率的な特徴抽出が重要となる高次元マルチエージェント問題に適用可能である。
論文 参考訳(メタデータ) (2023-05-30T16:05:44Z) - On the Complexity of Multi-Agent Decision Making: From Learning in Games
to Partial Monitoring [105.13668993076801]
マルチエージェント強化学習(MARL)理論における中心的な問題は、構造条件やアルゴリズムの原理がサンプル効率の学習保証につながるかを理解することである。
本稿では,複数のエージェントを用いた対話型意思決定のための一般的な枠組みとして,この問題について考察する。
マルチエージェント意思決定における統計的複雑性を特徴付けることは、単一エージェント決定の統計的複雑性を特徴付けることと等価であることを示す。
論文 参考訳(メタデータ) (2023-05-01T06:46:22Z) - Best Arm Identification for Stochastic Rising Bandits [93.12525232849706]
Rising Bandits (SRBs) は、選択肢の期待される報酬が選択されるたびに増加する、シーケンシャルな意思決定の問題をモデル化する。
本稿では,SRBの固定予算ベストアーム識別(BAI)問題に焦点をあてる。
提案手法は,UCBライクなアプローチを取り入れたR-UCBEと,連続的なリジェクション手順を用いたR-SRという2つのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-02-15T08:01:37Z) - Constrained Pure Exploration Multi-Armed Bandits with a Fixed Budget [4.226118870861363]
固定予算の下で、制約のある純粋な探索、多武装バンディットの定式化を検討する。
本稿では,Successive Rejects フレームワークに基づく textscConstrained-SR というアルゴリズムを提案する。
また, ある特別な場合において, 関連する崩壊速度は情報理論的下界に対してほぼ最適であることを示した。
論文 参考訳(メタデータ) (2022-11-27T08:58:16Z) - Quantization for decentralized learning under subspace constraints [61.59416703323886]
エージェントがサブスペース制約を最小化するために個々のコスト関数を持つ分散最適化問題を考察する。
本稿では,エージェントが確率化量子化器を用いて推定値を圧縮する適応分散型戦略を提案し,検討する。
この分析は、量子化ノイズのいくつかの一般的な条件下では、平均二乗誤差と平均ビットレートの両方で戦略が安定であることを示している。
論文 参考訳(メタデータ) (2022-09-16T09:38:38Z) - Distributed Adaptive Learning Under Communication Constraints [54.22472738551687]
本研究では,コミュニケーション制約下での運用を目的とした適応型分散学習戦略について検討する。
我々は,ストリーミングデータの連続的な観察から,オンライン最適化問題を解決しなければならないエージェントのネットワークを考える。
論文 参考訳(メタデータ) (2021-12-03T19:23:48Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳(メタデータ) (2021-06-05T09:16:28Z) - Coordinated Online Learning for Multi-Agent Systems with Coupled
Constraints and Perturbed Utility Observations [91.02019381927236]
本研究では, 資源制約を満たすため, エージェントを安定な集団状態へ誘導する新しい手法を提案する。
提案手法は,ゲームラグランジアンの拡張によるリソース負荷に基づく分散リソース価格設定手法である。
論文 参考訳(メタデータ) (2020-10-21T10:11:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。