IBM　二月 - 珍珠湾ART - Powered by Discuz!

This month's puzzle is about a simple 2 player poker like gambling game. The two players each ante 1 unit to a pot. Then each player receives a random number uniformly distributed between 0 and 1. Each player knows the value of his number but not the value of his opponent's number. The first player is then given an opportunity to bet one additional unit. If the first player doesn't bet there is a showdown and the player with the highest number collects the antes. If the first player bets the second player may call by matching the bet or drop out (giving the antes to the first player). If the second player calls there is again a showdown and the player with the highest number collects the pot (consisting of 4 units, the bets and the antes). If both players follow their optimal strategy what is the value of the game? In other words if they play (optimally) a large number of games how much is the first player expected to win (or lose if the value is negative) per game?

做出来先别贴，直接去IBM抢沙发。

两人赌钱。每人每次得到一个0，1之间的随机数，然后比大小。每次赌一块钱。第一个人得到数后可以选择是否加倍。第一个人加倍后，第二个人可以选择接受加倍或不接受加倍（认输）。问第一个人赢钱的期望值是多少。

好象挺难的，大约要++++。沙发是抢不着了。

I tried, but got a trivial answer: 0. Let me know what do you think:

I think each person will pick a threshold, and if the number he got is above the threshold, he will bet further. Suppose the first person picks a threshold V1 and the second person picks V2, we can calculate the expected gain of the first person by the followng method:

Consider the unit square [0 1] x [0 1], with the x-axis stands for the random number assigned to the first person and the y-axis stands for the random number assigned to the second person. The unit square is divided into the following regions:

A1 ={x

A2 = {xx}

A3 = {x>V1,y

A4 = {x>V1,y>x}

A5 = {x>V1,y

The first person will earn the following on each region respectivel: 1,-1,1,-2,2

The expected gain on A1 U A2 is -V1(1-V1)

The expected gain on A3 is V2(1-V1)

The expected gain on A4 U A5 is -2(V2-V1)(1-V2)

Put them together, the total expected gain for the first person is

G(V1,V2) = V1-V2+V2^2-3V1V2+2V2^2

The first person faces the following min-max problem: max_{V1}min_{V2} G(V1,V2)

It can be shown that, fixing V1, the worse V2 for the first person is V2=3/4V1+1/4, substitue this into G(V1,V2) and maximize it over V1, we get a trivial V1 = 1. This means that, the first person should never make the additional bet, and his expected gain is 0 -- of cause the same for the second person.

(We have assumed that V2>V1. from graph, it is obvious that V2

the corresponding G(V1,V2) for a given V1)

I have a non-trivial solution, not sure about its correctness, will post it later.

The problem with your solution is that you assumed there is a fixed threshold. The actual threshold for both players may follow a distribution.

听人说这题是 von Neumann 解的。他的解如下：当 x > 0.7 或 x < 0.1 时 A 加倍；当 y > 0.4 时 B 接受加倍。A 赢钱的期望值为 0.1。我的解不是最优的，也就不必登了。