  A correlated equilibrium is a fundamental solution concept in game theory
that enjoys many desirable properties. However, it requires a trusted mediator,
which is a major drawback in many practical applications. A computational
solution to this problem was proposed by Dodis, Halevi and Rabin. They extended
the original game by adding an initial communication stage and showed that any
correlated strategy for 2-player games can be achieved, provided that the
players are computationally bounded.
  In this paper, we show that if the players can communicate via a quantum
channel before the game, then any correlated equilibrium for 2-player games can
be achieved, without a trusted mediator and unconditionally. This provides
another example of a major advantage of quantum information processing. More
precisely, we prove that for any correlated equilibrium p of a strategic game
G, there exists an extended game (with a quantum communication initial stage) Q
with an efficiently computable approximate Nash equilibrium q, such that the
expected payoff for both players in q is at least as high as in p. The main
cryptographic tool used in the construction is the quantum weak coin flipping
protocol of Mochon.
