Almost perfect strategies for projection games are approximately tracial

• URL: http://arxiv.org/abs/2603.14746v1
• Date: Mon, 16 Mar 2026 02:33:01 GMT
• Title: Almost perfect strategies for projection games are approximately tracial
• Abstract summary: We show that strategies that win with probability $1-varepsilon$ in a projection game give rise to a tracial strategy that wins with probability $1-O((Lvarepsilon)1/4)$.<n>For constraint system games, this strengthens the rounding result of Paddock by eliminating the dependence on number of constraints.
• Score: 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.

Related papers

• Independent Reinforcement Learning in Discounted Markov Games [5.5438676149999075]
  We show for every fixed discount factor, there is no-time algorithm for inverse-polynomially accurate coarse correlated equilibria in discounted general-sum Markov games.<n>Our algorithm is a emphlayered variant of optimistic mirror descent with an increasing step-size schedule tailored to the multi-agent setting.
  arXiv  Detail & Related papers  (2026-09-01T00:07:45Z)
• Two-Player Zero-Sum Games with Bandit Feedback [6.66618805642802]
  We study a two-player zero-sum game in which the row player aims to maximize their payoff against an adversarial column player.<n>We propose three algorithms based on the Explore-Then-Commit framework.
  arXiv  Detail & Related papers  (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]
  We characterize exact, and approximate, optimality of games that players can interact with using quantum strategies.<n>We conclude this effort by describing other variants of other possible strategies, as proposed sources for quantum advantage.
  arXiv  Detail & Related papers  (2025-05-09T03:47:41Z)
• Swap Regret and Correlated Equilibria Beyond Normal-Form Games [62.01542145970044]
  We present a new variant of swap regret for polytope games that we call profile swap regret''<n>Although we show profile swap regret is NP-hard to compute given a transcript of play, we show it is nonetheless possible to design efficient learning algorithms that guarantee at most $O(sqrtT)$ profile swap regret.
  arXiv  Detail & Related papers  (2025-02-27T16:16:26Z)
• Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games [21.168085154982712]
  equilibria in multiplayer games are neither unique nor non-exploitable. This paper takes an initial step towards addressing these challenges by focusing on the natural objective of equal share. We design a series of efficient algorithms, inspired by no-regret learning, that provably attain approximate equal share across various settings.
  arXiv  Detail & Related papers  (2024-06-06T15:59:17Z)
• Abstracting Imperfect Information Away from Two-Player Zero-Sum Games [85.27865680662973]
  Nayyar et al. (2013) showed that imperfect information can be abstracted away from common-payoff games by having players publicly announce their policies as they play. This work shows that certain regularized equilibria do not possess the aforementioned non-correspondence problem. Because these regularized equilibria can be made arbitrarily close to Nash equilibria, our result opens the door to a new perspective to solving two-player zero-sum games.
  arXiv  Detail & Related papers  (2023-01-22T16:54:06Z)
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks [83.28949556413717]
  We study the problem of computing an approximate Nash equilibrium of continuous-action game without access to gradients. We model players' strategies using artificial neural networks. This paper is the first to solve general continuous-action games with unrestricted mixed strategies and without any gradient information.
  arXiv  Detail & Related papers  (2022-11-29T05:16:41Z)
• Learning in Multi-Player Stochastic Games [1.0878040851638]
  We consider the problem of simultaneous learning in games with many players in the finite-horizon setting. While the typical target solution for a game is a Nash equilibrium, this is intractable with many players. We turn to a different target: algorithms which generate an equilibrium when they are used by all players.
  arXiv  Detail & Related papers  (2022-10-25T19:02:03Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  We develop the concepts of Mean-Field correlated and coarse-correlated equilibria. We show that they can be efficiently learnt in emphall games, without requiring any additional assumption on the structure of the game.
  arXiv  Detail & Related papers  (2022-08-22T08:31:46Z)
• Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
  We show that regret can be obtained for general convex and compact strategy sets. Our dynamics are on an instantiation of optimistic follow-the-regularized-bounds over an appropriately emphlifted space. Even in those special cases where prior results apply, our algorithm improves over the state-of-the-art regret.
  arXiv  Detail & Related papers  (2022-06-17T12:58:58Z)
• Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation [78.48747645545944]
  We study the problem of finding optimal correlated equilibria of various sorts in extensive-form games. We introduce a new algorithm for computing optimal equilibria in all three notions.
  arXiv  Detail & Related papers  (2022-03-14T15:21:18Z)
• Rigidity for Monogamy-of-Entanglement Games [0.6091702876917281]
  We study the prototypical example of a game where the referee measures in either the computational or Hadamard basis. We show that this game satisfies a rigidity property similar to what is known for some nonlocal games. We also show rigidity for multiple copies of the game played in parallel.
  arXiv  Detail & Related papers  (2021-11-15T20:59:17Z)
• A Variational Inequality Approach to Bayesian Regression Games [90.79402153164587]
  We prove the existence of the uniqueness of a class of convex and generalize it to smooth cost functions. We provide two simple algorithms of solving them with necessarily strong convergence.
  arXiv  Detail & Related papers  (2021-03-24T22:33:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.