Playing Bayesian games better with separable quantum states than with any classical correlation

Technical Summary: Playing Bayesian Games Better with Separable Quantum States than with Any Classical Correlation

Problem Statement
Bayesian games (games of incomplete information) serve as a framework for analyzing how correlations between independent agents influence game equilibria. It is well-established that shared quantum states can yield equilibria superior to those achievable with classical correlations. However, previous demonstrations of this "quantum advantage" in games relied exclusively on entangled states. In the context of non-local games (Bell inequalities), it is known that separable quantum states provide no advantage over classical correlations. This paper addresses the question of whether separable quantum states—specifically classical-quantum (cq) states that contain no entanglement—can generate new, beneficial equilibria in competitive Bayesian games where players have conflicting interests, distinct from the cooperative setting of Bell inequalities.

Methodology
The authors propose a general construction to convert any non-local game (or Bell inequality) exhibiting a quantum advantage into a competitive Bayesian game. The methodology involves:

1. Game Transformation: Starting with a two-player non-local game $G$ with inputs $x, y$ and a common payoff function $V$, the authors define a modified Bayesian game $\tilde{G}_\Lambda$.

   • Types and Actions: Alice (Player 1) has a trivial type and outputs a pair $(x, a)$, effectively generating the input $x$ and the action $a$ for the original game. Bob (Player 2) receives the original input $y$ and must output a pair $(b, \hat{x})$, where $b$ is the action for the original game and $\hat{x}$ is a guess of Alice's input $x$.
   • Payoff Structure: The payoff functions are modified to include the original game payoff $V$ and a zero-sum penalty/reward term based on a matrix $W$.
     • $u_A = V - 2\Lambda W_{x, \hat{x}}$
     • $u_B = V + \Lambda W_{x, \hat{x}}$
   • The matrix $W$ is designed such that if Alice generates $x$ according to the distribution $p$ and Bob guesses $\hat{x}$ according to $p$, the expected value of the zero-sum term is zero. If Bob deviates from $p$ or Alice deviates from $p$, the zero-sum term penalizes the deviation, creating a strong incentive for both to adhere to the distribution $p$ independently.

2. Quantum Advice: The authors construct a specific separable quantum state $\omega$ to serve as advice.

   • The state is a classical-quantum (cq) state where Alice's part is classical (sampling $x$ and $a$), and Bob's part is a post-measurement state derived from an entangled state $\rho$ used in the original non-local game, combined with a classical guess $\hat{x}$.
   • Crucially, $\omega$ is fully separable and can be prepared using only classical correlation and local quantum state preparations, requiring no entanglement distribution between the players.

3. Equilibrium Analysis: The paper analyzes the Quantum Correlated Equilibrium (QuCE) and Classically Correlated Equilibrium (Corr) for the modified game.

   • It is shown that the separable state $\omega$ induces a behavior that constitutes a quantum correlated equilibrium.
   • The authors prove that for sufficiently large $\Lambda$, the social welfare of any classically correlated equilibrium is bounded by the classical limit $\beta(G)$ of the original non-local game (plus an arbitrarily small $\epsilon$).
   • In contrast, the quantum separable strategy achieves a social welfare equal to the quantum bound $\tau(G)$ (or 1 for pseudo-telepathy games).

4. Numerical Verification: The theoretical construction is applied to three specific games: the Magic Square (Peres-Mermin) game, the GHZ game, and the CHSH game. The authors use linear programming to optimize the social welfare over the set of classically correlated equilibria for varying $\Lambda$, comparing the results against the quantum separable strategy.

Key Contributions and Results

• Separable Quantum Advantage: The primary result is the explicit construction of Bayesian games where separable quantum states yield equilibria with higher social welfare than any classically correlated equilibrium. This demonstrates that non-classical correlations beyond entanglement (specifically, the structure of separable cq-states) are a resource in competitive settings.
• Hierarchy of Equilibria: The work clarifies the hierarchy of equilibrium notions in Bayesian games. It establishes that the set of behaviors achievable by classically correlated equilibria, $\text{Corr}(\tilde{G}_\Lambda)$, is a strict subset of the intersection of belief-invariant communication equilibria and local behaviors ($\text{BI} \cap \text{LO}$). The separable quantum advice produces a behavior in $\text{BI} \cap \text{LO}$ that is not in $\text{Corr}$.
• Local Communication Equilibria: The paper identifies a new class of equilibria: local communication equilibria that are not classically correlated equilibria. The behavior generated by the separable state is local (reproducible by shared randomness if the mediator is trusted) but cannot be represented as a correlated equilibrium because the underlying joint distribution of local strategies would reveal information that destroys the equilibrium condition.
• Numerical Results:
  • Magic Square & GHZ: For these pseudo-telepathy games, the quantum separable strategy achieves a social welfare of 1, while the maximum social welfare for classically correlated equilibria drops to the classical bound ($8/9$ and $7/8$ respectively) as $\Lambda$ increases.
  • CHSH: The numerical analysis reveals a critical threshold $\Lambda \geq 1/8$. Below this, correlated equilibria can achieve higher welfare; above it, the social welfare of classically correlated equilibria is capped at the classical bound $\beta(\text{CHSH}) = 3/4$, while the quantum separable strategy maintains the quantum bound $\approx 0.85$.

Significance and Claims
The authors claim that this work fundamentally departs from previous examples of quantum game advantages, which were tied to entanglement and cooperative Bell-type games. The significance lies in:

1. Resource Accessibility: Since separable states are easier to manufacture and distribute than entangled states, this result brings the potential realization of quantum advantage in games significantly closer to practical feasibility.
2. Theoretical Distinction: It illuminates the subtle differences between "legitimate notions of equilibrium" in Bayesian games, specifically separating local communication equilibria from classically correlated equilibria.
3. Beyond Entanglement: It proves that entanglement is not a necessary condition for quantum advantage in competitive games, suggesting that other quantum features (such as steering or discord, though the paper notes these are necessary but perhaps not sufficient conditions) may be the underlying resource.

The paper concludes by noting that while the construction relies on modifying non-local games, the resulting game structures are distinct enough to allow separable states to function as effective quantum advice. It poses open questions regarding whether every Bell violation can be converted into such a competitive game and whether "real-world" games (not artificially constructed) can exhibit this advantage.