A Game of Probabilities

[Yoruichi-san]

You and I are playing a little game (that is in no way whatsoever related to any game played on this site *cough*). There are 12 objects, 4 of which have the property M. The goal is to choose an object with the property M.

However, you and I are playing by different rules. For each round, first there is the N phase, in which you secretly choose an object (write down its number or something), then there is the D phase, during which I pick an object and it is revealed whether or not the object has property M.

If the object I pick has the property M, I win, if not we keep going. During any N phase, after you choose an object, you can call 'STOP' and the game will end. Then you reveal your choices, and if at least one has the property M, you win. If none have the property M, I win.

What is your play?

Bonus: Generalize to a case of n objects, k of which have the property M.

[Yodell]

not related in any way to a game on this site ???

wd Y-san .. u did it ...

edit... added spoiler

Edited June 22, 2012 by Yodell

[CaptainEd]

I guess neither of us knows which objects have property M, and we rely on a third party to give us a determination at the end of each N phase or the STOP event?

[Yoruichi-san]

I guess neither of us knows which objects have property M, and we rely on a third party to give us a determination at the end of each N phase or the STOP event?

Yes, or they could be, like, upside down cards or mahjong tiles or something like that that we shuffled.

[Yoruichi-san]

Or beakers of acid/base we test with litmus paper...or glasses of pepsi/coke we taste test...but not beakers of acid/base that we taste test...

(sorry, couldn't resist ;P)

[phil1882]

let me see if i have the riddle correct with an example.

let's say i have 12 playing cards, 4 of which are spades. all cards are over turned, so no one knows which is which.

player 1 chooses 1 card, and keeps it down turned.

then player 2 chooses 1 card. player 2's card is revealed. if it's a spade, he wins, else keep playing.

player 1 picks another card (assuming player 2 didn't win.) player 1 can call stop. if either of the two cards are spade, player 1 wins.

else, player 2 wins.

sound good?

[CaptainEd]

I think the second player could choose one of the cards chosen by the first player, as the first player's choices are secret.

[bonanova]

The game seems simply to determine when to say Stop.

Seems that 2 draws puts your winning chances above 50%.

So I'm stopping after my 2nd draw.

[bonanova]

let me see if i have the riddle correct with an example.

let's say i have 12 playing cards, 4 of which are spades. all cards are over turned, so no one knows which is which.

player 1 chooses 1 card, and keeps it down turned.

then player 2 chooses 1 card. player 2's card is revealed. if it's a spade, he wins, else keep playing.

player 1 picks another card (assuming player 2 didn't win.) player 1 can call stop. if either of the two cards are spade, player 1 wins.

else, player 2 wins.

sound good?

Only possible difference is that player 2 [i think] doesn't know which card player 1 has chosen.

E.g. P2 might choose one of them herself, and thus can 'steal' some of p1's chances.

[Yoruichi-san]

Yes, your choice is secret, and the object (beaker/tile/card) is not removed from the selection process.

And if I choose your card, your chances for stopping the second round aren't as good.

[bonanova]

The game seems simply to determine when to say Stop.

Seems that 2 draws puts your winning chances above 50%. 

So I'm stopping after my 2nd draw.

Generalizing to j and k,

I would compute player 2's chances with player 1 being silent.

On the turn the it exceeds 50%, I would say stop.

[bushindo]

You and I are playing a little game (that is in no way whatsoever related to any game played on this site *cough*). There are 12 objects, 4 of which have the property M. The goal is to choose an object with the property M.

However, you and I are playing by different rules. For each round, first there is the N phase, in which you secretly choose an object (write down its number or something), then there is the D phase, during which I pick an object and it is revealed whether or not the object has property M.

If the object I pick has the property M, I win, if not we keep going. During any N phase, after you choose an object, you can call 'STOP' and the game will end. Then you reveal your choices, and if at least one has the property M, you win. If none have the property M, I win.

What is your play?

Bonus: Generalize to a case of n objects, k of which have the property M.

Here's an approximative strategy,

At every point of the game, we can summarize the current state of the game with the number of remaining objects (R), the number of unopened chosen objects (c), and the k number of objects with property M.

We define a function for the probability of winning at state (R, c, k) as

The strategy now is as follows,

1) At the beginning of N phase (before we choose an object), we calculate the chance we would win if we were to call stop at that N phase. Call this S₀, which is defined as

S₀ = W( R, c + 1, k )

2) We then calculate the chance we would win if we go through one more round and then stop at the next N phase. Call this S₁, which is defined as

S₁ = ( 1 - k/R ) * [ [ ( c + 1 )/R ] * W( R - 1, c + 1, k ) + [ 1 - (c+1)/R ]* W( R - 1, c + 2, k ) ]

3) If S₁ > S₀, then continue the game. Otherwise, stop the game.

Back to the example where R = 12 and k = 4. At the first turn where c = 0, which means the game state is (12, 0, 4), we get

S₀ = .3333

S₁ = .398

Which means that we should continue the game. If the opponent does not win the game during next turn, then there are two possible next states, which are

(11, 1, 4) - The opponent did not open your chosen door - The strategy above says that we should stop at this N phase.

(11, 0, 4) - The opponent did open your chosen door (essentially a new game with R = 11) - The strategy above says we should continue the game.

Continue until the strategy calls for a stop.

Edited June 24, 2012 by bushindo

[Yoruichi-san]

Excellent, thank you Bushindo

I thought there might be multiple ways of looking at the problem, but felt that the differential method was the best, although I have no idea how to prove it. It makes a 'profit=marginal cost' kind of sense.

And yes, one of the key aspects, I think, is that the probabilities change each round, after you get information (that is, whether I choose your object). I.e., for the mth round, you calculate the probability you win if you stop at the (m+1)th round taking into account the probability that I choose your object, but during the (m+1)th round, you know whether I chose your card or not.

The other possible way I can see for looking at the problem is to assume an infinitely large n, such that at the stopping point, P(winning if you go one more round)=P(winning if you 'STOP' now), and working backwards.

[dpalmer]

The best strategy for N is to yell STOP only and as soon as he or she recieves something with property M because the payoff for losing is symmetrical to both ways of losing (D draws M or N calls STOP holding only not-M). It always pays to go another round after drawing not-M. It might be a more interesting game if there were different payoffs, though. What if it cost more to lose from D drawing M than from yelling STOP while only holding not-M? If that were the case, there would be a point at which it becomes more costly to continue playing. The payoff matrix would be based on the notion that k/(n-x) is the probability of winning the next round {where x is the number of the round, k is the number of objects with M, and n is the total number of objects}. I decided not to keep going and calculate the whole payoff because I need a function which is 0 when x is odd and 1 when x is even, and I'm a little too lazy for that.

[dpalmer]

Oh, I was assuming that the choice was only secret for D, but N knows what he or she draws. Those are two different games.

[voider]

Consider the decision tree.

You can calculate the probability that you will win, when you predetermine on which round you will say STOP (if you survive until that round).

The first round probability is 4/12=0.33

Second is 0.397979...

This increases, until some round to say STOP where the probability of winning will begin to drop.

Obviously the "general solution" is to say STOP on the round that produces the overall highest probability of winning relative to the beginning of the decision tree.

My solution would be a computation, rather than a calculation. There are multiple ways of presenting it, but none of them would look nice.

[voider]

The best strategy for N is to yell STOP only and as soon as he or she recieves something with property M...

You can't say STOP after they've already won.

[dpalmer]

Some people are arguing that it's best for N to go 2 rounds because then he or she has over a 50% chance of winning. The problem is allowing round 2 gives D a 31.8% of winning. That means letting the game reach round 2 only gives N a 1.2% net advantage for allowing it vs. a 33% advantage for calling STOP after the first draw. I'd say N's best strategy is to call STOP after the first draw.

[dpalmer]

You can't say STOP after they've already won.

Of course not, but it doesn't matter. If N knows what he or she draws, then the only reason to continue the game is if he or she draws not-M. Calling STOP at this point would ensure a loss. Continuing gives a chance of victory and a chance of loss. So clearly it's better to allow another round. This logic continues until k=n, at which point whoever draws next wins.