the chsh game: classical strategy
This article details the best possible strategy for the chsh game, assuming the universe is fundamentally classical in nature. This includes the so called “local theories with hidden variables”, in which there is no quantum superposition, but instead everything is pre-determined, even if some of those pre-determined variables are epistemologically unavailable to the observer, hence “hidden”.
recap of the game
There are two spies, one has a poison A 1 , the other has an antidote A 2 , which, ingested on its own, is also lethal. They are tasked with eliminating a target during an event. However, it is not certain the target will be there, there are three doppelgangers that can attend the event instead of the target – therefore there are four possibilities in total. That means two bits of information I 1 and I 2 , because 4 = 2 2. Each of the spies gathers exactly one of those bits, and because they cannot communicate with each other during the operation, each has to decide whether to use the poison, or the antidote respetively, only based on this one bit.
Summed up as a logical statement, the spies succeed if: A 1 xor A 2 holds if and only if I 1 and I 2 holds.
|A 1 ⊕ A 2 ||A 1 ||¬ A 1 |
|A 2 ||0||1|
|¬ A 2 ||1||0|
|I 1 ∧ I 2 ||I 1 ||¬ I 1 |
|I 2 ||1||0|
|¬ I 2 ||0||0|
The same, expressed pictographically:
best deterministic strategy
First, let us suppose that neither agent uses random chance in their decision-making. Instead, they agree on clear rules of the form „if I see this, I do this, if you see that, you do that“. In mathy terms, it means that A 1 is a function of I 1 and A 2 is a function of I 2 – action of each agent only depends on the information they gather themself.
To agree on a strategy, each agent must answer two yes-no questions: whether they would perform their action if their observation indicates a doppelganger, and whether they would perform the action if their observation is consistent with the target being present. This limits the total number of possible strategies to sixteen (four bits, 2 4 = 16). However, since the probability of a success of a given strategy wouldn't change if we swapped the two agents' answers, so it turns out we only need to go over 10 of them.
We will use the notation S ab c d , where a , b , c , d are either 0 or 1 to denote a strategy where
For example the strategy S 1001 would mean: if the first agent sees a left-handed person, they poison the drink, if they see a right-handed person, they don't; if the second agent sees the correct-sized suit, they don't add the antidote, if they see a wrong-sized suit, they add it. This strategy would be successful 75 % of the time:
|S 1001 ||left-handed,
poison not used
antidote not added
Let's evaluate all ten strategies then:
|S 0000 ||🙎❌||🙎✅||🙎✅||🙎✅||75%|
|S 1000 ||🪦✅||🙎✅||🪦❌||🙎✅||75%|
|S 0100 ||🙎❌||🪦❌||🙎✅||🪦❌||25%|
|S 1100 ||🪦✅||🪦❌||🪦❌||🪦❌||25%|
|S 1010 ||🙎❌||🪦❌||🪦❌||🙎✅||25%|
|S 0110 ||🪦✅||🙎✅||🙎✅||🪦❌||75%|
|S 0101 ||🪦❌||🙎❌||🙎❌||🪦✅||25%|
|S 1011 ||🙎❌||🪦❌||🙎✅||🪦❌||25%|
|S 0111 ||🪦✅||🙎✅||🪦❌||🙎✅||75%|
|S 1111 ||🙎❌||🙎✅||🙎✅||🙎✅||75%|
(Legend: 🎯 = target, ✋ = left-handed, 🤚 = right-handed, 🤵 = suit of the correct size, 🧑💼 = suit of the wrong size, 🙎 = lived, 🪦 = killed, ✅ = success, ❌ = failure, P = probability of success.)
As you can see, no strategy has a higher probability of success than 75%, one of those strategies is S 0000 – the strategy of doing nothing. Therefore, if this is the best you can do, you should probably abort the mission.
best non-deterministic strategy
Let's see if adding randomness to the decision-making process could increase your chances. For example, each agent could flip a coin, throw a dice, or decide according to whether the receptionist had red or black hair. It doesn't matter that event would be truly random – what matters is that the event wouldn't be in any way correlated to the left-handedness or suit size of the suspected target, therefore we can treat it as an independent random variable.
Let's imagine a few examples. The agents might flip a coin before the event to jointly decide between strategies S 0110 and S 1011 . Then, the total probability of either success is given by the weighted sum of the success probabilities of the two strategies: