It's just that they have access to an operation which classically doesn't exist, because their probabilities are complex numbers rather than real numbers. (Just as importantly, there are known limits to how great their correlation can be; the nice thing about Betrayal is that you can quickly prove that six classical random variables don't work no matter how they're jointly distributed.)
So what is this strange operation? There exist two nice "superposition over all states" quantum states for the three bits held by the three players:
+++ = 000 + 001 + 010 + 011 + ... + 111
−−− = 000 − 001 − 010 + 011 + ... − 111
Separately those states are not entangled: that is, +++ is made from the separable (0 + 1)(0 + 1)(0 + 1) while −−− is made from the separable (0 − 1)(0 − 1)(0 − 1). In both "pure" states any bit pattern from 000 to 111 has equal probability. Quantum mechanics now lets these observers have the superposition state:
(+++) + (−−−) = 000 + 011 + 101 + 110
This is an entangled state. In this state you cannot be sure which of these four will occur, but they will each occur with even probability and the sum will be even. So that's the "control" experiment covered. But we could solve the "control" experiment with the 000 state too. What about the "traitor" experiment?
Here's where you need the complex numbers. Each of the "make the sum odd" people maps (+),(−) → (+),i(−). This is called a phase rotation, and you might know i² = -1 in the complex plane. These separate acts shift the global state to:
(+++) + (−−−) → (+++) + i²(−−−) = (+++) − (−−−)
If you work it out you will find:
(+++) − (−−−) = 001 + 010 + 100 + 111
So even though
locally nobody can tell what's happened (every single person still has a 50/50 chance of seeing 0 or 1 by themselves), the
global sum changes due to this phase rotation. That is what entanglement can get you, large-scale correlations.
As for proving that classical probabilities cannot do this, take six random variables no matter their joint distribution, call them Ao, Ae, Bo, Be, and Co, Ce -- what Alice, Bob, and Carol do when they're told to make the sum odd or even, respectively. The problem asks to make Ao + Bo + Ce ≡ Ao + Be + Co ≡ Ae + Bo + Co ≡ 1 (mod 2) while Ae + Be + Ce ≡ 0 (mod 2). Adding those four equations together gives 2 * (Ao + Bo + Co + Ae + Be + Ce) ≡ 3 (mod 2), but 3 isn't even. So it's not possible to satisfy all four equations all of the time with classical probabilities.