論文の概要: Multiplicative weights, equalizers, and P=PPAD

• arxiv url: http://arxiv.org/abs/1609.08934v2
• Date: Tue, 22 Apr 2025 20:12:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-02 19:15:51.366103
• Title: Multiplicative weights, equalizers, and P=PPAD
• Title（参考訳）: 乗法重、等化剤、P=PPAD
• Authors: Ioannis Avramopoulos,
• Abstract要約: 対称ビマトリクスゲーム(つまり、各プレイヤーの行列が他方の行列の転置となるビマトリクス行列)を示す。 貧弱に支配される純粋な戦略は、線形プログラムを解くことで、時間内に検出および排除することができる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We show that, by using multiplicative weights in a game-theoretic thought experiment (and an important convexity result on the composition of multiplicative weights with the relative entropy function), a symmetric bimatrix game (that is, a bimatrix matrix wherein the payoff matrix of each player is the transpose of the payoff matrix of the other) either has an interior symmetric equilibrium or there is a pure strategy that is weakly dominated by some mixed strategy. Weakly dominated pure strategies can be detected and eliminated in polynomial time by solving a linear program. Furthermore, interior symmetric equilibria are a special case of a more general notion, namely, that of an "equalizer," which can also be computed efficiently in polynomial time by solving a linear program. An elegant "symmetrization method" of bimatrix games [Jurg et al., 1992] and the well-known PPAD-completeness results on equilibrium computation in bimatrix games [Daskalakis et al., 2009, Chen et al., 2009] imply then the compelling P = PPAD.
• Abstract（参考訳）: ゲーム理論的思考実験(および相対エントロピー関数を持つ乗算重みの合成に関する重要な凸性結果)において乗算重みを用いることにより、対称二行列ゲーム(つまり、各プレイヤーのペイオフ行列が他のプレイヤーのペイオフ行列の変換であるビマトリクス行列)が内部対称平衡を持つか、あるいは何らかの混合戦略によって弱支配される純粋な戦略が存在することを示す。 線形プログラムを解くことで、弱支配的な純粋な戦略を多項式時間で検出・排除することができる。 さらに、内部対称平衡は、より一般的な概念、すなわち「等化器」の特別な場合であり、線形プログラムを解くことで多項式時間でも効率的に計算できる。 ビマトリクスゲーム (Jurg et al , 1992) のエレガントな「対称性化法」と、ビマトリクスゲーム (Daskalakis et al , 2009 Chen et al , 2009) の平衡計算におけるよく知られたPPAD完全性の結果は、説得力のある P = PPAD を示唆する。

関連論文リスト

• Optimistic Online Learning in Symmetric Cone Games [3.124884279860061]
  そこで我々は,Optimistic Symmetric Cone Multiplicative Weights Updateアルゴリズムを導入し,$mathcalO(1/epsilon)$の反復複雑性を確立し,$epsilon$-saddle点に達する。 重要な技術的貢献は、トレースワンノルムに対する対称錐負のエントロピーの強い凸性の新たな証明である。
  論文  参考訳（メタデータ） (2025-04-04T16:59:19Z)
• Irreducible matrix representations for the walled Brauer algebra [0.9374652839580183]
  本稿では、部分転置置換作用素の代数の表現論、$mathcalAd_p,p$について考察する。 これは抽象壁付きブラウアー代数に対する行列表現を提供する。 この代数学は近年、量子情報理論の関連性から大きな注目を集めている。
  論文  参考訳（メタデータ） (2025-01-22T18:22:20Z)
• Computing Game Symmetries and Equilibria That Respect Them [77.72705755558839]
  ゲームにおける対称性の同定と利用の計算について検討する。 ゲーム対称性とグラフ自己同型の間には強い関係がある。 与えられた対称性の集合を尊重するナッシュ均衡を求めることは、ブラウワーの不動点や勾配降下問題と全く同じほど難しいことを示す。
  論文  参考訳（メタデータ） (2025-01-15T16:15:16Z)
• Error analysis of quantum operators written as a linear combination of permutations [0.0]
  我々は、置換の線形結合として与えられる行列を考慮し、固有値の摂動に対するビットと位相フリップの影響を分析する。 線形結合の係数が正となると、行列の固有値が量子ビットフリップ誤差に対するレジリエンスを示すことが観察される。 混合符号係数を持つ行列はビットフリップと位相フリップの誤差に対するレジリエンスが低いが、数値的な証拠は固有スペクトルの摂動が小さい場合に非常に小さいことを示している。
  論文  参考訳（メタデータ） (2024-12-17T10:27:10Z)
• Understanding Matrix Function Normalizations in Covariance Pooling through the Lens of Riemannian Geometry [63.694184882697435]
  グローバル共分散プーリング(GCP)は、高レベルの表現の2階統計を利用して、ディープニューラルネットワーク(DNN)の性能を向上させることが実証されている。 本稿では、リーマン幾何学の観点から行列対数とパワーの包括的かつ統一的な理解を提供する。
  論文  参考訳（メタデータ） (2024-07-15T07:11:44Z)
• Multiplicative Updates for Online Convex Optimization over Symmetric Cones [28.815822236291392]
  任意の対称コーンのトレースワンスライスに対するオンライン最適化のためのプロジェクションフリーアルゴリズムであるSymmetric-Cone Multiplicative Weights Update (SCMWU)を導入する。 SCMWUは, 対称錐負エントロピーを正則化器とするFollow-the-Regularized-LeaderおよびOnline Mirror Descentと等価であることを示す。
  論文  参考訳（メタデータ） (2023-07-06T17:06:43Z)
• Vectorization of the density matrix and quantum simulation of the von Neumann equation of time-dependent Hamiltonians [65.268245109828]
  我々は、von-Neumann方程式を線形化するための一般的なフレームワークを開発し、量子シミュレーションに適した形でレンダリングする。 フォン・ノイマン方程式のこれらの線型化のうちの1つは、状態ベクトルが密度行列の列重ね元となる標準的な場合に対応することを示す。 密度行列の力学をシミュレートする量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-14T23:08:51Z)
• Quantum algorithms for matrix operations and linear systems of equations [65.62256987706128]
  本稿では,「Sender-Receiver」モデルを用いた行列演算のための量子アルゴリズムを提案する。 これらの量子プロトコルは、他の量子スキームのサブルーチンとして使用できる。
  論文  参考訳（メタデータ） (2022-02-10T08:12:20Z)
• Sublinear Time Approximation of Text Similarity Matrices [50.73398637380375]
  一般的なNystr"om法を不確定な設定に一般化する。 我々のアルゴリズムは任意の類似性行列に適用でき、行列のサイズでサブ線形時間で実行される。 本手法は,CUR分解の単純な変種とともに,様々な類似性行列の近似において非常によく機能することを示す。
  論文  参考訳（メタデータ） (2021-12-17T17:04:34Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  非PSDおよび2乗根行列の次元削減法を提案する。 複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2021-06-16T04:07:48Z)
• Adversarially-Trained Nonnegative Matrix Factorization [77.34726150561087]
  非負行列ファクタリゼーションの逆学習版を検討する。 我々の定式化では、攻撃者は与えられたデータ行列に有界ノルムの任意の行列を追加する。 辞書と係数行列を最適化するために, 逆学習に触発された効率的なアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-04-10T13:13:17Z)
• J-matrix method of scattering in one dimension: The relativistic theory [0.0]
  散乱の一次元J行列法の相対論的拡張を行う。 相対論的ポテンシャル行列はベクトル、スカラー、擬スカラー成分の組み合わせである。
  論文  参考訳（メタデータ） (2020-01-14T19:02:15Z)

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

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