論文の概要: Almost perfect strategies for projection games are approximately tracial
- arxiv url: http://arxiv.org/abs/2603.14746v1
- Date: Mon, 16 Mar 2026 02:33:01 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-17 16:19:36.005668
- Title: Almost perfect strategies for projection games are approximately tracial
- Title（参考訳）: プロジェクションゲームにおけるほぼ完璧な戦略は、ほぼトランザクショナルである
- Authors: Eric Culf,
- Abstract要約: プロジェクションゲームにおいて、確率1-varepsilon$で勝つ戦略は、確率1-O((Lvarepsilon)1/4)$で勝つ戦略をもたらすことを示す。
制約システムゲームでは、制約数への依存を排除し、パドックの丸め結果を強化する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Projection games constitute an important class of nonlocal games where, for any answer from the first player, there is a unique correct answer for the second player. This class of games captures nonlocal games arising from constraint satisfaction problems, oracularisations, and unique games. However, due to the asymmetry between the players, projection games are in general not synchronous, and therefore the powerful results constraining the structure of almost perfect strategies for synchronous games do not apply. In this work, we adapt results of Marrakchi and de la Salle for synchronous games to show that, in both the quantum and commuting-operator models, any strategy that wins with probability $1-\varepsilon$ in a projection game gives rise to a tracial strategy that wins with probability $1-O((L\varepsilon)^{1/4})$, where $L$ is the inverse of the minimal conditional probability of a question for the second player being sampled given a question to the first. For constraint system games, this strengthens the rounding result of Paddock by eliminating the dependence on number of constraints and improving the dependence on constraint size, while also generalising to the commuting-operator setting.
- Abstract（参考訳）: プロジェクションゲームは、第1のプレイヤーからの任意の回答に対して、第2のプレイヤーに固有の正解があるような、非ローカルゲームの重要なクラスを構成する。
このタイプのゲームは、制約満足度問題、オラクル化、ユニークなゲームから生じる非局所的なゲームをキャプチャする。
しかし、プレイヤー間の非対称性のため、プロジェクションゲームは一般に同期ではないため、同期ゲームに対するほぼ完璧な戦略の構造を制約する強力な結果が適用されない。
本研究において、同期ゲームにおいて、Marrakchi と de la Salle の結果を適用し、量子および可換演算モデルの両方において、確率1-\varepsilon$ の射影ゲームにおいて、確率1-O((L\varepsilon)^{1/4})$ の確率で勝利する任意の戦略は、第1の質問に対してサンプリングされた第2のプレイヤーに対する質問の最小条件確率の逆であることを示す。
制約システムゲームでは、制約数への依存を排除し、制約サイズへの依存を改善するとともに、通勤操作設定に一般化することにより、パドックの丸め結果を強化する。
関連論文リスト
- Two-Player Zero-Sum Games with Bandit Feedback [6.66618805642802]
本研究では,行プレーヤが敵列プレーヤに対する報酬を最大化することを目的とした2プレイヤーゼロサムゲームについて検討する。
本研究では,Explore-Then-Commitフレームワークに基づく3つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-06-17T13:46:32Z) - Quantum strategies, error bounds, optimality, and duality gaps for multiplayer XOR, $\mathrm{XOR}^{*}$, compiled XOR, $\mathrm{XOR}^{*}$, and strong parallel repetiton of XOR, $\mathrm{XOR}^{*}$, and FFL games [0.0]
我々は、プレイヤーが量子戦略を用いて操作できるゲームの正確で近似的な最適性を特徴づける。
我々は、量子優位性のための提案された情報源として、他の可能な戦略の変種を記述することで、この取り組みを締めくくる。
論文 参考訳（メタデータ） (2025-05-09T03:47:41Z) - Swap Regret and Correlated Equilibria Beyond Normal-Form Games [62.01542145970044]
「我々は、プロファイルスワップ後悔と呼ぶポリトープゲームのスワップ後悔の新しい変種を提示する。」
プロファイルスワップ後悔は、プレイの書き起こしが与えられた場合、NPハードであることが示されるが、少なくとも$O(sqrtT)$プロファイルスワップ後悔を保証する効率的な学習アルゴリズムを設計することは可能である。
論文 参考訳（メタデータ） (2025-02-27T16:16:26Z) - Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games [21.168085154982712]
マルチプレイヤーゲームにおける平衡は、一意でも爆発的でもない。
本稿では,平等な共有という自然な目的に焦点をあてることで,これらの課題に対処するための最初の一歩を踏み出す。
我々は、様々な設定でほぼ同じシェアを確実に得る、非回帰学習にインスパイアされた、一連の効率的なアルゴリズムを設計する。
論文 参考訳（メタデータ） (2024-06-06T15:59:17Z) - Abstracting Imperfect Information Away from Two-Player Zero-Sum Games [85.27865680662973]
Nayyar et al. (2013) は、プレイヤーがプレイ中にポリシーを公に発表することで、不完全な情報を共通のペイオフゲームから抽象化できることを示した。
この研究は、ある正規化された平衡が上記の非対応問題を持たないことを示している。
これらの正規化された平衡はナッシュ平衡に任意に近づくことができるので、この結果は2つのプレイヤーゼロサムゲームを解くための新たな視点への扉を開く。
論文 参考訳（メタデータ） (2023-01-22T16:54:06Z) - Finding mixed-strategy equilibria of continuous-action games without
gradients using randomized policy networks [83.28949556413717]
グラデーションへのアクセスを伴わない連続アクションゲームのナッシュ平衡を近似的に計算する問題について検討する。
ニューラルネットワークを用いてプレイヤーの戦略をモデル化する。
本論文は、制約のない混合戦略と勾配情報のない一般的な連続アクションゲームを解決する最初の方法である。
論文 参考訳（メタデータ） (2022-11-29T05:16:41Z) - Learning in Multi-Player Stochastic Games [1.0878040851638]
有限ホライズン設定において、多くのプレイヤーとゲームにおける同時学習の問題を考える。
ゲームの典型的な対象解はナッシュ均衡であるが、これは多くのプレイヤーにとって難解である。
我々は異なるターゲットに目を向ける:全てのプレイヤーが使用するときの平衡を生成するアルゴリズム。
論文 参考訳（メタデータ） (2022-10-25T19:02:03Z) - Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
我々は平均場相関と粗相関平衡の概念を発展させる。
ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
論文 参考訳（メタデータ） (2022-08-22T08:31:46Z) - Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation [78.48747645545944]
ワイドフォームゲームにおいて,様々な種類の最適平衡を求める問題について検討する。
これら3つの概念のすべてに最適な平衡を計算するための新しいアルゴリズムを導入する。
論文 参考訳（メタデータ） (2022-03-14T15:21:18Z) - Rigidity for Monogamy-of-Entanglement Games [0.6091702876917281]
本研究では,レフェリーが算術的・アダマール的に測定するゲームのプロトタイプ事例について検討する。
このゲームは、いくつかの非局所ゲームで知られているような剛性特性を満たすことを示す。
また,並列にプレイするゲームの複数のコピーに対して剛性を示す。
論文 参考訳（メタデータ） (2021-11-15T20:59:17Z) - A Variational Inequality Approach to Bayesian Regression Games [90.79402153164587]
我々は凸類の一意性の存在を証明し、それを滑らかなコスト関数に一般化する。
必然的に強い収束で解くための2つの簡単なアルゴリズムを提供する。
論文 参考訳（メタデータ） (2021-03-24T22:33:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。