Noncommutative Nullstellens\"atze and Perfect Games

• URL: http://arxiv.org/abs/2111.14928v2
• Date: Wed, 1 Dec 2021 16:36:02 GMT
• Title: Noncommutative Nullstellens\"atze and Perfect Games
• Authors: Adam Bene Watts, John William Helton, Igor Klep
• Abstract summary: The foundations of classical Algebraic Geometry and Real Algebraic Geometry are the Nullsatz and Positivsatz. This paper concerns commuting operator strategies for nonlocal games. Results are spread over different literatures, hence rather than being terse, our style is fairly expository.
• Score: 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.

Related papers

• Runtime analysis of a coevolutionary algorithm on impartial combinatorial games [1.104960878651584]
  Coevolutionary algorithms (CoEAs) evolve a population of individuals by iteratively selecting the strongest based on their interactions against contemporaries, and using those selected as parents for the following generation. However, the successful application of CoEAs for game playing is difficult due to pathological behaviours such as cycling, an issue especially critical for games with in runtime payoff landscapes. In this paper, we push the scope of analysis to discover an optimal strategy for an impartial game. This result applies to any impartial game, and for many games the implied bound is or quasipolynomial as a function of the number of
  arXiv  Detail & Related papers  (2024-09-06T10:39:17Z)
• Imperfect-Recall Games: Equilibrium Concepts and Their Complexity [74.01381499760288]
  We investigate optimal decision making under imperfect recall, that is, when an agent forgets information it once held before. In the framework of extensive-form games with imperfect recall, we analyze the computational complexities of finding equilibria in multiplayer settings.
  arXiv  Detail & Related papers  (2024-06-23T00:27:28Z)
• A Characterization of Perfect Strategies for Mirror Games [0.0]
  We associate mirror games with the universal game algebra and use the *-representation to describe quantum commuting operator strategies. An algorithm based on noncommutative Gr"obner basis computation and semidefinite programming is given for certifying that a given mirror game has no perfect commuting operator strategies.
  arXiv  Detail & Related papers  (2023-02-09T10:49:06Z)
• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  We characterize the convergence of optimistic gradient descent (OGD) in time-varying games. Our framework yields sharp convergence bounds for the equilibrium gap of OGD in zero-sum games. We also provide new insights on dynamic regret guarantees in static games.
  arXiv  Detail & Related papers  (2023-01-26T17:25:45Z)
• Turning Mathematics Problems into Games: Reinforcement Learning and Gr\"obner bases together solve Integer Feasibility Problems [4.746723775952672]
  We consider the integer feasibility problem, a challenge of deciding whether a system of linear equations and inequalities has a solution with integer values. Our paper describes a novel algebraic reinforcement learning framework that allows an agent to play a game equivalent to the integer feasibility problem. As a proof of concept we demonstrate in experiments that our agent can play well the simplest version of our game for 2-way tables.
  arXiv  Detail & Related papers  (2022-08-25T16:24:34Z)
• 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)
• Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions [145.54544979467872]
  We propose and analyze new fictitious play policy optimization algorithms for zero-sum Markov games with structured but unknown transitions. We prove tight $widetildemathcalO(sqrtK)$ regret bounds after $K$ episodes in a two-agent competitive game scenario. Our algorithms feature a combination of Upper Confidence Bound (UCB)-type optimism and fictitious play under the scope of simultaneous policy optimization.
  arXiv  Detail & Related papers  (2022-07-25T18:29:16Z)
• 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)
• No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
  Learning from repeated play in a fixed zero-sum game is a classic problem in game theory and online learning. We develop a single parameter-free algorithm that simultaneously enjoys favorable guarantees under three performance measures. Our algorithm is based on a two-layer structure with a meta-algorithm learning over a group of black-box base-learners satisfying a certain property.
  arXiv  Detail & Related papers  (2022-01-30T06:10:04Z)
• Towards convergence to Nash equilibria in two-team zero-sum games [17.4461045395989]
  Two-team zero-sum games are defined as multi-player games where players are split into two competing sets of agents. We focus on the solution concept of Nash equilibria (NE) We show that computing NE for this class of games is $textithard$ for the complexity class $mathrm$.
  arXiv  Detail & Related papers  (2021-11-07T21:15:35Z)
• Synchronous linear constraint system games [0.0]
  We show that the game algebra is a suitable quotient of the group algebra of the solution group. We also demonstrate that linear constraint system games are equivalent to graph isomorphism games on a pair of graphs parameterized by the linear system.
  arXiv  Detail & Related papers  (2020-07-06T14:31:59Z)

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.