  We propose a simple yet rich model to extend the notions of Nash equilibria
and correlated equilibria of strategic games to the quantum setting, in which
we then study the relations between classical and quantum equilibria. Unlike
the previous work that focus on qualitative questions on specific games of
small sizes, we address the following fundamental and quantitative question for
general games:
  How much "advantage" can playing quantum strategies provide, if any?
  Two measures of the advantage are studied, summarized as follows.
  1. A natural measure is the increase of payoff. We consider natural mappings
between classical and quantum states, and study how well those mappings
preserve the equilibrium properties. Among other results, we exhibit correlated
equilibrium $p$ whose quantum superposition counterpart $\sum_s
\sqrt{p(s)}\ket{s}$ 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.
  2. For studying the hardness of generating correlated equilibria, we propose
to examine \emph{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 $\log(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.
