論文の概要: A survey on algorithms for Nash equilibria in finite normal-form games

• arxiv url: http://arxiv.org/abs/2312.11063v1
• Date: Mon, 18 Dec 2023 10:00:47 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-20 20:28:54.159785
• Title: A survey on algorithms for Nash equilibria in finite normal-form games
• Title（参考訳）: 有限正規形ゲームにおけるナッシュ平衡のアルゴリズムに関する調査
• Authors: Hanyu Li, Wenhan Huang, Zhijian Duan, David Henry Mguni, Kun Shao, Jun Wang, Xiaotie Deng
• Abstract要約: ナッシュ均衡はゲーム理論において最も影響力のある解の1つである。 コンピュータ科学と人工知能の発展に伴い、ナッシュ均衡計算への需要が高まっている。 本稿では, 有限正規形式ゲームにおけるナッシュ均衡とその近似解の計算アルゴリズムについて, 理論的, 経験的両面から検討する。
• 参考スコア（独自算出の注目度）: 15.76104985336285
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Nash equilibrium is one of the most influential solution concepts in game theory. With the development of computer science and artificial intelligence, there is an increasing demand on Nash equilibrium computation, especially for Internet economics and multi-agent learning. This paper reviews various algorithms computing the Nash equilibrium and its approximation solutions in finite normal-form games from both theoretical and empirical perspectives. For the theoretical part, we classify algorithms in the literature and present basic ideas on algorithm design and analysis. For the empirical part, we present a comprehensive comparison on the algorithms in the literature over different kinds of games. Based on these results, we provide practical suggestions on implementations and uses of these algorithms. Finally, we present a series of open problems from both theoretical and practical considerations.
• Abstract（参考訳）: ナッシュ均衡はゲーム理論における最も影響力のある解の1つである。 計算機科学と人工知能の発展に伴い、特にインターネット経済学やマルチエージェント学習において、nash平衡計算の需要が高まっている。 本稿では,有限正規形ゲームにおけるナッシュ均衡とその近似解を理論的および経験的観点から計算する様々なアルゴリズムについて検討する。 理論的には,文献中のアルゴリズムを分類し,アルゴリズム設計と解析に関する基本的な考え方を提案する。 そこで本研究では,様々なゲームに関する文献におけるアルゴリズムの包括的比較を行った。 これらの結果に基づき,これらのアルゴリズムの実装と利用について実践的な提案を行う。 最後に、理論的および実践的な考察から、一連のオープンな問題を提示する。

関連論文リスト

• Deep Equilibrium Algorithmic Reasoning [18.651333116786084]
  我々は異なる観点からニューラルネットワークの解法を研究する。 アルゴリズムの解はしばしば平衡であるため、平衡方程式を解くことによって直接解を見つけることができる。 我々のアプローチでは、列車とテスト時間の両方において、アルゴリズムの実際のステップ数に関する情報を必要としない。
  論文  参考訳（メタデータ） (2024-10-19T10:40:55Z)
• No-Regret Learning of Nash Equilibrium for Black-Box Games via Gaussian Processes [11.846329468283583]
  本稿では,ブラックボックスゲームにおける学習の課題について検討する。 我々はガウス過程を利用してそのようなゲームの平衡を同定する非回帰学習アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2024-05-14T04:58:23Z)
• A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [102.46640028830441]
  最適行列乗算重み更新(OMMWU)アルゴリズムを導入し,平均収束複雑性を$mathcalO(d/epsilon)$ to $epsilon$-Nash equilibriaとする。 この二次的なスピードアップは、量子ゼロサムゲームにおける$epsilon$-Nash平衡の計算のための新しいベンチマークを定めている。
  論文  参考訳（メタデータ） (2023-11-17T20:38:38Z)
• Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games [70.19141208203227]
  マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。 我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。 我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
  論文  参考訳（メタデータ） (2023-03-22T03:28:12Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。 また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
  論文  参考訳（メタデータ） (2023-01-19T11:36:50Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  我々は平均場相関と粗相関平衡の概念を発展させる。 ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
  論文  参考訳（メタデータ） (2022-08-22T08:31:46Z)
• Neural Combinatorial Optimization: a New Player in the Field [69.23334811890919]
  本稿では,ニューラルネットワークに基づくアルゴリズムの古典的最適化フレームワークへの導入に関する批判的分析を行う。 性能, 転送可能性, 計算コスト, 大規模インスタンスなど, これらのアルゴリズムの基本的側面を分析するために, 総合的研究を行った。
  論文  参考訳（メタデータ） (2022-05-03T07:54:56Z)
• Towards algorithm-free physical equilibrium model of computing [0.0]
  新しい計算モデルが提案され、アルゴリズムの逐次パラダイムを物理プロセスの固有の並列性に置き換える。 平衡状態が所望の解に対応する物理系を構築し、解を探すためにそれらを進化させる。 モデルの主な要件は特定され、潜在的な実装のために量子回路が提案される。
  論文  参考訳（メタデータ） (2021-11-30T09:48:39Z)
• 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)
• Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games [78.65798135008419]
  一般的なゲームでStackelberg平衡を効率的に学習する方法は、サンプルから非常にオープンなままです。 本稿では,2プレーヤターンベース汎用ゲームにおけるStackelberg平衡のサンプル効率学習に関する理論的研究を開始する。
  論文  参考訳（メタデータ） (2021-02-23T05:11:07Z)
• Quantum game theory and the complexity of approximating quantum Nash equilibria [0.6091702876917281]
  本稿では、量子ゲーム理論の一般的な定式化の複雑さ理論的側面について述べる。 特に、幅広い種類の量子ゲームにおける近似ナッシュ均衡を求める計算問題は、複雑性クラスPPADに含まれる(従って完備である)。
  論文  参考訳（メタデータ） (2021-01-31T18:42:59Z)

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

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