Re: Prisoners Dilemma

OK, since no-one even replied to that prisoner's dilemma, I guess it's time to produce some clues. We'll name the prisoners P1 through Pn and boxes B1 through Bn. We'll also, to avoid complications, assume the warden is going to arrange the boxes purely at random (so we don't need to cope with the warden just putting P1 in B2 and P2 in B1 for the 2 prisoner case, for example).¹

How do two prisoners play our game? If they both pick randomly, their joint chance of success is 1/4. However, if P1 picks B1 and P2 picks B2, they're either both correct or both incorrect, each with a 1/2 chance. This must be optimal or there'd be some one-prisoner strategy which is better than just picking one box.

What does this tell us?

1. The prisoners each need to pick different strategies.
2. The prisoners could do with knowing each other's strategies.

What follows is a description of the 3 prisoner optimal strategy and big clues on optimal strategies, so stop reading if you don't want to know more.

OK, so let's try that knowledge on 3 prisoners. The 'obvious' strategy for prisoner Pi is to pick box Bi, then B(i+1 mod 3). If he gets any wrong the prisoners fail no matter what they pick, so they may as well assume he was right and the remaining arrangements are:

• (1, 2, 3)
• (1, 3, 2)
• (2, 1, 3)
• (3, 1, 2)

Referring to "prisoner i succeeding" as Si, this tells us that P(S1) = 2/3 and P(S2|S1) = 3/4. (3 of the 4 possibilities have a 2 in B2 or B3). However, we're left with the following:

• (1, 2, 3)
• (1, 3, 2)
• (3, 1, 2)

In other words, P3 has no more information than P1 did, so P(S3|S2,S1) = 2/3 and the overall success probability is P(S1,S2,S3) = P(S1) * P(S2|S1) * P(S3|S1,S2) = 1/3. Can we do better?

The first box P1 picks doesn't matter (you can just re-number the boxes so that it's always B1), but for his second box, he's able to give information about the contents of his first box. How? By picking a different box depending on its contents. Let's say P1 picks B1, then if B1 = P1, stops, if B1 = P2, picks B2 and if B1 = P3, picks B3. There are once again 4 'sucess' arrangements:

• (1, 2, 3)
• (1, 3, 2)
• (2, 1, 3)
• (3, 2, 1)

Taking into account that P1 played this way, can we improve P2's strategy? We can see B2 is clearly a good box to start with as 2/4 of the remaining arrangements boxes have P2 in them. Also, if B2 = 3 then B3 = 2 and if B2 = 1 then B1 = 2. This means following the obvious strategy, P(S2|S1) = 1. P3 can follow a similar strategy so that P(S3|S1,S2) = P(S3|S1) = 1 and P(S1,S2,S3) = 2/3.

So, what do we know now?

3. Each prisoner's second (and presumably subsequent) box picks had better depend in some way on the contents of what he already picked.
4. Slightly deeper, looking at the results above, if one prisoner gets it wrong lots of prisoners should.

¹ You can get around any strategy the warden produces by simply numbering the prisoners randomly after the box order is chosen, so that the warden doesn't know the prisoners' chosen ordering. (It doesn't have to be the same numbering as the warden used to call them in.)