Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPerfect strategies for non-signalling games
119
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We unify and consolidate various results about non-signall-ing games, a subclass of non-local two-player one-round games, by introducing and studying several new families of games and establishing general theorems about them, which extend a number of known facts in a variety of special cases. Among these families are {it reflexive games,} which are characterised as the hardest non-signalling games that can be won using a given set of strategies. We introduce {it imitation games,} in which the players display linked behaviour, and which contains as subclasses the classes of variable assignment games, binary constraint system games, synchronous games, many games based on graphs, and {it unique} games. We associate a C*-algebra $C^*(mathcal{G})$ to any imitation game $mathcal{G}$, and show that the existence of perfect quantum commuting (resp. quantum, local) strategies of $mathcal{G}$ can be characterised in terms of properties of this C*-algebra, extending known results about synchronous games. We single out a subclass of imitation games, which we call {it mirror games,} and provide a characterisation of their quantum commuting strategies that has an algebraic flavour, showing in addition that their approximately quantum perfect strategies arise from amenable traces on the encoding C*-algebra. We describe the main classes of non-signalling correlations in terms of states on operator system tensor products.
rate research
Read More
Linear system games are a generalization of Mermins magic square game introduced by Cleve and Mittal. They show that perfect strategies for linear system games in the tensor-product model of entanglement correspond to finite-dimensional operator solutions of a certain set of non-commutative equations. We investigate linear system games in the commuting-operator model of entanglement, where Alice and Bobs measurement operators act on a joint Hilbert space, and Alices operators must commute with Bobs operators. We show that perfect strategies in this model correspond to possibly-infinite-dimensional operator solutions of the non-commutative equations. The proof is based around a finitely-presented group associated to the linear system which arises from the non-commutative equations.
We prove that optimal strategies exist in every perfect-information stochastic game with finitely many states and actions and a tail winning condition.
This article extends the idea of solving parity games by strategy iteration to non-deterministic strategies: In a non-deterministic strategy a player restricts himself to some non-empty subset of possible actions at a given node, instead of limiting himself to exactly one action. We show that a strategy-improvement algorithm by by Bjoerklund, Sandberg, and Vorobyov can easily be adapted to the more general setting of non-deterministic strategies. Further, we show that applying the heuristic of all profitable switches leads to choosing a locally optimal successor strategy in the setting of non-deterministic strategies, thereby obtaining an easy proof of an algorithm by Schewe. In contrast to the algorithm by Bjoerklund et al., we present our algorithm directly for parity games which allows us to compare it to the algorithm by Jurdzinski and Voege: We show that the valuations used in both algorithm coincide on parity game arenas in which one player can surrender. Thus, our algorithm can also be seen as a generalization of the one by Jurdzinski and Voege to non-deterministic strategies. Finally, using non-deterministic strategies allows us to show that the number of improvement steps is bound from above by O(1.724^n). For strategy-improvement algorithms, this bound was previously only known to be attainable by using randomization.
We examine the problem of the existence of optimal deterministic stationary strategiesintwo-players antagonistic (zero-sum) perfect information stochastic games with finitely many states and actions.We show that the existenceof such strategies follows from the existence of optimal deterministic stationarystrategies for some derived one-player games.Thus we reducethe problem from two-player to one-player games (Markov decisionproblems), where usually it is much easier to tackle.The reduction is very general, it holds not only for all possible payoff mappings but alsoin more a general situations whereplayers preferences are not expressed by payoffs.
Pure state of a physical system can be prepared in an infinite number of ways. Here, we prove that given a pure state of a quantum system it is impossible to distinguish two preparation procedures. Further, we show that if we can distinguish two preparation procedures for the same pure state then that can lead to signalling. This impossibility result is different than the no measurement without disturbance and the no-cloning. Extending this result for a pure bipartite entangled state entails that the impossibility of distinguishing two preparation procedures for a mixed state follows from the impossibility of distinguishing two preparations for a pure bipartite state.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
