Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Two players are playing a game. The first player has unlimited gold coins of 2 types, $C_1=2\$$ and $C_2=5\$$. Each turn he chooses one of these coins and hides it in his hand. If the second player guesses correctly which type of coin the first player is hiding in his hand, he gets this coin; otherwise he loses $x$ cents. Find the largest integer $x$ for which the game is beneficial to the second player.

I knew the answer, but I forget how we got it. I would appreciate it if someone would explain it for me. Thank you.

Answer is x=316

share|improve this question
    
I'd say that depends entirely on how well he can predict the type of coin. Does the first player choose the coin at random? And if so, with which probability? –  celtschk Aug 26 '12 at 18:34
    
First player chooses depends on his strategy and x. –  Daniel Aug 26 '12 at 18:42
2  
Assuming that the strategy is time- and memory-independent, you shall assume mixed strategies for both players (i.e. player 1 chooses 2 USD coin with probability $p_1$ and player 2 - with probability $p_2$). Looking for best responses, you can find Nash equilibrium depending on $x$ and the expected profit of player 2 depending on $x$. The just check for which $x$ the expected profit becomes negative. –  Ilya Aug 26 '12 at 19:05
    
Ilya i think i get it. Nice! Thank you. –  Daniel Aug 26 '12 at 19:13
    
@Daniel: you are welcome. Please tell me if you need hints on such computations. –  Ilya Aug 26 '12 at 19:22

2 Answers 2

up vote 5 down vote accepted

Since the first player has an unlimited number of coins he shouldn't care how much money he loses and there aren't any predictions on his strategy possible. But lets just assume he wants to loose as little money as possible.

Let player 1 choose the coin $C_1$ with probability $p$ and let player 2 choose the coin $C_1$ with probability $q$.

Then the expected value for player 2 is $$2pq+5(1-p)(1-q)-(1-pq-(1-p)(1-q))x$$ $$=7pq-5p-5q+5-x(p+q-2pq)$$

Player 2 wants to maximise his profit depending on the first player's strategy. So we derive wrt $q$:

$$7p-5-x(1-2p)$$

If the dervative is positive, player 2 will choose $q$ maximal i.e. $q=1$ with profit $2p-x(1-p)$, if it is negative, player 2 will choose $q$ minimal i.e. $q=0$ with profit $5-5p-xp$, and if it is zero, his choice doesn't matter and for all that it's worth we can assume he takes $q=0$ as well.

So player 1 wants to minimise the maximum of $2p-x+px$ and $5-5p-xp$. Since one is decreasing as a function of $p$ and the other one is increasing the equilibrium is the point where they are equal:

$$2p-x+px=5-5p-xp\Leftrightarrow p=\frac{5+x}{7+2x}$$

The profit of player 2 is then

$$(2+x)\frac{5+x}{7+2x}-x$$

This is positive if and only if $x\leq \sqrt{10}\simeq 3.16$

Edit I assume we might be able to streamline the solution a bit since this $x$ is precisely the value for which the derivative above vanishes. I suspect this is no coincidence. Unfortunatly I have no idea of the general theory and based my solution solely on common sense.

share|improve this answer
    
+1 for the solution. I tried to include it in my answer, but MathJax on Chrome crashed on me twice (known bug). :( –  Ilmari Karonen Aug 26 '12 at 19:38
1  
Yes, there's a well known theorem stating that, for any mixed-strategy Nash equilibrium, all the component pure strategies for each player must have the same payoff. (If they did not, for some player, that player would be better off playing the highest-payoff pure strategy than the mixed strategy.) –  Ilmari Karonen Aug 26 '12 at 19:41
    
@Ilmari: That's true if by "component pure strategies" you mean only those pure strategies which have non-zero probability in the player's mixed strategy. The ones with zero probability may have lower payoff. –  joriki Aug 26 '12 at 22:32

This is a zero-sum game, so the solution boils down to finding the minimax strategies for the two players, calculating their expected payoffs for those strategies and finding the threshold value of $x$ for which the expected payoff to each player is zero.

share|improve this answer
    
It does not seem to be exactly zero-sum, since as far as it looks in OP player 1 does not earn $x$ cent in case player 2 losses them. Not that it should affect the method of finding equilibrium strategy. –  Ilya Aug 26 '12 at 19:07
    
Even if interpreted your way, it's still a constant-sum game: the sum of the two players' payoffs is independent of their strategies. As you correctly note, the theory of constant-sum games is essentially equivalent to that of zero-sum games, as the addition of a constant to all payoffs does not affect the optimal strategies. Indeed, it's a common abuse of terminology (which I may be guilty of above) to use the term "zero-sum game" even for games with a non-zero constant total payoff. –  Ilmari Karonen Aug 26 '12 at 19:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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