論文の概要: Computing Game Symmetries and Equilibria That Respect Them

• arxiv url: http://arxiv.org/abs/2501.08905v1
• Date: Wed, 15 Jan 2025 16:15:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-16 15:51:35.084486
• Title: Computing Game Symmetries and Equilibria That Respect Them
• Title（参考訳）: ゲーム対称性と考慮すべき平衡
• Authors: Emanuel Tewolde, Brian Hu Zhang, Caspar Oesterheld, Tuomas Sandholm, Vincent Conitzer,
• Abstract要約: ゲームにおける対称性の同定と利用の計算について検討する。 ゲーム対称性とグラフ自己同型の間には強い関係がある。 与えられた対称性の集合を尊重するナッシュ均衡を求めることは、ブラウワーの不動点や勾配降下問題と全く同じほど難しいことを示す。
• 参考スコア（独自算出の注目度）: 77.72705755558839
• License:
• Abstract: Strategic interactions can be represented more concisely, and analyzed and solved more efficiently, if we are aware of the symmetries within the multiagent system. Symmetries also have conceptual implications, for example for equilibrium selection. We study the computational complexity of identifying and using symmetries. Using the classical framework of normal-form games, we consider game symmetries that can be across some or all players and/or actions. We find a strong connection between game symmetries and graph automorphisms, yielding graph automorphism and graph isomorphism completeness results for characterizing the symmetries present in a game. On the other hand, we also show that the problem becomes polynomial-time solvable when we restrict the consideration of actions in one of two ways. Next, we investigate when exactly game symmetries can be successfully leveraged for Nash equilibrium computation. We show that finding a Nash equilibrium that respects a given set of symmetries is PPAD- and CLS-complete in general-sum and team games respectively -- that is, exactly as hard as Brouwer fixed point and gradient descent problems. Finally, we present polynomial-time methods for the special cases where we are aware of a vast number of symmetries, or where the game is two-player zero-sum and we do not even know the symmetries.
• Abstract（参考訳）: 戦略的相互作用はより簡潔に表現され、マルチエージェントシステム内の対称性に気付いていれば、より効率的に解析され、解決される。 対称性は、例えば平衡選択のような概念的な意味を持つ。 対称性の同定と利用の計算複雑性について検討する。 正規形式のゲームの古典的な枠組みを用いて、一部のまたはすべてのプレイヤーおよび/またはアクションにまたがるゲーム対称性を考える。 ゲーム対称性とグラフ自己同型との間に強い結びつきがあり、ゲームに存在する対称性を特徴づけるためのグラフ自己同型とグラフ同型完全性の結果が得られる。 一方,動作の考慮を2つの方法の1つに制限した場合,多項式時間解法が問題となることも示している。 次に,Nash平衡計算にゲーム対称性を正確に活用する方法について検討する。 与えられた対称性の集合を尊重するナッシュ均衡を求めることは、一般のサムゲームとチームゲームにおいてそれぞれPPAD-およびCRS-完全であることが示される。 最後に,多数の対称性を認識している,あるいはゲームが2つのプレイヤーゼロサムであり,その対称性さえ知らない,特別な場合の多項式時間法を提案する。

関連論文リスト

• Non-invertible SPT, gauging and symmetry fractionalization [2.541410020898643]
  我々はRep($Q_8$)双対性Webにおけるすべての対称性の位相の格子モデルを構築する。 これらの相互作用は、2+1dバルクSETの対称性分数化を用いて説明できることを示す。
  論文  参考訳（メタデータ） (2024-05-24T21:35:55Z)
• Equivariant Symmetry Breaking Sets [0.6475999521931204]
  等価ニューラルネットワーク(ENN)は、基礎となる対称性を含むアプリケーションに非常に効果的であることが示されている。 完全同変で、自発対称性の破れに対処する最初のフレームワークである新しい対称性破れフレームワークを提案する。
  論文  参考訳（メタデータ） (2024-02-05T02:35:11Z)
• Learning Layer-wise Equivariances Automatically using Gradients [66.81218780702125]
  畳み込みは等価対称性をニューラルネットワークにエンコードし、より優れた一般化性能をもたらす。 対称性は、ネットワークが表現できる機能、事前に指定する必要、適応できない機能に対して、固定されたハード制約を提供する。 私たちのゴールは、勾配を使ってデータから自動的に学習できるフレキシブル対称性の制約を可能にすることです。
  論文  参考訳（メタデータ） (2023-10-09T20:22:43Z)
• Symmetry Induces Structure and Constraint of Learning [0.0]
  機械学習モデルの学習行動に影響を及ぼすか、決定しないかにかかわらず、損失関数対称性の重要性を明らかにする。 ディープラーニングにおけるミラー対称性の一般的な例としては、再スケーリング、回転、置換対称性がある。 ニューラルネットワークにおける可塑性の喪失や様々な崩壊現象などの興味深い現象を理論的枠組みで説明できることを示す。
  論文  参考訳（メタデータ） (2023-09-29T02:21:31Z)
• Towards fully covariant machine learning [0.0]
  機械学習において、最も可視的な受動的対称性はグラフの可逆対称性または置換対称性である。 受動的対称性を尊重すべきならば,機械学習の実践について,dos と not について議論する。
  論文  参考訳（メタデータ） (2023-01-31T16:01:12Z)
• Deep Learning Symmetries and Their Lie Groups, Algebras, and Subalgebras from First Principles [55.41644538483948]
  ラベル付きデータセットに存在する連続した対称性群の検出と同定のためのディープラーニングアルゴリズムを設計する。 完全に接続されたニューラルネットワークを用いて、変換対称性と対応するジェネレータをモデル化する。 また,Lie群とその性質の数学的研究に機械学習アプローチを使うための扉を開く。
  論文  参考訳（メタデータ） (2023-01-13T16:25:25Z)
• Quantum Mechanics as a Theory of Incompatible Symmetries [77.34726150561087]
  古典確率論が非互換変数を持つ任意の系を含むように拡張可能であることを示す。 非互換な変数を持つ確率的システム(古典的あるいは量子的)が不確実性だけでなく、その確率パターンにも干渉することを示す。
  論文  参考訳（メタデータ） (2022-05-31T16:04:59Z)
• Quantum guessing games with posterior information [68.8204255655161]
  後続情報を持つ量子推測ゲームは、量子システムを用いてメッセージと古典的な通信を符号化し、量子測定が実行された後に部分的な情報を与える。 我々は、推理ゲームの対称性を定式化し、対称性が既約表現と関連している場合の最適測定を特徴付ける。
  論文  参考訳（メタデータ） (2021-07-25T19:10:26Z)
• Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games [78.65798135008419]
  一般的なゲームでStackelberg平衡を効率的に学習する方法は、サンプルから非常にオープンなままです。 本稿では,2プレーヤターンベース汎用ゲームにおけるStackelberg平衡のサンプル効率学習に関する理論的研究を開始する。
  論文  参考訳（メタデータ） (2021-02-23T05:11:07Z)
• Quantifying Algebraic Asymmetry of Hamiltonian Systems [0.0]
  我々は、ハミルトニアン系の対称性を、ある代数に対するハミルトニアンの非対称性について研究することによって研究する。 q$で変形した可積分スピンチェーンモデルの非対称性が計算される。
  論文  参考訳（メタデータ） (2020-01-08T08:12:20Z)

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

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