論文の概要: Nimber-Preserving Reductions and Homomorphic Sprague-Grundy Game Encodings

• arxiv url: http://arxiv.org/abs/2109.05622v1
• Date: Sun, 12 Sep 2021 22:12:13 GMT
• ステータス: 処理完了
• システム内更新日: 2021-09-14 15:16:52.924797
• Title: Nimber-Preserving Reductions and Homomorphic Sprague-Grundy Game Encodings
• Title（参考訳）: ニムバー保存と同型スプラグ・グランディゲーム符号化
• Authors: Kyle Burke, Matthew Ferland, Shanghua Teng
• Abstract要約: ニバーは、その可算和と可算性において、不分ゲーム間の戦略的相互作用の完全な特徴づけを提供する。 Generalized Geography が自然クラス $calIP$ に対して完備であることを証明する。 また、$calIP$のすべてのPSPACE完全ルールセットが$calIP$のSprague-Grundy-completeであることも示しています。
• 参考スコア（独自算出の注目度）: 1.471992435706872
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The concept of nimbers--a.k.a. Grundy-values or nim-values--is fundamental to combinatorial game theory. Nimbers provide a complete characterization of strategic interactions among impartial games in their disjunctive sums as well as the winnability. In this paper, we initiate a study of nimber-preserving reductions among impartial games. These reductions enhance the winnability-preserving reductions in traditional computational characterizations of combinatorial games. We prove that Generalized Geography is complete for the natural class, $\cal{I}^P$ , of polynomially-short impartial rulesets under nimber-preserving reductions, a property we refer to as Sprague-Grundy-complete. In contrast, we also show that not every PSPACE-complete ruleset in $\cal{I}^P$ is Sprague-Grundy-complete for $\cal{I}^P$ . By considering every impartial game as an encoding of its nimber, our technical result establishes the following striking cryptography-inspired homomorphic theorem: Despite the PSPACE-completeness of nimber computation for $\cal{I}^P$ , there exists a polynomial-time algorithm to construct, for any pair of games $G_1$, $G_2$ of $\cal{I}^P$ , a prime game (i.e. a game that cannot be written as a sum) $H$ of $\cal{I}^P$ , satisfying: nimber($H$) = nimber($G_1$) $\oplus$ nimber($G_2$).
• Abstract（参考訳）: nimbers--a.k. grundy-values または nim-values-の概念は組合せゲーム理論の基本である。 nimbersは、不公平なゲーム間の戦略的な相互作用を、それらの和とウィンナビリティで完全に特徴づける。 本稿では,公平なゲーム間におけるニンバー保存削減の研究を開始する。 これらの還元は、コンビネータゲームにおける従来の計算特性のウィンナビリティ保存還元を促進する。 一般化地理学は、ニムバー保存還元の下で多項式的にショートなイペンシャルな規則セットの自然類 $\cal{I}^P$ に対して完備であることを証明する。 対照的に、$\cal{I}^P$ のすべての PSPACE 完全規則セットが $\cal{I}^P$ に対して Sprague-Grundy-complete であることも示している。 すべての不偏なゲームをnimberのエンコードとして考えることで、我々の技術的結果は次の印象的な準同型定理を確立している: $\cal{i}^p$ に対するnimber計算のpspace完全性にもかかわらず、任意の対のゲームに対して$g_1$, $g_2$ of $\cal{i}^p$ , 素ゲーム(つまり、和として書けないゲーム)$h$ of $\cal{i}^p$, を満たす: nimber($h$) = nimber($g_1$)$\oplus$ nimber($g_2$)。

関連論文リスト

• Topics in Non-local Games: Synchronous Algebras, Algebraic Graph Identities, and Quantum NP-hardness Reductions [0.0]
  我々は遺伝モデルと$C*$モデルの等価性を証明している(Hlton et al., New York J. Math)。 また、量子変換NP硬度低減$texttt3-SAT* leq_p textttClique*$ も拡張し、この還元の別の例を示す。
  論文  参考訳（メタデータ） (2024-08-19T16:01:21Z)
• Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms [71.73971094342349]
  オンライン学習によるセルフプレイは、大規模な2人プレイのゼロサムゲームを解くための重要な方法の1つだ。 我々は,OMWUが支払行列のサイズに対数依存するなど,いくつかの利点があることを示した。 我々は、過去のことをすぐに忘れない幅広い種類のアルゴリズムが、すべて同じ問題に悩まされていることを証明している。
  論文  参考訳（メタデータ） (2024-06-15T13:26:17Z)
• The complexity of approximate (coarse) correlated equilibrium for incomplete information games [16.96984593866157]
  不完全情報ゲームにおける近似平衡の分散学習の複雑さについて検討する。 我々の下限は、$epsilon$-approximate $mathitco$ correlation equilibriumというより簡単な解の概念にも当てはまる。
  論文  参考訳（メタデータ） (2024-06-04T14:35:27Z)
• Universality of graph homomorphism games and the quantum coloring problem [0.0]
  量子グラフパラメータは、任意の同期非局所ゲームに対する勝利戦略をエンコードすることを示す。 同期ゲームにおける勝利戦略は、関連するグラフカラーゲームに対する勝利戦略に変換することができる。
  論文  参考訳（メタデータ） (2023-05-29T14:28:28Z)
• Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback [49.1061436241109]
  非漸近収束率の非結合、収束、合理的なアルゴリズムの開発に注力する。 我々のアルゴリズムは[Chen et al., 2021, Cen et al., 2021]と関係があり、エントロピー正規化技術に基づいている。
  論文  参考訳（メタデータ） (2023-03-05T18:08:54Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  我々は平均場相関と粗相関平衡の概念を発展させる。 ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
  論文  参考訳（メタデータ） (2022-08-22T08:31:46Z)
• Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
  一般凸およびコンパクト戦略集合に対して後悔が得られることを示す。 我々の力学は、適度にエンハンリフトされた空間上の楽観的な従順化バウンドのインスタンス化にある。 先行結果が適用される特殊な場合であっても、我々のアルゴリズムは最先端の後悔よりも改善される。
  論文  参考訳（メタデータ） (2022-06-17T12:58:58Z)
• Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
  本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。 これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
  論文  参考訳（メタデータ） (2022-02-03T18:18:28Z)
• Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback [29.553652241608997]
  本研究では,テキストモオと強いモノトーンゲームの研究を行い,その学習方法について検討した。 我々はまず,新しい帯域学習アルゴリズムを構築し,$tildeTheta(nsqrtT)$の単一エージェント最適後悔を実現することを示す。 そこで我々は,このオープンな問題を解決し,広範にわたるバンディットゲーム理論学習に寄与した。
  論文  参考訳（メタデータ） (2021-12-06T08:27:54Z)
• Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
  我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。 本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-22T05:00:13Z)

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

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