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.
Since our goal is to study a mediator-free setting, it is necessary to restrict our model so that the initial shared state be pure (See Appendix ). This restriction is very significant and differs from work such as Zhang's @cite_20 which, while studying both pure and mixed initial states, limited its mention of pure states to those with a certain restricted form. Roughly speaking, the main difference is that we allow for pure states with many ancillary qubits, and these ancillary qubits can indeed affect the players' ability to gain utility by deviating. Furthermore, unlike La Mura's model @cite_11 , in our definition of equilibrium we do not restrict the local operations that a player might potentially perform to his own qubits.
@cite_20 @cite_11
1517645949 2136629712 2179146913 2024712778
We study the outcome of natural learning algorithms in atomic congestion games. Atomic congestion games have a wide variety of equilibria often with vastly differing social costs. We show that in almost all such games, the well- known multiplicative-weights learning algorithm results in convergence to pure equilibria. Our results show that nat- ural learning behavior can avoid bad outcomes predicted by the price of anarchy in atomic congestion games such as the load-balancing game introduced by Koutsoupias and Pa- padimitriou, which has super-constant price of anarchy and has correlated equilibria that are exponentially worse than any mixed Nash equilibrium. Our results identify a set of mixed Nash equilibria that we call weakly stable equilibria. Our notion of weakly stable is defined game-theoretically, but we show that this property holds whenever a stability criterion from the theory of dy- namical systems is satisfied. This allows us to show that in every congestion game, the distribution of play converges to the set of weakly stable equilibria. Pure Nash equilibria are weakly stable, and we show using techniques from algebraic geometry that the converse is true with probability 1 when congestion costs are selected at random independently on each edge (from any monotonically parametrized distribu- tion). We further extend our results to show that players can use algorithms with different (sufficiently small) learn- ing rates, i.e. they can trade off convergence speed and long term average regret differently. 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 consider strategic games in which each player seeks a mixed strategy to minimize her cost evaluated by a concave valuationV (mapping probability distributions to reals); such valuations are used to model risk. In contrast to games with expectation-optimizer players where mixed equilibria always exist (Nash 1950; Nash Ann. Math. 54, 286---295, 1951), a mixed equilibrium for such games, called a V-equilibrium, may fail to exist, even though pure equilibria (if any) transfer over. What is the exact impact of such valuations on the existence, structure and complexity of mixed equilibria? We address this fundamental question in the context of expectation plus variance, a particular concave valuation denoted as RA, which stands for risk-averse; so, variance enters as a measure of risk and it is used as an additive adjustment to expectation. We obtain the following results about RA-equilibria: A collection of general structural properties of RA-equilibria connecting to (i)E-equilibria and Var-equilibria, which correspond to the expectation and variance valuations E and Var, respectively, and to (ii) other weaker or incomparable properties such as Weak Equilibrium and Strong Equilibrium. Some of these structural properties imply quantitative constraints on the existence of mixed RA-equilibria.A second collection of (i) existence, (ii) equivalence and separation (with respect to E-equilibria), and (iii) characterization results for RA-equilibria in the new class of player-specific scheduling games. We provide suitable examples with a mixed RA-equilibrium that is not an E-equilibrium and vice versa.A purification technique to transform a player-specific scheduling game on two identical links into a player-specific scheduling game on two links so that all non-pureRA-equilibria are eliminated while no new pure equilibria are created; so, a particular player-specific scheduling game on two identical links with no pure equilibrium yields a player-specific scheduling game with noRA-equilibrium (whether mixed or pure). As a by-product, the first ?????-completeness result for the computation of RA-equilibria follows. Recently, it has been claimed that full-information multiple equilibria in games with strategic complementarities are not robust, because generalizing to allow slightly heterogeneous information implies uniqueness. This paper argues that this "global games" uniqueness result is itself not robust. If we generalize by allowing most agents to observe a few previous actions before choosing, instead of forcing players to move exactly simultaneously, then multiplicity of outcomes is restored. Only a small sample of observations is needed to make our herding equilibrium behave like a full-information sunspot equilibrium instead of a global games equilibrium.