اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدPerfect strategies for non-signalling games
119
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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 solu
tions 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 follow
s 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 prep
aration 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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
