Synchronous Values of Games

• URL: http://arxiv.org/abs/2109.14741v2
• Date: Tue, 22 Aug 2023 18:12:12 GMT
• Title: Synchronous Values of Games
• Authors: J. William Helton, Hamoon Mousavi, Seyed Sajjad Nezhadi, Vern I. Paulsen, and Travis B. Russell
• Abstract summary: It is known that a synchronous game has a perfect strategy if and only if it has a perfect synchronous strategy. We give examples of synchronous games, in particular graph colouring games, with synchronous value that is strictly smaller than their ordinary value.
• Score: 0.23301643766310368
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study synchronous values of games, especially synchronous games. It is known that a synchronous game has a perfect strategy if and only if it has a perfect synchronous strategy. However, we give examples of synchronous games, in particular graph colouring games, with synchronous value that is strictly smaller than their ordinary value. Thus, the optimal strategy for a synchronous game need not be synchronous. We derive a formula for the synchronous value of an XOR game as an optimization problem over a spectrahedron involving a matrix related to the cost matrix. We give an example of a game such that the synchronous value of repeated products of the game is strictly increasing. We show that the synchronous quantum bias of the XOR of two XOR games is not multiplicative. Finally, we derive geometric and algebraic conditions that a set of projections that yields the synchronous value of a game must satisfy.

Related papers

• Robust Self-testing for Synchronous Correlations and Games [0.0]
  We show that a synchronous correlation is a robust self-test if and only if there is a unique state on an appropriate $C*$-algebra. We establish that all synchronous correlations and games that serve as commuting operator self-tests for finite-dimensional strategies are also robust self-tests.
  arXiv  Detail & Related papers  (2025-03-30T16:19:14Z)
• Quantum Games and Synchronicity [0.0]
  We extend nonlocal quantum games to allow quantum questions and answers. Equations are presented using a diagrammatic calculus for tensor categories. We extend the standard definitions, including strategies, correlations, and synchronicity, and we use these definitions to extend results about synchronicity.
  arXiv  Detail & Related papers  (2024-08-27T23:27:59Z)
• Hybrid Approach to Parallel Stochastic Gradient Descent [0.0]
  We propose a third approach to data parallelism which is a hybrid between synchronous and asynchronous approaches. In a given time period our hybrid approach outperforms both asynchronous and synchronous approaches.
  arXiv  Detail & Related papers  (2024-06-27T06:28:30Z)
• AsyncDiff: Parallelizing Diffusion Models by Asynchronous Denoising [49.785626309848276]
  AsyncDiff is a universal and plug-and-play acceleration scheme that enables model parallelism across multiple devices. For the Stable Diffusion v2.1, AsyncDiff achieves a 2.7x speedup with negligible degradation and a 4.0x speedup with only a slight reduction of 0.38 in CLIP Score. Our experiments also demonstrate that AsyncDiff can be readily applied to video diffusion models with encouraging performances.
  arXiv  Detail & Related papers  (2024-06-11T03:09:37Z)
• Synchformer: Efficient Synchronization from Sparse Cues [100.89656994681934]
  Our contributions include a novel audio-visual synchronization model, and training that decouples extraction from synchronization modelling. This approach achieves state-of-the-art performance in both dense and sparse settings. We also extend synchronization model training to AudioSet a million-scale 'in-the-wild' dataset, investigate evidence attribution techniques for interpretability, and explore a new capability for synchronization models: audio-visual synchronizability.
  arXiv  Detail & Related papers  (2024-01-29T18:59:55Z)
• Transitive Nonlocal Games [0.0]
  We study a class of nonlocal games, called transitive games, for which the set of perfect strategies forms a semigroup. We prove that the existence of a C*-strategy, the existence of a quantum commuting strategy, and the existence of a classical strategy are all equivalent.
  arXiv  Detail & Related papers  (2023-12-19T10:49:41Z)
• Asynchronous Distributed Optimization with Delay-free Parameters [9.062164411594175]
  This paper develops asynchronous versions of two distributed algorithms, Prox-DGD and DGD-ATC, for solving consensus optimization problems over undirected networks. In contrast to alternatives, our algorithms can converge to the fixed point set of their synchronous counterparts using step-sizes that are independent of the delays.
  arXiv  Detail & Related papers  (2023-12-11T16:33:38Z)
• 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)
• Sparse in Space and Time: Audio-visual Synchronisation with Trainable Selectors [103.21152156339484]
  The objective of this paper is audio-visual synchronisation of general videos 'in the wild' We make four contributions: (i) in order to handle longer temporal sequences required for sparse synchronisation signals, we design a multi-modal transformer model that employs'selectors' We identify artefacts that can arise from the compression codecs used for audio and video and can be used by audio-visual models in training to artificially solve the synchronisation task.
  arXiv  Detail & Related papers  (2022-10-13T14:25:37Z)
• Connes implies Tsirelson: a simple proof [91.3755431537592]
  We show that the Connes embedding problem implies the synchronous Tsirelson conjecture. We also give a different construction of Connes' algebra $mathcalRomega$ appearing in the Connes embedding problem.
  arXiv  Detail & Related papers  (2022-09-16T13:59:42Z)
• Learning Iterative Robust Transformation Synchronization [71.73273007900717]
  We propose to use graph neural networks (GNNs) to learn transformation synchronization. In this work, we avoid handcrafting robust loss functions, and propose to use graph neural networks (GNNs) to learn transformation synchronization.
  arXiv  Detail & Related papers  (2021-11-01T07:03:14Z)
• EigenGame Unloaded: When playing games is better than optimizing [19.522120239876486]
  EigenGame views eigendecomposition as a competitive game. We build on the recently proposed EigenGame that views eigendecomposition as a competitive game.
  arXiv  Detail & Related papers  (2021-02-08T12:04:59Z)
• A Parallel Repetition Theorem for the GHZ Game [2.561899487681323]
  We prove that the value of the GHZ game repeated in parallel $t$ times is at most $t-Omega(1)$. The GHZ game, first introduced by Greenberger, Horne and Zeilinger, is a central game in the study of quantum entanglement.
  arXiv  Detail & Related papers  (2020-08-12T01:32:34Z)

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.