Synchronous linear constraint system games

• URL: http://arxiv.org/abs/2007.02782v1
• Date: Mon, 6 Jul 2020 14:31:59 GMT
• Title: Synchronous linear constraint system games
• Authors: Adina Goldberg
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Synchronous linear constraint system games are nonlocal games that verify whether or not two players share a solution to a given system of equations. Two algebraic objects associated to these games encode information about the existence of perfect strategies. They are called the game algebra and the solution group. Here we show that these objects are essentially the same, i.e., 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.

Related papers

• 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)
• Maximizing Utilitarian and Egalitarian Welfare of Fractional Hedonic Games on Tree-like Graphs [2.348041867134616]
  This paper presents (pseudo)polynomial-time algorithms to compute welfare-maximizing partitions in fractional hedonic games on tree-like graphs. A hardness result is provided, demonstrating that the pseudopolynomial-time solvability is the best possible under the assumption P$neq$NP.
  arXiv  Detail & Related papers  (2023-10-08T12:18:08Z)
• CoLA: Exploiting Compositional Structure for Automatic and Efficient Numerical Linear Algebra [62.37017125812101]
  We propose a simple but general framework for large-scale linear algebra problems in machine learning, named CoLA. By combining a linear operator abstraction with compositional dispatch rules, CoLA automatically constructs memory and runtime efficient numerical algorithms. We showcase its efficacy across a broad range of applications, including partial differential equations, Gaussian processes, equivariant model construction, and unsupervised learning.
  arXiv  Detail & Related papers  (2023-09-06T14:59:38Z)
• Simplicial techniques for operator solutions of linear constraint systems [0.0]
  We use the theory of simplicial sets to develop a framework for studying operator solutions of linear systems. Within our framework, we introduce a new class of linear systems that come from simplicial sets. We provide significant evidence for a conjecture stating that for odd $d$ every linear system admitting a solution in a group admits a solution in $ZZ_d$.
  arXiv  Detail & Related papers  (2023-05-13T17:34:29Z)
• 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)
• On the solvability of weakly linear systems of fuzzy relation equations [0.0]
  Systems of fuzzy relation equations and inequalities in which an unknown fuzzy relation is on the one side of the equation or inequality are linear systems. This paper describes the set of fuzzy relations that solve weakly linear systems to a certain degree and provides ways to compute them.
  arXiv  Detail & Related papers  (2022-05-25T16:59:48Z)
• Arkhipov's theorem, graph minors, and linear system nonlocal games [0.0]
  We study the solution groups of graph incidence games in which the underlying linear system is the incidence system of a two-coloured graph. Arkhipov's theorem states that the graph incidence game of a connected graph has a perfect quantum strategy if and only if it either has a perfect classical strategy, or the graph is nonplanar. We extend Arkhipov's theorem by showing that, for graph incidence games of connected two-coloured graphs, every quotient closed property of the solution group has a forbidden minor characterization.
  arXiv  Detail & Related papers  (2022-05-10T03:21:38Z)
• 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)
• Noncommutative Nullstellens\"atze and Perfect Games [0.0]
  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.
  arXiv  Detail & Related papers  (2021-11-29T20:05:33Z)
• Hamiltonian systems, Toda lattices, Solitons, Lax Pairs on weighted Z-graded graphs [62.997667081978825]
  We identify conditions which allow one to lift one dimensional solutions to solutions on graphs. We show that even for a simple example of a topologically interesting graph the corresponding non-trivial Lax pairs and associated unitary transformations do not lift to a Lax pair on the Z-graded graph.
  arXiv  Detail & Related papers  (2020-08-11T17:58:13Z)
• Competitive Mirror Descent [67.31015611281225]
  Constrained competitive optimization involves multiple agents trying to minimize conflicting objectives, subject to constraints. We propose competitive mirror descent (CMD): a general method for solving such problems based on first order information. As a special case we obtain a novel competitive multiplicative weights algorithm for problems on the positive cone.
  arXiv  Detail & Related papers  (2020-06-17T22:11:35Z)

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.