4
$\begingroup$

100 prisoners are given an opportunity to go to a theatre and watch a movie. Each can choose either to go or not. However, if everyone chooses to go to the trip then no one is allowed to go.

The prisoners can't communicate with each other and all are equally selfish. They all follow the same strategy to make a choice.

What could be a strategy that allows some of them to go? How can the strategy be optimized so that maximum of the prisoners can see the movie?

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ They can't really be perfectly selfish. The strategy of always choosing to go on the trip dominates every other possible strategy, every time. If they were perfectly selfish, they'd just all choose to go with 100% probability. If they're not perfectly selfish, then they should just randomly choose a prisoner to not go. That's what an "each prisoner chooses randomly and independently" solution amounts to anyway. $\endgroup$
    – Jack M
    Commented Oct 17, 2017 at 20:11
  • 1
    $\begingroup$ If only one prisoner says no, then the other 99 get to? $\endgroup$
    – Carl
    Commented Oct 17, 2017 at 21:08
  • $\begingroup$ If all prisoners are selfish and have no way to communicate, then there is no "strategy". A strategy means that there is agency, and if the only choice I have is to go or not to go, then the only possible outcomes are "You are guaranteed to lose" and "You are very likely to lose". As such, the perfect strategy is "Chose to go and hope someone gets shanked in the shower" $\endgroup$
    – MechMK1
    Commented Nov 10, 2017 at 13:55

3 Answers 3

Reset to default
12
$\begingroup$

If each prisoner

chooses to go independently with probability p (which on the face of it seems like the only class of strategies they can actually employ)

then

the probability that a given prisoner gets to go is p times the probability that at least one of the others chooses not to go; that is, $p(1-p^{99})$.

This is maximized when

$100p^{99}=1$ or $p=100^{-1/99}$ which is about 0.955. This gives each prisoner about a 0.945 chance of seeing the movie.

Improve this answer
$\endgroup$
12
  • $\begingroup$ Think you have a typo somewhere, you say 0.955 and 0.945.. $\endgroup$
    – Beastly Gerbil
    Commented Oct 17, 2017 at 17:01
  • 1
    $\begingroup$ They're probabilities of two different things. $\endgroup$
    – Gareth McCaughan ♦
    Commented Oct 17, 2017 at 17:01
  • $\begingroup$ (I may well have a typo anyway, of course. In fact I did, a formatting error, but I've fixed it now.) $\endgroup$
    – Gareth McCaughan ♦
    Commented Oct 17, 2017 at 17:02
  • $\begingroup$ A lame question maybe - how is it maximized in that form? Could you please explain.. $\endgroup$
    – Saurav Das
    Commented Oct 17, 2017 at 17:23
  • $\begingroup$ @SauravDas take the derivative of the formula $p(1-p^{99})$ with respect to $p$ and set it to zero. Solve for $p$. Aka solve $1-100p^{99}=0$. The value is $0.954548456661834$... $\endgroup$
    – kaine
    Commented Oct 17, 2017 at 17:33
1
$\begingroup$

Here is my answer:

First of all, the answer depends on how you would like to maximize your way. To be honest, I believe this is open-ended question because there is no best optimized $p$. In other words, what would be your confidence interval? Some likes 99%, some other 95% not 100 people to go:

For 95%

$p^{100}=0.05$, which makes our $p=0.97$

For 99%

$p^{100}=0.01$, which makes our $p=0.955$ which is practically the same answer as Gareth's answer.

and some others (like me), I would try to maximize the probability of at least 90 people go with low chance 100 will go:

maximize $C(100,99)(1-p)\times p^{99}+C(100,98)(1-p)^{2}\times p^{99}+...+C(100,90)(1-p)^{90}\times p^{90}$

which makes the result as

$p=0.9543$ with $0.93\%$ 100 people will go.

If I would try to maximize the probability of at least 95 people will go with low chance 100 people go:

$p=0.9736$ with $7 \%$ 100 people will go.

As I said, it is preference and I believe there is no exact solution for this problem.

Improve this answer
$\endgroup$
4
  • $\begingroup$ The question says all prisoners are selfish, that is they don't care about the probability that others will go to the movie. $\endgroup$
    – ffao
    Commented Oct 17, 2017 at 23:24
  • $\begingroup$ @ffao if each prisoner goes independently with the probability of p as Garerh's answer. $\endgroup$
    – Oray
    Commented Oct 18, 2017 at 5:12
  • $\begingroup$ So those answers (yours and Garerh's) mean that you give the prisoner 'probability' (e.g. Dice or some sort of thing which count one individual chance of going to theater), which define if one could go or not. Correct? $\endgroup$
    – Cockabondy
    Commented Oct 18, 2017 at 7:27
  • $\begingroup$ @Cockabondy yes, it is like giving a dice, they roll and decide to go or not. $\endgroup$
    – Oray
    Commented Oct 18, 2017 at 7:34
0
$\begingroup$

Assuming that the prisoners can generally communicate between themselves, but not when the choice of going to the theatre is given, they will take turns for choosing not to attend. This may be based on an prisoner number given by the guards, the cell number... The exact details aren't important, just that there is an order known by all the inmates. When it is their turn for not going, it is in their selfish interest to play fairly and choose so, since otherwise they will be beaten/punished by the other 99 prisoners.

(Actually, exchanging the no-goer role would be common, and those in the top of the pyramid would always end up going)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.