We study the scenario where the players of a classical complete information game initially share an entangled pure quantum state. Each player may perform arbitrary local operations on his own qubits, but no direct communication is allowed. In this framework, we define the concept of quantum correlated equilibrium (QCE) for both normal and extensive form games of complete information. We show that in a normal form game, any outcome distribution implementable by a QCE can also be implemented by a classical correlated equilibrium (CE). We prove that the converse is surprisingly false: we give an example of an outcome distribution of a normal form game which is implementably by a CE, yet we prove that in any attempted quantum protocol beginning with a partition of a pure quantum state, at least one of the players will have incentive to deviate. We extend our analysis to extensive form games, and find that the relation between classical and quantum correlated equilibria becomes less clear. We compare the outcome distributions implementable in our quantum model to those implementable by a classical extensive form correlated equilibrium (EFCE). For example, we show that there exists an extensive form complete information game and a distribution of outcomes which can be implemented by a QCE but not by any EFCE, in contrast to the result for normal form games. We also consider the concept of an immediate-revelation extensive form correlated equilibrium (IR-EFCE) and compare the power of IR-EFCE to EFCE and to QCE.
While work by @cite_15 , @cite_7 and La Mura @cite_11 have studied how quantum entanglement can aid in games of incomplete information (such as Bayesian games), we restrict our attention to games of complete information, and find that even in this framework the questions are nontrivial. Quantum solutions of classical coordination games have been studied previously, such as in @cite_7 and @cite_19 . In this paper, we look at games which have both cooperative and competitive components. Instead of analyzing the quantization'' of games (see Meyer @cite_13 ), our underlying games remain purely classical. Entanglement is used only as a device to aid in a player's decision of which strategy to play in the classical game. By keeping the underlying game classical, our model generalizes naturally from normal form to extensive form games.
@cite_7 @cite_19 @cite_15 @cite_13 @cite_11
2136629712 2127592065 2116397277 2232305496
We propose a simple yet rich model to extend strategic games to the quantum setting, in which we define quantum Nash and correlated equilibria and study the relations between classical and quantum equilibria. Unlike all previous work that focused on qualitative questions on specific games of very small sizes, we quantitatively address the following fundamental question for general games of growing sizes: How much "advantage" can playing quantum strategies provide, if any? Two measures of the advantage are studied. 1. Since game mainly is about each player trying to maximize individual payoff, a natural measure is the increase of payoff by playing quantum strategies. We consider natural mappings between classical and quantum states, and study how well those mappings preserve equilibrium properties. Among other results, we exhibit a correlated equilibrium p whose quantum superposition counterpart [EQUATION] is far from being a quantum correlated equilibrium; actually a player can increase her payoff from almost 0 to almost 1 in a [0, 1]-normalized game. We achieve this by a tensor product construction on carefully designed base cases. The result can also be interpreted as in Meyer's comparison [47]: In a state no classical player can gain, one player using quantum computers has an huge advantage than continuing to play classically. 2. Another measure is the hardness of generating correlated equilibria, for which we propose to study correlation complexity, a new complexity measure for correlation generation. We show that there are n-bit correlated equilibria which can be generated by only one EPR pair followed by local operation (without communication), but need at least log2(n) classical shared random bits plus communication. The randomized lower bound can be improved to n, the best possible, assuming (even a much weaker version of) a recent conjecture in linear algebra. We believe that the correlation complexity, as a complexity-theoretical counterpart of the celebrated Bell's inequality, has independent interest in both physics and computational complexity theory and deserves more explorations. We present a quantum solution to coordination problems that can be implemented with existing technologies. Using the properties of entangled states, this quantum mechanism allows participants to rapidly find suitable correlated choices as an alternative to conventional approaches relying on explicit communication, prior commitment or trusted third parties. Unlike prior proposals for quantum games our approach retains the same choices as in the classical game and instead utilizes quantum entanglement as an extra resource to aid the participants in their choices. PACS: 03.67.-a; 02.50.Le; 89.65.Gh This paper investigates various aspects of the nonlocal effects that can arise when entangled quantum information is shared between two parties. A natural framework for studying nonlocality is that of cooperative games with incomplete information, where two cooperating players may share entanglement. Here, nonlocality can be quantified in terms of the values of such games. We review some examples of non-locality and show that it can profoundly affect the soundness of two-prover interactive proof systems. We then establish limits on nonlocal behavior by upper-bounding the values of several of these games. These upper bounds can be regarded as generalizations of the so-called Tsirelson inequality. We also investigate the amount of entanglement required by optimal and nearly optimal quantum strategies. We introduce quantum XOR games, a model of two-player, one-round games that extends the model of XOR games by allowing the referee’s questions to the players to be quantum states. We give examples showing that quantum XOR games exhibit a wide range of behaviors that are known not to exist for standard XOR games, such as cases in which the use of entanglement leads to an arbitrarily large advantage over the use of no entanglement. By invoking two deep extensions of Grothendieck’s inequality, we present an efficient algorithm that gives a constant-factor approximation to the best performance that players can obtain in a given game, both in the case that they have no shared entanglement and that they share unlimited entanglement. As a byproduct of the algorithm, we prove some additional interesting properties of quantum XOR games, such as the fact that sharing a maximally entangled state of arbitrary dimension gives only a small advantage over having no entanglement at all.