Choosing number game

[tuanl]

pruse: can you explain why the expected winning for \(x_1\in {1,2,...14}\) is \(\frac{1+2+\cdot+14}{20}\) and \(f(x_1)=x_1+1\). I'm thinking about the case where X=10 or X=11, where the 2nd player can choose x_1-1 instead of x_1+1 and wins the game.

 

[pruse]

pruse: can you explain why the expected winning for \(x_1\in {1,2,...14}\) is \(\frac{1+2+\cdot+14}{20}\) and \(f(x_1)=x_1+1\). I'm thinking about the case where X=10 or X=11, where the 2nd player can choose x_1-1 instead of x_1+1 and wins the game.

\(E(winnings) = \sum_{k=1}^{20} E(winnings|X=k)P(X=k)=\sum_{k\in S}\frac{k}{20}\), where \(S\) is the set of \(X\)'s where you win (because for all other \(k\)'s, your winnings are 0).

For instance, if you pick 11 and then your opponent picks 12, you of course win for any \(X\in \{1,...,11\}\) as these are the numbers closer to 11 than to 12. Plugging into the above, your expected winnings for this case are thus \(\frac{1}{20}(1+\cdots+11)\)

 

[tuanl]

I finally see your strategy! It basically maximizes the expected value of winning for the 2nd player, and turns out that if the 1st player also plays optimally(by choosing 14 or 15), then the expected winning of both players are the same. Since when the 1st player chooses a number x, then either \(X \in[1,2,...,x]\) or \(X\in [x+1,..,20]\), so the 2nd player can always maximize his expected winning by choosing x+1 or x-1, depending on the actual value of x.

Btw, why do you choose 14 to divide the problem into 2 cases? I guess you found this number by first summing \(1+2+\cdot +20\), then divide this sum by 2 and see that the sum from \(1+2+\cdot +14\)=the sum/2. And do you know any books that can give me insight for solving these kinds of 2-people game problems?

 

[pruse]

Since when the 1st player chooses a number x, then either \(X \in[1,2,...,x]\) or \(X\in [x+1,..,20]\), so the 2nd player can always maximize his expected winning by choosing x+1 or x-1, depending on the actual value of x.

It's not that \(X\in\{1,...,x\}\) or \(X\in\{x+1,...,20\}\) if Player 1 picks \(x\) (\(X\) is random and can be anywhere)... it's that Player 1 knows what Player 2 will play after he plays \(x\) (see my argument above). Once he knows this, he knows what his expected winnings are because he knows that he wins if \(X\) is in one of those sets (depending on his choice of \(x\)).

It's 14 (or 15) because this is the value for which his expected earnings are maximized (sum of numbers up to 14, divided by 20), knowing what Player 2's optimal move will be.

102 Combinatorial Problems by Titu Andreescu and Zuming Feng is good for all sorts of combinatorial problems like this, plus others. It goes from fairly easy to very hard (IMO level). 102 Combinatorial Problems

 

[tuanl]

It's not that \(X\in\{1,...,x\}\) or \(X\in\{x+1,...,20\}\) if Player 1 picks \(x\) (\(X\) is random and can be anywhere)... it's that Player 1 knows what Player 2 will play after he plays \(x\) (see my argument above). Once he knows this, he knows what his expected winnings are because he knows that he wins if \(X\) is in one of those sets (depending on his choice of \(x\)).

Well, X is random, but it's already chosen before these two players start the game (of course they just don't know what it is). The way player 1 picks a number x will surely result in \(X\in\{1,...,x\}\) or \(X\in\{x+1,...,20\}\). These 2 events are equally likely to occur, so I think that's why the expected winnings of both players are the same if they play optimally. I also think that the reason player 2 plays the way you defined is because he will always get the maximum expected winning since he already knows what number player 1 plays in every case(e.g: if player 1 plays 11, then player 2 will play 12(since in this case the expected winning for player 2 is maximized when he plays 12) and he has probability of winning=1/2(for X>11. This why he chooses 12) and prob. of losing=1/2(for X<11. In this case, his expected winning is always< that of player 1, so there's no point of not risking to choose 12 since P(X<11)=P(X>11)=1/2)

 

[pruse]

Well, no, those two events are not equally likely to occur, unless those sets have the same size, which only occurs for \(x=10\). It's not about the probability of winning, so much as it is about the players' expected winnings. For instance, if player 1 plays 12, then player 2 will play 13 because this maximizes his expected earnings; however, it does not maximize his probability of winning; he wins with probability 8/20 if he plays 13, but with probability of 11/20 if he plays 11. In most cases, however, the e.v.-maximizing play also maximizes the probability of winning.

Now, if risk aversion comes into play, which is better, going first or second? The variance of player 1's e.v.-optimizing strategy of playing 14 first is \(\frac{1^2+\cdots+14^2}{20}-\large(\frac{105}{20}\right)^2\), smaller than player 2's variance of \(\frac{15^2+\cdots+20^2}{20}-\large(\frac{105}{20}\right)^2\). Obviously roles are then reversed if Player 1 instead plays 15, even though 15 gets the same e.v. So from a risk perspective, you should actually choose to go first and play 14.

 

[tuanl]

Well, no, those two events are not equally likely to occur, unless those sets have the same size, which only occurs for \(x=10\). It's not about the probability of winning, so much as it is about the players' expected winnings. For instance, if player 1 plays 12, then player 2 will play 13 because this maximizes his expected earnings; however, it does not maximize his probability of winning; he wins with probability 8/20 if he plays 13, but with probability of 11/20 if he plays 11. In most cases, however, the e.v.-maximizing play also maximizes the probability of winning.

Now, if risk aversion comes into play, which is better, going first or second? The variance of player 1's e.v.-optimizing strategy of playing 14 first is \(\frac{1^2+\cdots+14^2}{20}-\large(\frac{1}{20}\right)^2\), smaller than player 2's variance of \(\frac{15^2+\cdots+20^2}{20}-\large(\frac{1}{20}\right)^2\). Obviously roles are then reversed if Player 1 instead plays 15, even though 15 gets the same e.v. So from a risk perspective, you should actually choose to go first and play 14.

I still can't see why those two events are not equal. Since X is already chosen in [1,20], so no matter what values of x, it's either in [1,...,X] or [X+1,..,20], and the probability of each event is definitely 1/2 (your choice of x is not biased by anything).

The variance of player 1 should be \(\frac{1^2+\cdots+14^2}{20}-(\frac{105}{20})^2\), and Var. of player 2 is \(\frac{15^2+\cdots+20^2}{20}-(\frac{105}{20})^2\), but your analysis is correct.

 

[pruse]

Yes, those should be 105's; that's what happens when you type fast.

So you're saying that the sets \(\{1,2\}\) and \(\{3, 4, 5, ..., 20\}\) have equal probability? that's obviously not true; the first has the very small probability of \(\frac{1}{20}+\frac{1}{20}=\frac{2}{20}\), while the second has probability of \(\frac{18}{20}\)