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

• URL: http://arxiv.org/abs/2505.06322v2
• Date: Wed, 25 Jun 2025 20:31:38 GMT
• Title: 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
• Authors: Pete Rigas,
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We characterize exact, and approximate, optimality of games that players can interact with using quantum strategies. In comparison to a previous work of the author, arXiv: 2311.12887, which applied a 2016 framework due to Ostrev for constructing error bounds beyond CHSH and XOR games, in addition to the existence of well-posed semidefinite programs for determining primal feasible solutions, along with quantum-classical duality gaps, it continues to remain of interest to further develop the construction of error bounds, and related objects, to game-theoretic settings with several participants. In such settings, one encounters a rich information theoretic landscape, not only from the fact that there exists a significantly larger combinatorial space of possible strategies for each player, but also several opportunities for pronounced quantum advantage. We conclude this effort by describing other variants of other possible strategies, as proposed sources for quantum advantage, in $\mathrm{XOR}^{*}$, compiled $\mathrm{XOR}^{*}$, and strong parallel repetition variants of $\mathrm{XOR}^{*}$ games.

Related papers

• Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback [60.610120215789976]
  We show that when a pure strategy Nash equilibrium exists, $c$ becomes zero, leading to an optimal instance-dependent regret bound.<n>Our algorithm also enjoys last-iterate convergence and can identify the pure strategy Nash equilibrium with near-optimal sample.
  arXiv  Detail & Related papers  (2025-02-24T20:20:06Z)
• A Computational Tsirelson's Theorem for the Value of Compiled XOR Games [9.818381970014284]
  We show that the compiler proposed by Kalai et al. is sound for any two-player XOR game. Using our techniques, we obtain several additional results, including tight bounds on the compiled value of parallel-repeated XOR games.
  arXiv  Detail & Related papers  (2024-02-27T08:24:21Z)
• Optimal, and approximately optimal, quantum strategies for $\mathrm{XOR}^{*}$ and $\mathrm{FFL}$ games [0.0]
  We analyze optimal, and approximately optimal, quantum strategies for a variety of non-local XOR games. We identify additional applications of the framework for analyzing the performance of a broader class of quantum strategies.
  arXiv  Detail & Related papers  (2023-11-21T04:03:26Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  We show that Nash equilibrium (NE) is acceptable to all players in a multi-player game. We also show that no one can benefit unilaterally from the general theory step by step.
  arXiv  Detail & Related papers  (2023-01-19T11:36:50Z)
• Connecting XOR and XOR* games [0.0]
  We focus on two classes of games: XOR nonlocal games and XOR* sequential games with monopartite resources. We prove that under certain assumptions these two classes of games can be related via an explicit theorem that connects their optimal strategies.
  arXiv  Detail & Related papers  (2022-10-02T00:11:38Z)
• 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)
• Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
  We present the first line of algorithms that require only $widetildemathcalO((XA+YB)/varepsilon2)$ episodes of play to find an $varepsilon$-approximate Nash equilibrium in two-player zero-sum games. This improves upon the best known sample complexity of $widetildemathcalO((X2A+Y2B)/varepsilon2)$ by a factor of $widetildemathcalO(maxX,
  arXiv  Detail & Related papers  (2022-02-03T18:18:28Z)
• On the relation between completely bounded and $(1,cb)$-summing maps with applications to quantum XOR games [65.51757376525798]
  We show that given a linear map from a general operator space into the dual of a C$*$-algebra, its completely bounded norm is upper bounded by a universal constant times its $(''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
  arXiv  Detail & Related papers  (2021-12-09T21:06:52Z)
• Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
  We focus on self-play algorithms which learn the optimal policy by playing against itself without any direct supervision. We propose an optimistic variant of the emphNash Q-learning algorithm with sample complexity $tildemathcalO(SAB)$, and a new emphNash V-learning algorithm with sample complexity $tildemathcalO(S(A+B))$.
  arXiv  Detail & Related papers  (2020-06-22T05:00:13Z)
• Quantum-over-classical Advantage in Solving Multiplayer Games [0.0]
  Subtraction games are sometimes referred to as one-heap Nim games. In quantum game theory, a subset of Subtraction games became the first explicitly defined class of zero-sum games. For a narrower subset of Subtraction games, an exact quantum sublinear algorithm is known that surpasses all deterministic algorithms.
  arXiv  Detail & Related papers  (2020-06-12T06:36:07Z)
• Complexity limitations on one-turn quantum refereed games [0.6091702876917281]
  The paper studies theoretic aspects of quantum refereed games. The abstract games are between two competing players that send quantum states to a referee. The referee performs an efficiently implementable joint measurement on the two states to determine which of the player wins.
  arXiv  Detail & Related papers  (2020-02-04T19:28:03Z)

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.