論文の概要: Noncommutative Nullstellens\"atze and Perfect Games
- arxiv url: http://arxiv.org/abs/2111.14928v2
- Date: Wed, 1 Dec 2021 16:36:02 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-06 09:16:52.818766
- Title: Noncommutative Nullstellens\"atze and Perfect Games
- Title（参考訳）: Noncommutative Nullstellens\"atze and Perfect Games
- Authors: Adam Bene Watts, John William Helton, Igor Klep
- Abstract要約: 古典的代数幾何学と実代数幾何学の基礎は、ヌルサッツとポシティフサッツである。
本稿では,非ローカルゲームにおける通信事業者戦略について述べる。
結果は異なる文献にまたがるので、簡潔であるよりむしろ、我々のスタイルはかなり実証的だ。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The foundations of classical Algebraic Geometry and Real Algebraic Geometry
are the Nullstellensatz and Positivstellensatz. Over the last two decades the
basic analogous theorems for matrix and operator theory (noncommutative
variables) have emerged. This paper concerns commuting operator strategies for
nonlocal games, recalls NC Nullstellensatz which are helpful, extends these,
and applies them to a very broad collection of games. In the process it brings
together results spread over different literatures, hence rather than being
terse, our style is fairly expository.
The main results of this paper are two characterizations, based on
Nullstellensatz, which apply to games with perfect commuting operator
strategies. The first applies to all games and reduces the question of whether
or not a game has a perfect commuting operator strategy to a question involving
left ideals and sums of squares. Previously, Paulsen and others translated the
study of perfect synchronous games to problems entirely involving a
$*$-algebra.The characterization we present is analogous, but works for all
games. The second characterization is based on a new Nullstellensatz we derive
in this paper. It applies to a class of games we call torically determined
games, special cases of which are XOR and linear system games. For these games
we show the question of whether or not a game has a perfect commuting operator
strategy reduces to instances of the subgroup membership problem and, for
linear systems games, we further show this subgroup membership characterization
is equivalent to the standard characterization of perfect commuting operator
strategies in terms of solution groups. Both the general and torically
determined games characterizations are amenable to computer algebra techniques,
which we also develop.
- Abstract（参考訳）: 古典代数幾何学と実代数幾何学の基礎は nullstellensatz と positivstellensatz である。
過去20年間で、行列と作用素理論(非可換変数)の基本的な類似定理が出現した。
本稿では,非ローカルゲームにおけるオペレータ戦略の通勤,有用なnc nullstellensatzのリコール,これらを拡張し,非常に幅広いゲームに適用する。
異なる文献にまたがって結果をまとめる過程において、簡潔である代わりに、我々のスタイルはかなり実証的だ。
本論文の主な結果は,完全可換作用素戦略を持つゲームに適用可能なnullstellensatzに基づく2つのキャラクタリゼーションである。
1つ目は全てのゲームに適用し、ゲームが完全通勤操作者戦略を持っているかどうかという問題を左イデアルと平方の和を含む問題に還元する。
これまでpaulsenらは、完全同期ゲームの研究を、$*$-algebraを含む問題に翻訳した。
第2のキャラクタリゼーションは、この論文で導かれる新しいnullstellensatzに基づいている。
XOR や線形システムゲームといった、トーラス的に決定されたゲームのクラスに適用される。
これらのゲームに対して、ゲームが完全可換作用素戦略を持つか否かは、サブグループのメンバシップ問題の事例に還元され、線形システムゲームでは、このサブグループのメンバシップ特性は、解群の観点からの完全可換作用素戦略の標準的な特徴と等価であることを示す。
一般ゲームとトーラスゲームの両方の特徴付けは、コンピュータ代数技術にも適用可能である。
関連論文リスト
- Runtime analysis of a coevolutionary algorithm on impartial combinatorial games [1.104960878651584]
進化的アルゴリズム(CoEA)は、現代人との相互作用に基づいて最強を反復的に選択し、次の世代で両親として選択した個体群を用いて、個体群を進化させる。
しかし,CoEAのゲームプレイへの応用はサイクリングなどの病理的行動のため,実行時のペイオフ状況において特に問題となる。
本稿では,解析の範囲を推し進め,公平なゲームのための最適な戦略を見出す。
この結果はどんな公平なゲームにも当てはまり、多くのゲームでは、インプリッド・バウンドは数の関数として、あるいは準ポリノミアルである。
論文 参考訳（メタデータ） (2024-09-06T10:39:17Z) - Imperfect-Recall Games: Equilibrium Concepts and Their Complexity [74.01381499760288]
エージェントが以前保持していた情報を忘れたとき、不完全なリコールの下で最適な意思決定を行う。
不完全なリコールを伴う広範囲形式のゲームフレームワークにおいて、マルチプレイヤー設定における平衡を求める際の計算複雑性を解析する。
論文 参考訳（メタデータ） (2024-06-23T00:27:28Z) - A Characterization of Perfect Strategies for Mirror Games [0.0]
ミラーゲームとユニバーサルゲーム代数を関連付け、*-表現を用いて量子可換作用素戦略を記述する。
ミラーゲームが完全可換演算子戦略を持たないことを証明するために、非可換Gr"オブナー基底計算と半定値プログラミングに基づくアルゴリズムが与えられる。
論文 参考訳（メタデータ） (2023-02-09T10:49:06Z) - On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
時間変化ゲームにおける楽観的勾配降下(OGD)の収束を特徴付ける。
我々のフレームワークは、ゼロサムゲームにおけるOGDの平衡ギャップに対して鋭い収束境界をもたらす。
また,静的ゲームにおける動的後悔の保証に関する新たな洞察も提供する。
論文 参考訳（メタデータ） (2023-01-26T17:25:45Z) - Turning Mathematics Problems into Games: Reinforcement Learning and
Gr\"obner bases together solve Integer Feasibility Problems [4.746723775952672]
我々は、線形方程式と不等式の系が整数値の解を持つかどうかを判定する問題である整数実現可能性問題を考察する。
本稿では,エージェントが整数実現可能性問題と同等のゲームをすることができる,新しい代数的強化学習フレームワークについて述べる。
概念実証として、エージェントが2方向テーブルの最も単純なバージョンをうまくプレイできることを実験で実証する。
論文 参考訳（メタデータ） (2022-08-25T16:24:34Z) - Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
我々は平均場相関と粗相関平衡の概念を発展させる。
ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
論文 参考訳（メタデータ） (2022-08-22T08:31:46Z) - Provably Efficient Fictitious Play Policy Optimization for Zero-Sum
Markov Games with Structured Transitions [145.54544979467872]
本研究では,ゼロサムマルコフゲームに対して,構造的だが未知の遷移を伴う架空のプレイポリシー最適化アルゴリズムを提案し,解析する。
我々は、2年制の競争ゲームシナリオで、$K$のエピソードに続き、$widetildemathcalO(sqrtK)$ regret boundsを証明した。
提案アルゴリズムは,アッパー信頼境界(UCB)型最適化と,同時政策最適化の範囲内での架空のプレイの組み合わせを特徴とする。
論文 参考訳（メタデータ） (2022-07-25T18:29:16Z) - Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
一般凸およびコンパクト戦略集合に対して後悔が得られることを示す。
我々の力学は、適度にエンハンリフトされた空間上の楽観的な従順化バウンドのインスタンス化にある。
先行結果が適用される特殊な場合であっても、我々のアルゴリズムは最先端の後悔よりも改善される。
論文 参考訳（メタデータ） (2022-06-17T12:58:58Z) - No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
固定ゼロサムゲームにおける繰り返しプレイからの学習は、ゲーム理論とオンライン学習における古典的な問題である。
提案手法は,3つの性能基準の下で,良好な保証を同時に享受できる1つのパラメータフリーアルゴリズムである。
本アルゴリズムは,ある特性を満たすブラックボックスベースラーナー群に対するメタアルゴリズムを用いた2層構造に基づく。
論文 参考訳（メタデータ） (2022-01-30T06:10:04Z) - 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) - Synchronous linear constraint system games [0.0]
ゲーム代数は解群の群代数の適当な商であることを示す。
また、線形制約系ゲームは、線形系によってパラメータ化されたグラフの対上のグラフ同型ゲームと等価であることを示す。
論文 参考訳（メタデータ） (2020-07-06T14:31:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。