Hacker News new | ask | show | jobs
by adyavanapalli 2965 days ago
I'm curious, is there a better strategy?
2 comments

There is not, actually! You can show this strategy does as well as the case where prisoners have full information of each other's moves.[0] So any other strategy where each prisoner is blind to others' actions can always be executed in the full-information case above; so this bound is tight and this strategy is optimal: if there was a strategy that did better in the blind case, you could execute it in the full-information case to get a better outcome, but this is impossible.

For a nice exposition of this, see Curtin and Warshauer's article "The Locker Puzzle."

---

[0] More specifically, a game where all lockers are left open, so every strategy has the same probability of winning.

To be precise, the strategy is shown to be optimal as well in a modified game where all lockers are left open and you cannot open any more lockers if you find your own number.
Any better strategy would have to exhibit the cyclic behavior of the proposed strategy. I don't think there is any.