Fugu-MT 論文翻訳(概要): PROPm Allocations of Indivisible Goods to Multiple Agents

論文の概要: PROPm Allocations of Indivisible Goods to Multiple Agents

arxiv url: http://arxiv.org/abs/2105.11348v1
Date: Mon, 24 May 2021 15:34:33 GMT
ステータス: 処理完了
システム内更新日: 2021-05-25 15:03:20.740525
Title: PROPm Allocations of Indivisible Goods to Multiple Agents
Title（参考訳）: 複数のエージェントに対する識別不能商品のプロパム配分
Authors: Artem Baklanov, Pranav Garimidi, Vasilis Gkatzelis, Daniel Schoepflin
Abstract要約: 本稿では,エージェント群間の不特定商品の集合を適切に割り当てる古典的問題を考察し,PROPmとして知られる近似比例性の概念に着目した。 PROPm割り当ては、エージェントや商品の数によらず、すべてのインスタンスに対して存在することが保証されていることを示す。
参考スコア（独自算出の注目度）: 3.361550072563245
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study the classic problem of fairly allocating a set of indivisible goods among a group of agents, and focus on the notion of approximate proportionality known as PROPm. Prior work showed that there exists an allocation that satisfies this notion of fairness for instances involving up to five agents, but fell short of proving that this is true in general. We extend this result to show that a PROPm allocation is guaranteed to exist for all instances, independent of the number of agents or goods. Our proof is constructive, providing an algorithm that computes such an allocation and, unlike prior work, the running time of this algorithm is polynomial in both the number of agents and the number of goods.
Abstract（参考訳）: 本稿では,エージェント群間の不特定商品の集合を適切に割り当てる古典的問題を考察し,PROPmとして知られる近似比例性の概念に焦点をあてる。以前の研究は、最大5つのエージェントを含むインスタンスに対して、この公平性の概念を満たすアロケーションが存在することを示したが、これは一般に真実であることを示すには至らなかった。この結果を拡張して、エージェントや商品の数によらず、すべてのインスタンスに対して PROPm 割り当てが保証されていることを示す。我々の証明は構成的であり、そのような割り当てを計算するアルゴリズムを提供し、以前の仕事とは異なり、このアルゴリズムの実行時間はエージェント数と商品数の両方において多項式である。

関連論文リスト

Temporal Fair Division of Indivisible Items [61.235172150247614]
分割不可能なアイテムが順次到着し,即時かつ無効に割り当てられなければならない公平な分割モデルについて検討する。オンラインフェアディビジョンに関する以前の研究は、これらの制約の下で近似的なうらやみのない結果が得られないことを示してきた。各ラウンドにおける累積割り当てが1項目までの時間的エンビーフリーネス(TEF1)に近似することを確実にすることを目指している。
論文参考訳（メタデータ） (2024-10-18T16:43:36Z)
Online Fair Division with Contextual Bandits [41.57721032039409]
本稿では,学習者が不可分な項目を観察する複数のエージェントを含む,オンラインフェア分割問題について考察する。既存のアルゴリズムは、十分な数のコピーを持つ少数のアイテムを仮定し、全てのアイテムとエージェントのペアに対して優れたユーティリティー推定を可能にする。次に,オンラインフェアディビジョンのためのサブ線形後悔保証付きアルゴリズムを提案する。
論文参考訳（メタデータ） (2024-08-23T05:25:58Z)
Are Bounded Contracts Learnable and Approximately Optimal? [8.121834515103243]
本稿では,主エージェントが契約を用いてプロジェクトに取り組む動機付けを行う,主エージェント問題の隠れアクションモデルについて考察する。本研究では,有界決済契約が学習可能か,ほぼ最適かを検討する。
論文参考訳（メタデータ） (2024-02-22T12:19:19Z)
Approximate Linear Programming for Decentralized Policy Iteration in Cooperative Multi-agent Markov Decision Processes [5.842054972839244]
我々は,mエージェントを含む協調的マルチエージェントマルコフ決定過程について考察する。マルチエージェント設定のポリシーイテレーションプロセスでは、アクションの数はエージェントの数とともに指数関数的に増加する。本稿では,関数近似を用いた近似線形計画法を用いて,近似分散型ポリシー反復アルゴリズムを提案する。
論文参考訳（メタデータ） (2023-11-20T14:14:13Z)
Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
論文参考訳（メタデータ） (2023-04-01T15:50:18Z)
Robust Allocations with Diversity Constraints [65.3799850959513]
エージェント値の積を最大化するナッシュ福祉規則は,多様性の制約が導入されたとき,一意にロバストな位置にあることを示す。また, ナッシュ・ウェルズによる保証は, 広く研究されているアロケーション・ルールのクラスにおいて, ほぼ最適であることを示す。
論文参考訳（メタデータ） (2021-09-30T11:09:31Z)
Multi-agent Policy Optimization with Approximatively Synchronous Advantage Estimation [55.96893934962757]
マルチエージェントシステムでは、異なるエージェントの警察を共同で評価する必要がある。現在の方法では、バリュー関数やアドバンテージ関数は非同期に評価される対実関節アクションを使用する。本研究では,近似的に同期する利点推定を提案する。
論文参考訳（メタデータ） (2020-12-07T07:29:19Z)
Achieving Proportionality up to the Maximin Item with Indivisible Goods [14.002498730240902]
我々は、分割不可能な商品をかなり配置する問題を研究し、古典的公平性の概念である比例性に焦点をあてる。最近の研究で、比例性(PROPx)の近似バージョンでさえ、小さなインスタンスでも達成できないことが証明されている。最大5つのエージェントが付加価値を持つ場合において、この概念を満たすアロケーションにどのように到達するかを示す。
論文参考訳（メタデータ） (2020-09-20T19:21:19Z)
Randomized Entity-wise Factorization for Multi-Agent Reinforcement Learning [59.62721526353915]
実世界のマルチエージェント設定は、エージェントや非エージェントエンティティのタイプや量が異なるタスクを伴うことが多い。我々の方法は、これらの共通点を活用することを目的としており、「観察対象のランダムに選択されたサブグループのみを考えるとき、各エージェントが期待する効用は何か?」という問いを投げかける。
論文参考訳（メタデータ） (2020-06-07T18:28:41Z)
Scalable Multi-Agent Inverse Reinforcement Learning via Actor-Attention-Critic [54.2180984002807]
マルチエージェント逆逆強化学習 (MA-AIRL) は, 単エージェントAIRLをマルチエージェント問題に適用する最近の手法である。本稿では,従来の手法よりもサンプル効率が高く,スケーラブルなマルチエージェント逆RLアルゴリズムを提案する。
論文参考訳（メタデータ） (2020-02-24T20:30:45Z)

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