論文の概要: Multiplayer Performative Prediction: Learning in Decision-Dependent
Games
- arxiv url: http://arxiv.org/abs/2201.03398v1
- Date: Mon, 10 Jan 2022 15:31:10 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-11 17:27:24.149509
- Title: Multiplayer Performative Prediction: Learning in Decision-Dependent
Games
- Title(参考訳): マルチプレイヤーパフォーマンス予測:決定依存ゲームにおける学習
- Authors: Adhyyan Narang and Evan Faulkner and Dmitriy Drusvyatskiy and Maryam
Fazel and Lillian J. Ratliff
- Abstract要約: 本稿では,マルチプレイヤー演奏予測のための新たなゲーム理論の枠組みを定式化する。
我々は、(i)パフォーマンス的に安定な平衡と(ii)ゲームのナッシュ平衡という、2つの異なる解の概念に焦点を当てる。
軽微な仮定の下では、様々なアルゴリズムにより、性能的に安定な平衡を効率的に見つけることができることを示す。
- 参考スコア(独自算出の注目度): 18.386569111954213
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Learning problems commonly exhibit an interesting feedback mechanism wherein
the population data reacts to competing decision makers' actions. This paper
formulates a new game theoretic framework for this phenomenon, called
multi-player performative prediction. We focus on two distinct solution
concepts, namely (i) performatively stable equilibria and (ii) Nash equilibria
of the game. The latter equilibria are arguably more informative, but can be
found efficiently only when the game is monotone. We show that under mild
assumptions, the performatively stable equilibria can be found efficiently by a
variety of algorithms, including repeated retraining and repeated (stochastic)
gradient play. We then establish transparent sufficient conditions for strong
monotonicity of the game and use them to develop algorithms for finding Nash
equilibria. We investigate derivative free methods and adaptive gradient
algorithms wherein each player alternates between learning a parametric
description of their distribution and gradient steps on the empirical risk.
Synthetic and semi-synthetic numerical experiments illustrate the results.
- Abstract(参考訳): 学習問題は通常、人口データが競合する意思決定者の行動に反応する興味深いフィードバックメカニズムを示す。
本稿では,この現象に対する新たなゲーム理論の枠組みを定式化した。
我々は2つの異なる解の概念、すなわち
一 能動安定均衡及び
(ii)ゲームのナッシュ平衡。
後者の平衡はおそらくより有益であるが、ゲームが単調である場合にのみ効率的に発見できる。
軽微な仮定では、繰り返し再学習や繰り返し(確率的)勾配プレイを含む様々なアルゴリズムにより、性能的に安定な平衡を効率的に見つけることができる。
次に,ゲームの強い単調性に対する透明な十分条件を確立し,ナッシュ平衡を求めるアルゴリズムの開発に使用する。
本研究では,各プレイヤーがパラメトリックな分布記述の学習と,経験的リスクに対する勾配ステップを交互に行う,微分自由法と適応勾配アルゴリズムについて検討する。
合成および半合成の数値実験は結果を示す。
関連論文リスト
- No-Regret Learning of Nash Equilibrium for Black-Box Games via Gaussian Processes [11.846329468283583]
本稿では,ブラックボックスゲームにおける学習の課題について検討する。
我々はガウス過程を利用してそのようなゲームの平衡を同定する非回帰学習アルゴリズムを提供する。
論文 参考訳(メタデータ) (2024-05-14T04:58:23Z) - A Black-box Approach for Non-stationary Multi-agent Reinforcement Learning [53.83345471268163]
非定常マルチエージェントシステムにおける平衡の学習について検討する。
単エージェント学習へのブラックボックス還元による様々な平衡の検証方法を示す。
論文 参考訳(メタデータ) (2023-06-12T23:48:24Z) - On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
時間変化ゲームにおける楽観的勾配降下(OGD)の収束を特徴付ける。
我々のフレームワークは、ゼロサムゲームにおけるOGDの平衡ギャップに対して鋭い収束境界をもたらす。
また,静的ゲームにおける動的後悔の保証に関する新たな洞察も提供する。
論文 参考訳(メタデータ) (2023-01-26T17:25:45Z) - Global Nash Equilibrium in Non-convex Multi-player Game: Theory and
Algorithms [66.8634598612777]
ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。
また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
論文 参考訳(メタデータ) (2023-01-19T11:36:50Z) - Finding mixed-strategy equilibria of continuous-action games without
gradients using randomized policy networks [83.28949556413717]
グラデーションへのアクセスを伴わない連続アクションゲームのナッシュ平衡を近似的に計算する問題について検討する。
ニューラルネットワークを用いてプレイヤーの戦略をモデル化する。
本論文は、制約のない混合戦略と勾配情報のない一般的な連続アクションゲームを解決する最初の方法である。
論文 参考訳(メタデータ) (2022-11-29T05:16:41Z) - 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) - Learning to Compute Approximate Nash Equilibrium for Normal-form Games [15.321036952379488]
有限$n$-playerの正規形式ゲームに対して,Nash平衡を近似的に計算するための一般的なメタ学習手法を提案する。
ゲーム毎のナッシュ均衡をスクラッチから近似あるいは学習する既存の解とは異なり、メタソルバはゲームユーティリティ行列からジョイント戦略プロファイルへの写像を直接構築する。
論文 参考訳(メタデータ) (2021-08-17T07:06:46Z) - Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games [78.65798135008419]
一般的なゲームでStackelberg平衡を効率的に学習する方法は、サンプルから非常にオープンなままです。
本稿では,2プレーヤターンベース汎用ゲームにおけるStackelberg平衡のサンプル効率学習に関する理論的研究を開始する。
論文 参考訳(メタデータ) (2021-02-23T05:11:07Z) - Hindsight and Sequential Rationality of Correlated Play [18.176128899338433]
私たちは、修正された振る舞いで達成できたことに対して、強いパフォーマンスを後見で保証するアルゴリズムを検討します。
我々は,学習の隠れた枠組みを,逐次的な意思決定の場で開発し,提唱する。
本稿では,それぞれの平衡の強さと弱さを文献に示す例を示す。
論文 参考訳(メタデータ) (2020-12-10T18:30:21Z) - No-regret learning and mixed Nash equilibria: They do not mix [64.37511607254115]
我々はFTRL(Follow-the-regularized-leader)のダイナミクスについて検討する。
厳密でないナッシュ均衡は、FTRLの下で安定して引き寄せることは不可能である。
この結果は,学習過程の結果を予測する上で重要な意味を持つ。
論文 参考訳(メタデータ) (2020-10-19T13:49:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。