Alice, Bob e Eva — Perché non si può giocare a mental poker

“Non posso credere che una dimostrazione matematica sia sbagliata”.

“Ma non lo è”.

“Allora non è vero che si riesce a giocare a poker via telefono”.

“E invece lo è. Ti riporto le parole degli autori:”.

We will present two solutions to the problem of playing Mental Poker:

1. A rigorous proof that it is theoretically impossible to deal the cards in a way which simultaneously ensures that the two hands are disjoint and that neither player has any knowledge of the other player's hand (other than that the opponent's hand is disjoint from his).

2. An elegant protocol for dealing the cards that permits one to play a fair game of Mental Poker as desired.

The blatant contradiction between our two results is not due to any tricks or faults in either result. In fact, we will leave to the reader the enjoyable task of puzzling out the differences in the underlying assumptions that account for our seemingly contradictory results.

“Enjoyable task? Questi sono matti”.

“Te l'ho detto che si sono divertiti un sacco, no?”.

“Ma com'è la faccenda, allora? Dice che i due risultati sono apparentemente contraddittori”.

“Sì, vediamo la prima parte, per adesso”.

“Ok”.

“Per semplicità, supponiamo che ci siano solo due giocatori, i soliti Alice e Bob, e un mazzo di tre carte, X, Y e Z”.

“Solo tre?”.

“Ce ne devono essere almeno tre, in modo che sia Alice che Bob non possano conoscere la carta dell'altro”.

“Va bene”.

“Allora, supponiamo che esista un sistema per giocare a poker via telefono. Esso prevederà che vengano scambiati alcuni messaggi lungo la linea telefonica”.

“Quali messaggi?”.

“Non lo sappiamo, non sappiamo ancora se esiste questo sistema, né come è fatto. Immaginiamo che esista, e proviamo a vedere che succede. Supponiamo che alla fine Alice ottenga la carta X e Bob la carta Y: per arrivare a questa situazione si sono prima parlati”.

“Mh, ok, per giocare Alice e Bob devono certamente parlarsi, è l'unica cosa che possono fare col telefono”.

“Bene. Quindi il sistema è composto da un certo numero di messaggi, M₁, M₂, …, M_n. Ora indichiamo con S_A l'insieme delle carte che Alice potrebbe aver ottenuto in seguito allo scambio di quei messaggi”.

“Ma come, non abbiamo detto che ne ottengono una per uno? Alice avrà una carta sola, no?”.

“Sì, certo, una sola. L'insieme S_A contiene però tutte le carte permesse da quell'insieme di messaggi. Magari il protocollo prevede che i due giocatori possano fare scelte casuali, e quindi uno stesso scambio di messaggi potrebbe anche dare luogo a carte diverse”.

“Mh, non mi viene in mente nessun metodo che funzioni così, però capisco che in linea teorica non possiamo dare niente per scontato”.

“Proviamo ad andare avanti: se S_A contiene solo X, allora non è vero che Bob non ha informazioni riguardanti le carte di Alice: in questo caso la sequenza di messaggi determina univocamente le carte di Alice, e quindi Bob sa”.

“Mi pare giusto”.

“Quindi S_A non può contenere soltanto X (che è la carta effettivamente presa da Alice), ma deve contenerne anche qualcun altra: ecco perché dicevo che la sequenza di messaggi deve essere compatibile con più assegnazioni di carte. Se la sequenza di messaggi fosse solo associabile alla carta X, Bob potrebbe scoprire la mano di Alice analizzando proprio tutti i messaggi”.

“Va bene. Quindi?”.

“D'altra parte, se S_A contiene tutte e tre le carte, allora Bob non può avere nessuna carta: qualunque carta egli scelga, potrebbe averla già Alice”.

“Anche questo è vero. Quindi S_A deve contenere due elementi?”.

“Proprio così. Ma anche l'insieme di carte che può ottenere Bob dovrà, per simmetria, avere due elementi. I ruoli di Alice e Bob sono perfettamente simmetrici, se S_A contiene due carte, anche S_B (l'insieme di carte che potrebbero essere assegnate a Bob) ne conterrà due”.

“Ma le carte sono in tutto tre”.

“Esattamente, quindi S_A e S_B devono avere un elemento in comune. Nel nostro esempio è Z, che potrebbe essere assegnata a Alice o a Bob”.

“E questo è un problema?”.

“Eh, questo significa che la sequenza di messaggi M₁, …, M_n è compatibile sia col fatto che Alice ottenga la carta Z, sia che Bob ottenga la stessa carta. Quindi il protocollo non garantisce che Bob e Alice ottengano carte diverse. E dunque il mental poker non è realizzabile. C.V.D.”.

“Ah”.

“La prossima volta vediamo come si può giocare a mental poker”.

“Grrr”.

⇐ · ⇒