A game theory problem that puzzled Marilyn vos Savant

Marilyn vos Savant is most known for being listed as the “Highest IQ” in the Guinness Book of World Records.

She is also famous for her column “Ask Marylin” in Parade magazine (that she has written since 1986) that tackles interesting questions and puzzles, the most controversial being the Monty Hall problem.

The following question appeared in her column on March 31, 2002, and it is an interesting game theory problem:

Say you’re in a public library, and a beautiful stranger strikes up a conversation with you. She says: ‘Let’s show pennies to each other, either heads or tails. If we both show heads, I pay you $3. If we both show tails, I pay you $1. If they don’t match, you pay me $2.’ At this point, she is shushed.

You think: ‘With both heads 1/4 of the time, I get $3. And with both tails 1/4 of the time, I get $1. So 1/2 of the time, I get $4. And
with no matches 1/2 of the time, she gets $4. So it’s a fair game.’

As the game is quiet, you can play in the library. But should you? Should she?

- Edward Spellman, Cheshire, Connecticut.

Source: “Ask Marilyn,” Parade, March 31 2002, quoted in Siam News June 2003.

Here is Marylin’s answer which appeared in the following issue:

The woman in the library said: ‘Let’s show pennies to each other, either heads or tails. If we both show heads, I pay you $3. If we both show tails, I pay you $1. And if they don’t match, you pay me $2.’

Should you play? No.

She can win easily. One way: If she shows you twice as many tails as heads, she wins an average of $1 for every six plays.

While the answer is on the right track, and the logic is proper, I would still have to say the answer is wrong because it is incomplete. It only specifies one possible best response and the reasoning stops.

At best, that answer would get partial credit in a game theory class.

The complete answer would specify the equilibrium strategies for both players along with their payoffs. Then it would be fair to answer whether the game is worth playing.

The challenge to you: Can you figure out the complete solution? Does the game favor you or the beautiful stranger, or is it fair?

Write your thoughts / ideas / guesses in the comments.

I will post my writeup of the solution in a few days in the comments section.



Share this post:

| More

Previous post:

Next post:



  • richard

    I would say that the complete solution would include how beautiful the woman is relative to how single I am :)

  • Scott

    I’m having some difficulty in this one, at least without my books at hand.

    As it is, it seems that the proposed answer is only true if you play Heads and Tails with equal probability. In which case, the average pay off is:

    ~17% * $3 (heads-heads) + ~33% * -$2 (heads-tails) + ~17% * -$2 (tails-heads) + ~33% * $1 (tails-tails) = ~-$0.17 per play (or -$1 per six plays)

    From what I’ve been able to determine so far, that, no matter what strategy either player chooses, it’s better for the other player to either play all heads or all tails, depending on said strategy, implying the lack of an equilibrium.

    For example, if I knew she was playing twice as many tails as heads, I would play all tails. This would make the average payoff:

    0% * $3 (heads-heads) + 0% * -$2 (heads-tails) + ~33% * -$2 (tails-heads) + ~66% * $1 (tails-tails) = $0.00

    Granted, I break even, but any other strategy turns in her favor. But, realizing that I’m playing all tails, she’d play all heads and, realizing she’s playing all heads, I’d also switch to all heads, and an endless back and forth ensues (along with hijinks, presumably).

    Now, assuming there is no equilibrium, and assuming that lack of an equilibrium results in a back-and-forth that is tantamount to randomness, I’d presume this would result in an effective strategy of 50% for each player, which breaks even.

  • Tim

    Clearly there is no pure strategy equilibrium (I want to match, she wants to mismatch). Since a Nash equilibrium always exists, it must be in mixed strategies. This means that I must be mixing with probabilities that makes the stranger indifferent between playing heads and tails, and she must be mixing with probabilities that make me indifferent between playing heads and tails. If she is playing pH+(1-p)T, then my indifference condition is:

    3p-2(1-p)= -2p + 1(1-p) -> p=3/8, so my payoff from playing either heads or tails is -1/8; that is, I expect to lose $1 every 8 times we play. So, the game isn’t fair and I shouldn’t play.

    For completeness, let’s find my strategy. If I’m playing qH+(1-q)T, then the stranger’s indifference condition is:

    -3q +2(1-q) = 2q -1 (1-q) -> q=3/8

    So, her payoff from playing either heads or tails is 1/8, which isn’t surprising since this is a zero-sum game.

    To sum up: in equilibrium, we both play heads 3/8 of the time and tails 5/8 of the time. This results in an expected payoff of $1/8 from me to the stranger each time we play.

  • M. Allen

    This seems like a pretty straightforward simultaneous game. Not quite the typical matching pennies, but calculating the mixed strategy equilibria for both players does not appear overly complicated.

  • Frank

    Marilyn discusses the problem as if it’s a repeated game, in which case a strategy is a contingent sequence of choices, not necessarily a constant mixed strategy. She proposes a constant mixed strategy that (Scott shows) reduces the player’s payoff to zero. This is a lower bound on the payoff she could get (and an upper bound on the player’s payoff), so without going any further we know it’s individually rational not to play.

    Right?

  • Travis

    The expected payout to you is 3*(p1*p2) + (1-p1)(1-p2) – 2*p1*(1-p2) – 2*(1-p1)*p2, where p1 is the probability of the stranger choosing heads and p2 is the probability of you choosing heads. The equilibrium comes out to each of you choosing heads 3/8 and tails 5/8, for an expected payout at equilibrium of 1/8 to the stranger. So far, not a good game.

    To verify that this isn’t just a minimum, assume the stranger plays this strategy and you know they will stick to it. Playing pure heads against them gives an expected payout of (3*3 – 5*2)/8, or 1/8 to the stranger. Playing pure tails gives (-2*3 – 5*1)/8, or -1/8 to the stranger. Likewise, any combination of these two strategies will pay an average of 1/8 to the stranger.

    So, in summary, you should not play this game. If the stranger plays a random 3-5 heads-tails strategy you will in the long run lose $1 every eight games.

  • Kyle

    I worked it out the same as Scott. The best strategy for both players in the long term is to mix heads and tails equally.

  • Joon

    I’m just commenting so I can get an email when Presh posts the solution. The key word in this problem is in fact “beautiful.”

    The marginal benefit you receive from silently gambling/flirting in a library easily outweighs any potential losses.

  • Scott

    @Travis:

    Wow. Can’t believe I missed that. I was working out the different strategies manually, basing my assessment on increments of 10% percent. While I had in my mind that I would need to continue to narrow the scope, I guess I forgot that part, totally missing on your find.

    Good work!

  • http://asad123.wordpress.com Asad

    Even though it has little mathematical basis, I find Joon’s reasoning compelling. I wouldn’t go so far as to say that I’d pay any price to flirt, but it’s not hard to break even on the game (using Kyle’s method) and get the benefit of her company, thus come out a winner.

  • http://www.unioviedo.es/fidalgo Eduardo

    I worked this the same as Scott and I agree that the mixed strategies Nash Equilibrium is P=3/8, q=3/8.
    However, I don’t agree that you should not play the game. Being p the probability that the stranger plays heads and q the probability that I play heads, the payoff for the stranger in this Nash eq. is:
    -3pq+2p(1-q)+2(1-p)q-1(1-p)(1-q)=-8pq+3p+3q-1=-2/8
    And my payoff is (equally derived):
    8pq-3p+3q-1=+2/8

    Perhaps there is some mistake in that but I cannot see it right now. Please check it.

    Conclusion: the stranger has the incentive to show more tails than heads (reduce p), because my payoff in the case of winning is lower with tails. But, because of that, I can increase the number of times I win by playing tails more times (reducing q). By adjusting my frequency of showing heads to only 3/8 I can exploit this as an advantage making less per win with more wins.

  • http://www.unioviedo.es/fidalgo Eduardo

    When I said Scott I meant Tim. Sorry

  • Dan

    Eduardo – Algebra is good. Probably a simple mistake as it does equal +/- 1/8
    -8pq+3p+3q-1 = -8(3/8)(3/8) + 3(3/8) + 3(3/8) +1
    = -72/64 + 9/8 + 9/8 + 1 = (-72 + 72 + 72 + 64)/64
    = -8/64 = -1/8

    Also, I believe Tim is making another point with the term “indifference condition”. If the stranger plays a strategy of 3/8H:5/8T, she will on average win $1/8 per play INDEPENDENT of what you do. It is similar if you deploy a 3/8H strategy, she will on average win $1/8 per play independent of what she does.

    So when is the game fair? The stranger needs to collect the square root of 3 or ~$1.73 instead of 2. (There probably is a nice derivation of this; I used Excel trial/error) The break-even strategy is then calculated as (SQRT(3)-1)/2 or ~0.366H.

  • http://www.unioviedo.es/fidalgo Eduardo

    I see. Yes I made a sign mistake. The actual equilibrium payoffs are 1/8 for the stranger and -1/8 for the poor guy. So my conclusion would be exactly the other way around. Thank you Dan.

  • Kevin

    Definitely play the game. After she takes some money, explain how you knew you should expect to lose, and how much, and how you only played to share the company of such a clever and beautiful stranger. There’s a certain James Bond suaveness in taking small loser bets to maybe get a big payoff somewhere else, and we know what happens to Mr. Bond when he gambles.

  • http://www.mindyourdecisions.com/blog/ Presh Talwalkar

    Thanks all for the comments and the correct solutions.

    The correct answer is that both people will play a mixed strategy of heads 3/8 times and tails 5/8 in equilibrium, yielding the stranger a profit of $1/8, or $1 in eight games.

    For details on the derivation, there is a nice explanation with the algebra in this pdf file.

    The game is not fair, and another example of why one should be skeptical of beautiful strangers.

  • john

    Good puzzle and answer, and I realize I’m really late with this comment, but I have 2 points to make if you’ll allow.

    First, if you accurately copied Marilyn’s answer, its logic isn’t “proper” and she is wrong not just out of incompleteness.

    The stanger will win in the long run with a stategy with 7/24<p<1/3 (where p is the probability she shows heads). Marilyn suggests she (the stranger) will win by choosing p=1/3 which is not a guaranteed win, and certainly not a $1 average every 6 games! To get this answer she has to be assuming that I MUST show heads and tails equally, while the stranger can choose her strategy. I'm sorry, but I cannot consider this "proper" logic.

    Second, for completeness and because Dan brought it up. It is very easy to determine a fair game. Dan is right that making the mixed payoff the square root of 3 dollar to her would make it fair. But the square root of 3 isn't a viable dollar amount. Instead, I would make the HH payoff be $4 to me.

    To find this, simply make the indifference condition be 0 (i.e. fair). Call the HH payoff X, and you get 2 equations. One with only p ((1-p)-2p=0) which gives p=1/3, then solve for X in the other (pX-2(1-p)=0) to find X=$4.

    Because of the symetry, either player can force the game to be fair by using a p=1/3 strategy when X=$4.

  • Omar Arredondo

    I believe Marilyn is right!

  • Omar Arredondo

    I believe that the fact that the stranger is beautiful is going to make you play and Marilyn says the stranger has a better change of winning so since she is beautiful, it is most likely that you will play just to get to know her, and the odds are that you will lose money because i believe Marilyn is right because there is more chance of both not being heads or tails. and course there is going to be times that you win. but the more you play the better chance you have of losing money

  • Omar Arredondo

    This game is not fair the stranger will always have a chance of winning and the more you play the better chance the stranger will have of winning





Previous post:

Next post:

Other posts you may enjoy reading:

This site is for recreational and educational purposes only (privacy policy)

Powered by WordPress