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
2116397277 2127592065 2028815089 1480296433 1551419266
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 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 A quantum algorithm for an oracle problem can be understood as a quantum strategy for a player in a two-player zero-sum game in which the other player is constrained to play classically. I formalize this correspondence and give examples of games (and hence oracle problems) for which the quantum player can do better than would be possible classically. The most remarkable example is the Bernstein-Vazirani quantum search algorithm which I show creates no entanglement at any timestep. Correlated equilibria are sometimes more efficient than the Nash equilibria of a game without signals. We investigate whether the availability of quantum signals in the context of a classical strategic game may allow the players to achieve even better efficiency than in any correlated equilibrium with classical signals, and find the answer to be positive.