Quantum Pseudo-Telepathy in Game Theory

In some Bayesian games with asymmetric information, players who have access to a shared physical system in an entangled quantum state, and who are able to execute strategies that are contingent upon measurements performed on the entangled physical system, are able to achieve higher expected payoffs in equilibrium than can be achieved in any mixed-strategy Nash equilibrium of the same game by players without access to the entangled quantum system.
The phenomenon came to be referred to as quantum pseudo-telepathy, with the prefix pseudo referring to the fact that quantum pseudo-telepathy does not involve the exchange of information between any parties.
By removing the need to engage in communication to achieve mutually advantageous outcomes in some circumstances, quantum pseudo-telepathy could be useful if some participants in a game were separated by many light years, meaning that communication between them would take many years.
In some Bayesian games, allowing players to exchange entangled qubits before the game begins can result in a Nash equilibrium which is Pareto optimal to any Nash equilibrium achievable in the absence of communication.
The magic square game features two players, Alice and Bob.
At the beginning of the game, Alice and Bob are separated.
After they are separated, communication between them is not possible.
The game requires that Alice fill in one row, and Bob one column, of a 3×3 table with plus and minus signs.
Before the game begins, Alice does not know which row of the table she will be required to fill in. Similarly, Bob does not know which column he will be required to fill in.
After the two players are separated, Alice is randomly assigned one row of the table and asked to fill it with plus and minus signs. Similarly, Bob is randomly assigned one column of the table and asked to fill it with plus and minus signs.
The players are subject to the following requirement: Alice must fill in her row such that there is an even number of minus signs in that row. Furthermore, Bob must fill in his column such that there is an odd number of minus signs in that column.
Depending on the actions taken by participants, one of two outcomes can occur in this game. Either both players win, or both players lose.
If Alice and Bob place the same sign in the cell shared by their row and column, they win the game. If they place opposite signs, they lose the game.
It can be proved that in the classic formulation of this game, there is no strategy (Nash equilibrium or otherwise) which allows the players to win the game with probability greater than 8/9.
The reason why the game can only be won with probability 8/9 is that a perfectly consistent table does not exist: it would be self-contradictory, with the sum of the minus signs in the table being even based on row sums, and being odd when using column sums, or vice versa.
If the game was modified to allow Alice and Bob to communicate after they discover which row/column they have been assigned, then there would exist a set of strategies allowing both players to win the game with probability 1. However, if quantum pseudo-telepathy were used, then Alice and Bob could both win the game without communicating.
Pseudo-telepathic strategies involve using quantum pseudo-telepathy in order to communicate without revealing the information that was communicated.
The game of quantum communication is played between two players, Alice and Bob.
Each player has two particles, each of which is in an entangled state.
Alice and Bob learn which column and row they must fill in order to win the game.
Each player makes one measurement on their particles per round of the game.
The game proceeds by having Alice and Bob use those measurements to derive the table entries for the game.
The player who fills in the table entries first wins the game.
Classical non-cooperative game theory is a theory of games between two or more players, in which each player has a finite number of options available to them.
In quantum non-cooperative game theory, a coordination game is a game in which multiple Nash equilibrium are possible, but the players do not always have access to each other's options.
It has been demonstrated that the game described above is the simplest two-player game of its type in which quantum pseudo-telepathy allows a win with probability one.
Other games in which quantum pseudo-telepathy occurs have been studied, including larger magic square games, graph colouring games, and multiplayer games involving more than two participants.
The win probability of a two-player nonlocal game can be improved by increasing the number of entangled qubits the players are allowed to share. However, it is impossible to calculate the maximum probability of winning a two-player game using quantum pseudo-telepathy.