論文の概要: Who Plays First? Optimizing the Order of Play in Stackelberg Games with Many Robots
- arxiv url: http://arxiv.org/abs/2402.09246v2
- Date: Sun, 28 Apr 2024 23:35:05 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-30 23:35:54.707771
- Title: Who Plays First? Optimizing the Order of Play in Stackelberg Games with Many Robots
- Title(参考訳): 誰が最初にプレイするか? 多くのロボットによるStackelbergゲームにおけるプレイ順序の最適化
- Authors: Haimin Hu, Gabriele Dragotto, Zixu Zhang, Kaiqu Liang, Bartolomeo Stellato, Jaime F. Fisac,
- Abstract要約: Branch and Play (B&P) は、社会的に最適な遊びの順序とスタックルバーグ均衡に収束する効率的かつ正確なアルゴリズムである。
本稿では,B&Pによる航空交通管制,群れ形成,輸送車両の配車における実用性を実証する。
- 参考スコア(独自算出の注目度): 4.146913555716228
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the multi-agent spatial navigation problem of computing the socially optimal order of play, i.e., the sequence in which the agents commit to their decisions, and its associated equilibrium in an N-player Stackelberg trajectory game. We model this problem as a mixed-integer optimization problem over the space of all possible Stackelberg games associated with the order of play's permutations. To solve the problem, we introduce Branch and Play (B&P), an efficient and exact algorithm that provably converges to a socially optimal order of play and its Stackelberg equilibrium. As a subroutine for B&P, we employ and extend sequential trajectory planning, i.e., a popular multi-agent control approach, to scalably compute valid local Stackelberg equilibria for any given order of play. We demonstrate the practical utility of B&P to coordinate air traffic control, swarm formation, and delivery vehicle fleets. We find that B&P consistently outperforms various baselines, and computes the socially optimal equilibrium.
- Abstract(参考訳): 我々は, N-player Stackelberg 軌道ゲームにおいて, エージェントが決定にコミットする順序や, 関連する平衡といった, 社会的に最適なプレイ順序を演算する多エージェント空間ナビゲーション問題を考える。
我々は、この問題を、プレイの順列に付随する全ての可能なStackelbergゲーム空間上の混合整数最適化問題としてモデル化する。
この問題を解決するために、社会的に最適な遊び順序とスタックルバーグ均衡に確実に収束する効率的かつ正確なアルゴリズムであるブランチ・アンド・プレイ(B&P)を導入する。
B&Pのサブルーチンとして、我々はシーケンシャルな軌道計画、すなわち一般的なマルチエージェント制御アプローチを採用し、任意のプレイの順序に対して有効な局所スタックルバーグ平衡を計算する。
本稿では,B&Pによる航空交通管制,群れ形成,輸送車両の配車における実用性を実証する。
我々は、B&Pが様々なベースラインを一貫して上回り、社会的に最適な均衡を計算することを発見した。
関連論文リスト
- Neural Population Learning beyond Symmetric Zero-sum Games [52.20454809055356]
我々はNuPL-JPSROという,スキルの伝達学習の恩恵を受けるニューラル集団学習アルゴリズムを導入し,ゲームの粗相関(CCE)に収束する。
本研究は, 均衡収束型集団学習を大規模かつ汎用的に実施可能であることを示す。
論文 参考訳(メタデータ) (2024-01-10T12:56:24Z) - How Bad is Selfish Driving? Bounding the Inefficiency of Equilibria in
Urban Driving Games [64.71476526716668]
我々は,任意の平衡選手がプレーに同意するであろう効率について検討する。
我々は、アナーキーの価格に関する既存の境界を洗練させる保証を得る。
提案手法はオープンループ軌道に対する懸念を保証しているが,エージェントがクローズドループポリシーを採用する場合においても,効率的な平衡を観測する。
論文 参考訳(メタデータ) (2022-10-24T09:32:40Z) - Learning Correlated Stackelberg Equilibrium in General-Sum
Multi-Leader-Single-Follower Games [16.810700878778007]
本研究では、非対称な役割を持つプレイヤーをリーダーとフォロワーに分けることができる階層型マルチプレイヤーゲーム構造について検討する。
特に、複数のリーダーと1人のフォロワーがいるStackelbergのゲームシナリオに焦点を当てています。
我々は、CSE(Correlated Stackelberg Equilibrium)と呼ばれるMLSFゲームのための新しい非対称平衡概念を提案する。
論文 参考訳(メタデータ) (2022-10-22T15:05:44Z) - Pareto Actor-Critic for Equilibrium Selection in Multi-Agent
Reinforcement Learning [18.20664209675016]
この研究は、競合しないマルチエージェントゲームにおける平衡選択に焦点を当てている。
Pareto Actor-Critic (Pareto-AC)は、すべてのエージェントのリターンを最大化するアクター批判アルゴリズムである。
論文 参考訳(メタデータ) (2022-09-28T18:14:34Z) - Optimal Correlated Equilibria in General-Sum Extensive-Form Games:
Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation [99.00383370823839]
様々な種類の最適相関平衡を求める問題について検討する。
本稿では,特定の解の概念に依存する相関戦略の空間の表現である相関DAGを紹介する。
また、カードゲームブリッジのエンドゲームフェーズをエミュレートするトリックテイクゲームと、ライドシェアリングゲームという2つの新しいベンチマークゲームも導入した。
論文 参考訳(メタデータ) (2022-03-14T15:21:18Z) - Can Reinforcement Learning Find Stackelberg-Nash Equilibria in
General-Sum Markov Games with Myopic Followers? [156.5760265539888]
我々は,マルチプレイヤーのジェネラルサムマルコフゲームについて,リーダーに指名されたプレイヤーとフォロワーに指名されたプレイヤーの1人を用いて研究した。
そのようなゲームに対して、我々のゴールは、政策対 $(pi*, nu*)$ であるスタックルバーグ・ナッシュ均衡 (SNE) を見つけることである。
オンラインとオフラインの両方でSNEを解くために,サンプル効率強化学習(RL)アルゴリズムを開発した。
論文 参考訳(メタデータ) (2021-12-27T05:41:14Z) - Towards convergence to Nash equilibria in two-team zero-sum games [17.4461045395989]
2チームゼロサムゲームは、プレイヤーが2つの競合するエージェントに分割されるマルチプレイヤーゲームとして定義される。
我々はNash equilibria(NE)の解の概念に焦点をあてる。
このクラスのゲームに対する計算 NE は、複雑性クラス $mathrm$ に対して $textithard$ であることを示す。
論文 参考訳(メタデータ) (2021-11-07T21:15:35Z) - Multi-Agent Training beyond Zero-Sum with Correlated Equilibrium Meta-Solvers [21.462231105582347]
本稿では,n-player, general-sum extensive form game におけるエージェントのトレーニングアルゴリズムを提案する。
また,メタソリューションとして相関平衡(CE)を提案するとともに,新しい解法概念であるGini Correlated Equilibrium(MGCE)を提案する。
JPSROのためのCEメタソルバを用いていくつかの実験を行い、n-player, general-sumゲーム上で収束を示す。
論文 参考訳(メタデータ) (2021-06-17T12:34:18Z) - Better Regularization for Sequential Decision Spaces: Fast Convergence
Rates for Nash, Correlated, and Team Equilibria [121.36609493711292]
大規模2プレーヤワイドフォームゲームの計算平衡問題に対する反復的な一階法の適用について検討する。
正則化器を用いて一階法をインスタンス化することにより、相関平衡と元アンティー座標のチーム平衡を計算するための最初の加速一階法を開発する。
論文 参考訳(メタデータ) (2021-05-27T06:10:24Z) - Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games [78.65798135008419]
一般的なゲームでStackelberg平衡を効率的に学習する方法は、サンプルから非常にオープンなままです。
本稿では,2プレーヤターンベース汎用ゲームにおけるStackelberg平衡のサンプル効率学習に関する理論的研究を開始する。
論文 参考訳(メタデータ) (2021-02-23T05:11:07Z) - Safe Search for Stackelberg Equilibria in Extensive-Form Games [24.557177222572786]
スタックルバーグ均衡(Stackelberg equilibrium)は、2人プレイヤゲームにおいて、リーダーが従者に対するコミットメント権を持つ解概念である。
一般ゲームにおけるスタックルバーグ平衡の計算に探索を適用するための理論的に健全で実験的に有効な方法を提案する。
論文 参考訳(メタデータ) (2021-02-02T22:01:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。