論文の概要: Resource Sharing Through Multi-Round Matchings

• arxiv url: http://arxiv.org/abs/2211.17199v1
• Date: Wed, 30 Nov 2022 17:46:43 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-01 16:58:49.504348
• Title: Resource Sharing Through Multi-Round Matchings
• Title（参考訳）: 多元マッチングによる資源共有
• Authors: Yohai Trabelsi, Abhijin Adiga, Sarit Kraus, S.S. Ravi, Daniel J. Rosenkrantz
• Abstract要約: 1ラウンド当たりのマッチングの集合は、もし存在するなら、効率的に見つけることができることを示す。 提案アルゴリズムを合成ネットワーク上で実験的に評価し,2つの実環境 – 共有オフィススペースとマッチングコース – に適用した。
• 参考スコア（独自算出の注目度）: 27.98321373077565
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Applications such as employees sharing office spaces over a workweek can be modeled as problems where agents are matched to resources over multiple rounds. Agents' requirements limit the set of compatible resources and the rounds in which they want to be matched. Viewing such an application as a multi-round matching problem on a bipartite compatibility graph between agents and resources, we show that a solution (i.e., a set of matchings, with one matching per round) can be found efficiently if one exists. To cope with situations where a solution does not exist, we consider two extensions. In the first extension, a benefit function is defined for each agent and the objective is to find a multi-round matching to maximize the total benefit. For a general class of benefit functions satisfying certain properties (including diminishing returns), we show that this multi-round matching problem is efficiently solvable. This class includes utilitarian and Rawlsian welfare functions. For another benefit function, we show that the maximization problem is NP-hard. In the second extension, the objective is to generate advice to each agent (i.e., a subset of requirements to be relaxed) subject to a budget constraint so that the agent can be matched. We show that this budget-constrained advice generation problem is NP-hard. For this problem, we develop an integer linear programming formulation as well as a heuristic based on local search. We experimentally evaluate our algorithms on synthetic networks and apply them to two real-world situations: shared office spaces and matching courses to classrooms.
• Abstract（参考訳）: ワークウィークでオフィススペースを共有する従業員のようなアプリケーションは、エージェントが複数のラウンドでリソースにマッチする問題としてモデル化できる。 エージェントの要件は、互換性のあるリソースのセットと、それらがマッチしたいラウンドを制限する。 このようなアプリケーションをエージェントとリソースの2部間互換性グラフ上でマルチラウンドマッチング問題と見なすと、解(つまり、ラウンド毎に1つのマッチングを持つマッチングの集合)が存在すれば効率的に見つかることが分かる。 解が存在しない状況に対処するため、2つの拡張を考える。 最初の拡張では、各エージェントに対して利益関数を定義し、目的は全利益を最大化するマルチラウンドマッチングを見つけることである。 特定の性質を満たす一般の利得関数(リターンの減少を含む)に対して、このマルチラウンドマッチング問題は効率的に解けることを示す。 このクラスには功利主義とラウルシズムの福祉機能が含まれる。 別の利益関数に対して、最大化問題はNPハードであることを示す。 第2の拡張では、各エージェント(つまり、緩和すべき要件のサブセット)に対して、エージェントが一致できるように予算制約の対象となるアドバイスを生成することが目的である。 この予算制約付きアドバイス生成問題はnp困難であることを示す。 そこで本研究では,局所探索に基づくヒューリスティックだけでなく,整数線形プログラミングの定式化も行う。 合成ネットワーク上のアルゴリズムを実験的に評価し,共有オフィス空間とマッチングコースの2つの実環境に適用した。

関連論文リスト

• Efficient Planning in Combinatorial Action Spaces with Applications to Cooperative Multi-Agent Reinforcement Learning [16.844525262228103]
  協調型マルチエージェント強化学習では、多数のエージェントが共同でグローバル報酬関数を最適化し、エージェントの数によってアクション空間が爆発する。 最小限の要件として、モデルクラスの任意のQ-関数に対する欲求ポリシーを効率的に計算できるargmaxオラクルへのアクセスを仮定する。 そこで本研究では,全ての問題パラメータの計算と問合せを複雑化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-08T23:42:49Z)
• Multi-task Bias-Variance Trade-off Through Functional Constraints [102.64082402388192]
  マルチタスク学習は、多様なタスクによく機能する関数の集合を取得することを目的としている。 本稿では,2つの極端な学習シナリオ,すなわちすべてのタスクに対する単一関数と,他のタスクを無視するタスク固有関数から直感を抽出する。 本稿では,集中関数に対するドメイン固有解を強制する制約付き学習定式化を導入する。
  論文  参考訳（メタデータ） (2022-10-27T16:06:47Z)
• Multi-agent Deep Covering Skill Discovery [50.812414209206054]
  本稿では,複数エージェントの結合状態空間の予測被覆時間を最小化し,マルチエージェントオプションを構築するマルチエージェントDeep Covering Option Discoveryを提案する。 また、MARLプロセスにマルチエージェントオプションを採用するための新しいフレームワークを提案する。 提案アルゴリズムは,アテンション機構とエージェントの相互作用を効果的に把握し,マルチエージェントオプションの同定に成功した。
  論文  参考訳（メタデータ） (2022-10-07T00:40:59Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。 クエリを少なくすることで、問題の解決が容易になる。
  論文  参考訳（メタデータ） (2021-06-04T02:32:26Z)
• Multi-agent Policy Optimization with Approximatively Synchronous Advantage Estimation [55.96893934962757]
  マルチエージェントシステムでは、異なるエージェントの警察を共同で評価する必要がある。 現在の方法では、バリュー関数やアドバンテージ関数は非同期に評価される対実関節アクションを使用する。 本研究では,近似的に同期する利点推定を提案する。
  論文  参考訳（メタデータ） (2020-12-07T07:29:19Z)
• The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems [7.433931244705934]
  本稿では,意思決定者に対して未知の入力モデルを用いて,各要求に対する報酬とリソース消費を生成するデータ駆動型設定について考察する。 様々な入力モデルにおいて,どの入力に直面するかを知ることなく,優れた性能が得られるアルゴリズムの一般クラスを設計する。 我々のアルゴリズムはラグランジアン双対空間で動作し、オンラインミラー降下を用いて更新される各リソースに対して双対乗算器を保持する。
  論文  参考訳（メタデータ） (2020-11-18T18:39:17Z)
• Kernel Methods for Cooperative Multi-Agent Contextual Bandits [15.609414012418043]
  協調的マルチエージェント意思決定は、遅延のあるネットワーク上で通信しながら、学習問題を協調的に解決するエージェントのグループを含む。 エージェントが得られる報酬は、関連するカーネル再生ヒルベルト空間(RKHS)におけるコンテキストのイメージの任意の線形関数である。 我々は, 年齢ごとの後悔に対して, ほぼ最適境界を与えるアルゴリズムであるtextscCoop- KernelUCBを提案する。
  論文  参考訳（メタデータ） (2020-08-14T07:37:44Z)
• A Multi-Agent Primal-Dual Strategy for Composite Optimization over Distributed Features [52.856801164425086]
  目的関数を滑らかな局所関数と凸(おそらく非滑らか)結合関数の和とするマルチエージェント共有最適化問題について検討する。
  論文  参考訳（メタデータ） (2020-06-15T19:40:24Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。 都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
  論文  参考訳（メタデータ） (2020-05-27T01:10:41Z)
• Constrained Multiagent Rollout and Multidimensional Assignment with the Auction Algorithm [0.0]
  本稿では,制約付き決定論的動的プログラミングに適用可能なロールアウトアルゴリズムの拡張について考察する。 提案手法では,ベースが実現可能な解を生成する場合,ロールアウトアルゴリズムはコスト改善特性を有することを示す。 コスト改善特性は計算要求を大幅に削減した代替実装で維持されていることを示す。
  論文  参考訳（メタデータ） (2020-02-18T07:09:06Z)

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

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