In a new paper with Mika Goos, we prove an lower bound on the randomized communication complexity of computing an approximate Nash equilibrium in a two-player game. Then Shalev Ben-David observed that our new proof also gives the first non-trivial lower bound on the quantum communication complexity of approximate Nash equilibrium. So quantum computers might not help us cooperate better with each other after all. Or maybe they will? You’ll have to read until the end of this short post. But first let me point out a cool technical challenge:
1. For quantum communication, we lose a quadratic factor (corresponding to Grover’s search), i.e. our lower bound is only . But I don’t know how to use Grover’s search to improve over the naive upper bound. So, is the quantum communication of approximate Nash equilibrium closer to linear or quadratic?
Why is this interesting?
Before we discuss why quantum communication of approximate Nash is interesting, it is helpful to first recall some game theory, and in particular remind ourselves why the classical (randomized) communication complexity of approximate Nash is important. Briefly, a two-player game is described by two matrices ; if Alice and Bob play actions , their payoffs are and , respectively. Typically, they want to use randomized strategies (called mixed strategies). We say that Alice and Bob are at an (approximate) Nash equilibrium, each player’s strategy is (approximately) best-response to other player’s strategy. I.e. once players are at an equilibrium, they may never want to leave it. The big question is how do they get there in the first place?
A common approach to this question is to look for plausible dynamics, or procedures by which players update their strategies, and which guarantee convergence to Nash equilibrium. Defining “plausible” is a fascinating philosophical discussion far beyond the scope of this post, but two useful desiderata are: (i) uncoupled dynamics, namely each player knows only her own payoff matrix and the history of the game — this rules out the trivial dynamics where players start at a Nash equilibrium; and (ii) efficient dynamics, namely the dynamics must converge faster than it would take Alice to communicate her entire payoff matrix to Bob. Those are certainly not sufficient conditions for plausibility of dynamics, but our communication lower bound rules out any efficient uncoupled dynamics.
Back to quantum communication
So, what is a natural model of quantum uncoupled dynamics? I was confused about this for a few weeks: people have studied quantum games where players’ actions are described by qubits, and the payoffs are determined based on their measurements. But this is a generalization of classical games, where we already know that the problem is hard. So I asked Shalev again, and he had another nice observation: the players can still send classical bits (aka play classical actions) — they merely need to share entangled qubits and measure them before deciding what strategies to play. (But admittedly this might not work if the police decide to search the Dilemma Prisoners for entangled qubits before their interrogation…)
One last motivational comment: my very superficial understanding of the real-world feasibility of all this stuff is that while there is a lot of buzz around the race toward the first quantum computer that may or may not be able to execute a “hello world!” program , quantum communication already allows cross-continental video conferences…
Quantum + game theory
While writing this post, I realized that there is an entire literature on various ways to entangle quantum with game theory. My favorite is this paper by Alan Deckelbaum about quantum correlated equilibrium. Correlated equilibrium is a generalization of Nash equilibrium where a trusted coordinating device suggests to Alice and Bob pairs of actions drawn from a joint (correlated) distribution. The requirement is that Alice, after seeing the action the coordinating device suggested for her (but not the one for Bob), has no incentive to deviate from the suggestion. It is known that natural no-internal-regret dynamics converge to the set of correlated equilibria. But without the trusted coordinating device the players are still incentivized to keep modifying their strategies. (By the way, the classical communication complexity of approximate correlated equilibrium in two-player games is still open!)
Anyway, Deckelbaum points out that any correlated distribution can be simulated using quantum entanglement. Can quantum entanglement replace the trusted coordinating device? Sometimes, but there is a catch: sampling from the correlated distribution using quantum measurements requires players to cooperate with the sampling protocol. Specifically, Deckelbaum shows that some games have correlated equilibria that cannot be truthfully sampled with quantum entanglement, i.e. one of the players has an incentive to deviate from any sampling protocol. He defines quantum correlated equilibria as those that can be sampled truthfully, and asks what is the computational complexity of finding one. (Note that this is an easier question than the PPAD-complete Nash equilibrium, and harder than the polynomial-time correlated equilibrium.) So here is yet another nice question:
2. What is the (randomized/quantum) communication complexity of finding an approximate quantum correlated equilibrium?