[superprismatic]

Two players, A and B, play the following

game: Each secretly chooses a real

number and passes his choice to a judge.

Neither A nor B gets to see the other's

choice of number. The judge then

multiplies the two numbers and reveals

the most significant (non-zero) digit of

the result. If this digit is 1, 2, or

3, player A wins $1 and B wins nothing.

If this digit is 4, 5, 6, 7, 8, or 9,

player B wins $1 and A wins nothing.

If they play N games, each using an

optimal strategy, what is the expected

winnings for each player? Why?

[Guest]

Ok, this is simply probability. Player A as only three combinations that will give him a win, (1x1, 1x2, 1x3). Player B, has: 1x4, 1x5, 1x6, 1x7, 1x8, 1x9, 2x2, 2x3, 2x4, 3,3. This means player A only has a chance to win one third as many games as player B. Knowing this, Player A will probably pick one, the only number that ever gives him a win. Player B, knowing player A will pick one, can pick 4 safely. Only if player A choses three will this result in a loss for him. Therefore the probability if B has a brain, is 100% win for B.

Yes, I know it's sort of a work around. But it works.

Edited January 9, 2011 by Darth Legion

[Guest]

Seeing the last significant digit part, B still has two times as many chances to win as A.

[Guest]

if they both pick a 1 digit number,

A\B 1 2 3 4 5 6 7 8 9

1 A A A B B B B B B

2 A B B B A A A A A

3 A B B A A A A A A

4 B B A A A A A A A

5 B A A A A A A B B

6 B A A A A A B B B

7 B A A A A B B B B

8 B A A A B B B B B

9 B A A A B B B B B

so, with a single pick, A's best bet is either 3 or 4. B's best bet is either 1, 8 or 9.

however when playing multiple rounds the game could get interesting. B would have to start picking values less then 5. preferably 1!

[Guest]

A. going to 3 significant figures, i got that A should pick 3.99 or 4.00 and B should pick 1.00, 9.98, or 9.99.

however, given A's optimal strategy, B really should pick between 1.00 and 5.00 and A should do likewise. this still gives A the favor, but by not quite so much. i get 83817/76183 for the winning ratio A/B.

[dark_magician_92]

20 possibilities for 1,2 & 3 and 53 for others,

so its A will win 20*k games out of 73*k and B will win 53*k out of 73*k.

Two players, A and B, play the following

game: Each secretly chooses a real

number and passes his choice to a judge.

Neither A nor B gets to see the other's

choice of number. The judge then

multiplies the two numbers and reveals

the most significant (non-zero) digit of

the result. If this digit is 1, 2, or

3, player A wins $1 and B wins nothing.

If this digit is 4, 5, 6, 7, 8, or 9,

player B wins $1 and A wins nothing.

If they play N games, each using an

optimal strategy, what is the expected

winnings for each player? Why?

[dark_magician_92]

20 possibilities for 1,2 & 3 and 53 for others,

so A will win 20 games out of 73 and B will win 53 out of 73.

so outta N games, A wins (20/73)*N times and B wins N*(53/73) games.

Two players, A and B, play the following

game: Each secretly chooses a real

number and passes his choice to a judge.

Neither A nor B gets to see the other's

choice of number. The judge then

multiplies the two numbers and reveals

the most significant (non-zero) digit of

the result. If this digit is 1, 2, or

3, player A wins $1 and B wins nothing.

If this digit is 4, 5, 6, 7, 8, or 9,

player B wins $1 and A wins nothing.

If they play N games, each using an

optimal strategy, what is the expected

winnings for each player? Why?

[superprismatic]

20 possibilities for 1,2 & 3 and 53 for others,

so its A will win 20*k games out of 73*k and B will win 53*k out of 73*k.

No, it isn't correct. Sorry.

[superprismatic]

A. going to 3 significant figures, i got that A should pick 3.99 or 4.00 and B should pick 1.00, 9.98, or 9.99.

however, given A's optimal strategy, B really should pick between 1.00 and 5.00 and A should do likewise. this still gives A the favor, but by not quite so much. i get 83817/76183 for the winning ratio A/B.

I don't understand the strategies, though. Remember, they get to choose any real number (except for 0, which makes no sense in this game) with as many digits of accuracy as they want, even infinite. The players could choose π or √2 for example. It seems to me that this would affect strategies a lot.

[Guest]

not really, the further out you go the less effect the digits have on the most significant digit.

[Guest]

you list pi and the square root of 2 as possible choices, but is more degrees of accuracy better?

let's compare.

A      B pick

pick   pi| 3.14 |sqrt(2) |1.41

1.00 | A | A    |   A    |  A

1.15 | A | A    |   A    |  A

1.30 | B | B    |   A    |  A

1.45 | B | B    |   A    |  A

1.60 | B | B    |   A    |  A

1.75 | B | B    |   A    |  A

1.90 | B | B    |   A    |  A   

2.05 | B | B    |   A    |  A

2.20 | B | B    |   A    |  A

2.35 | B | B    |   A    |  A

2.50 | B | B    |   A    |  A   

2.65 | B | B    |   A    |  A 

2.80 | B | B    |   A    |  A

2.95 | B | B    |   B    |  B

3.10 | B | B    |   B    |  B

3.25 | A | A    |   B    |  B

3.40 | A | A    |   B    |  B

3.55 | A | A    |   B    |  B

3.70 | A | A    |   B    |  B

3.85 | A | A    |   B    |  B

4.00 | A | A    |   B    |  B

4.15 | A | A    |   B    |  B

4.30 | A | A    |   B    |  B

4.45 | A | A    |   B    |  B

4.60 | A | A    |   B    |  B

4.75 | A | A    |   B    |  B

4.90 | A | A    |   B    |  B

as you can see it doesn't help much. (A's win ratio in this scenario: pi/3.14, 14 out of 27; sqrt(2)/1.41, 13 out of 27.)

[superprismatic]

you list pi and the square root of 2 as possible choices, but is more degrees of accuracy better?

let's compare.

A B pick
pick pi| 3.14 |sqrt(2) |1.41
1.00 | A | A | A | A
1.15 | A | A | A | A
1.30 | B | B | A | A
1.45 | B | B | A | A
1.60 | B | B | A | A
1.75 | B | B | A | A
1.90 | B | B | A | A
2.05 | B | B | A | A
2.20 | B | B | A | A
2.35 | B | B | A | A
2.50 | B | B | A | A
2.65 | B | B | A | A
2.80 | B | B | A | A
2.95 | B | B | B | B
3.10 | B | B | B | B
3.25 | A | A | B | B
3.40 | A | A | B | B
3.55 | A | A | B | B
3.70 | A | A | B | B
3.85 | A | A | B | B
4.00 | A | A | B | B
4.15 | A | A | B | B
4.30 | A | A | B | B
4.45 | A | A | B | B
4.60 | A | A | B | B
4.75 | A | A | B | B
4.90 | A | A | B | B

as you can see it doesn't help much. (A's win ratio in this scenario: pi/3.14, 14 out of 27; sqrt(2)/1.41, 13 out of 27.)

Your estimate of the expected winnings

for each player is not correct in your

post (#5), although it is in the right

direction (A fares better than B). I

used real numbers in this problem because

it makes it easier to figure out the

optimal strategies. I suspect that you

haven't used optimal strategies in your

calculations. You are certainly correct

that the probabilities for first digit

of the product are changed less and less

as the number of digits increases.

[Quantum.Mechanic]

If A and B choose randomly, A wins slightly more often than B (57% vs. 43%).

Since it's only the leading digit that matters, we can limit the range to real numbers in [1,10) without any loss of generality. The game is essentially unchanged even if restricted to integers between 1 and 9, though the probability distribution will change slightly.

If B plays randomly, A has a 2 piece probability distribution curve. The first piece is from [1,4), an increasing exponential, and the second piece from [4,10), a decaying exponential. B of course has a complementary distribution.

If A were to choose the best single value in the range [1,9], which is 4, then B could choose 2 and always win. Similarly for any value A or B might choose, there is a winning choice for the other player.

Optimal play would involve both A and B playing randomly according to the distribution curve. For example, if A's wins from picking 4 constitutes 40% of A's wins, then A should pick 4 40% of the time.

If both players are playing optimally, then neither can expect to win by any significant amount.

[i'm still trying to work out the math better to prove this.]

[superprismatic]

If A and B choose randomly, A wins slightly more often than B (57% vs. 43%).

Since it's only the leading digit that matters, we can limit the range to real numbers in [1,10) without any loss of generality. The game is essentially unchanged even if restricted to integers between 1 and 9, though the probability distribution will change slightly.

If B plays randomly, A has a 2 piece probability distribution curve. The first piece is from [1,4), an increasing exponential, and the second piece from [4,10), a decaying exponential. B of course has a complementary distribution.

If A were to choose the best single value in the range [1,9], which is 4, then B could choose 2 and always win. Similarly for any value A or B might choose, there is a winning choice for the other player.

Optimal play would involve both A and B playing randomly according to the distribution curve. For example, if A's wins from picking 4 constitutes 40% of A's wins, then A should pick 4 40% of the time.

If both players are playing optimally, then neither can expect to win by any significant amount.

[i'm still trying to work out the math better to prove this.]

I hope you're enjoying this problem. It's

more complex than it appears to be at first

blush. I have some comments on your answer:

Your second sentence is key to the analysis

of this game (that, without loss of generality,

we need only consider reals in the range [0,10)).

But, with optimal play, A will still win

considerably more than B. But, you have to

get the optimal strategies right to determine

this.

[Quantum.Mechanic]

I hope you're enjoying this problem. It's

more complex than it appears to be at first

blush. I have some comments on your answer:

Your second sentence is key to the analysis

of this game (that, without loss of generality,

we need only consider reals in the range [0,10)).

But, with optimal play, A will still win

considerably more than B. But, you have to

get the optimal strategies right to determine

this.

Zero is not inlcuded as an outcome. If either player chooses 0, the product is 0, and the outcome is undefined.

Any decade is equivalent to any other decade, so [0.1,1) is equivalent to [1,10), etc.

Yes, it is more complex than I thought. Simulating with weighted probabilities shows similar results to random picks.

Edited January 11, 2011 by Quantum.Mechanic

[superprismatic]

Zero is not inlcuded as an outcome. If either player chooses 0, the product is 0, and the outcome is undefined.

Any decade is equivalent to any other decade, so [0.1,1) is equivalent to [1,10), etc.

Yes, it is more complex than I thought. Simulating with weighted probabilities shows similar results to random picks.

Sorry, that 0 was a typo. It should have been [1,10) as you had in your original post. Although any decade will do, I find it easier to work with the one you picked to use.

[Guest]

It has been nearly a decade since I tried solving a game theory problem. Here is my attempt.

and arrived at this table which shows if a player were to chose the number, what are favorable outcomes (out of 9) depending on what the other player chooses.

# A B

-- -- --

1 3 6

2 6 3

3 7 2

4 7 2

5 6 3

6 5 4

7 4 5

8 3 6

9 3 6

So, thinking independently A should ideally chose between 3 and 4; in which case B should chose 2

Similarly, thinking independently B should ideally chose between 1, 8 and 9; in which case A should chose 3

However, if both are going to think this way, we need to go towards multiple levels of iteration: since the selection (3,2) would result in B's win and hence A wouldn't want to go with it. Hence, if assume them not to be so smart then A would win 54% of times while B winning remaining 46% of times.

Edited January 13, 2011 by KlueMaster

[Guest]

If EITHER player chooses numbers randomly, then the product will be random, and B will win twice as often as A. So B's best strategy is to pick random numbers, and A's best strategy is not to play. Apart from this, ANY strategy applied by one side can be counteracted by the other side, making it dependent on an unsolvable infinity long "What if he knows that I know that he knows that I know..." condition.

[Guest]

If EITHER player chooses numbers randomly, then the product will be random, and B will win twice as often as A. So B's best strategy is to pick random numbers, and A's best strategy is not to play. Apart from this, ANY strategy applied by one side can be counteracted by the other side, making it dependent on an unsolvable infinity long "What if he knows that I know that he knows that I know..." condition.

There is no reason for A not to play, seeing as the game costs him nothing, so each player should choose randomly to prevent the other player using a strategy. So my Final answer is A=(N/3)$ B=(2N/3)$

[Guest]

Share a few of my thoughts

Firstly, A and B sd be assumed to be extremely smart, (even if they are not, in the long run, they will gradually become), they will strategitize according to opponent's move. We will see if an equilibrium can be achieved in the end.

Numbers to be considered is [1,10), all other numbers can be converted by 10^n.(we are only focusing on the leftmost number).

Assume B is picking a number randomly, A's best shot is pick 4 so that he can win whenever B's number is in [2.5,10), B's corresponding strategy is to pick a number between 1-2.5 to ensure his victory. This is Iteration 1.

After knowing B's strategy, A will start thinking and pick number from 1-1.6 to ensure his own chance of winning. B will then react to this, picking number from 4-6.25.

A B

Iteration1 4 1-2.5

2 1-1.6 4-6.25

3 2.5-6.4 1.5625

4 1-2.56 or 6.4-10 1-1.5625 or 6.25-10

5 1.6-2.56 2.5-3.90625

6 1-1.024 OR 4-10 1

7 1-4 2.5

8 1-1.6 OR 4-10 1

9 1-4 2.5

B's final strategy is oscillate between 1 and 2.5. However, if A chooses between 1-1.6, he will rethick his strategy and the game will start a new loop. If A chooses between 1.6-4, B chooses 2.5 will win. If A chooses 4-10, B chooses 1 will win. Therefore, I think in the long run, it is a fair game, A and B have to guess each other. A has to guess if B chooses 1 or 2.5 or B thinks he will choose between 1-1.6 and choose some other number. B has to guess if A is choosing between 1.6-4 or 4-10 or 1-1.6.

[Guest]

I think no matter player B chooses 2.5 or 1 or 3rd strategy, there are 2 out of 3 player A's strategies will win the game. E.g. Player B chooses 2.5, Player A can either choose 1-1.6 or 4-10 to defeat player B, A only loses when he unfortunately chooses to use his 2nd strategy 1.6-4.

Likewise no matter what player A chooses, there are only 1 out of 3 player B's strategies will win the game... So player A will win $2N/3

Edited January 14, 2011 by iverson2002939

[bushindo]

Here is a rough stab at the strategy,

At every turn, let player B choose a number with equal probability from the following 13 number set

( 10, 2.5, 6.25, 1.5625, 3.90625, 9.765625, 2.441406, 6.103516, 1.525879, 3.814697, 9.536743, 4, 2)

It is easily shown that this strategy has a worst case winning probability of 5/13 for player B. This strategy can be improved marginally, but I think player B optimal winning rate couldn't get pass 2/5.

[Guest]

Seeing as we haven't heard back from the OP, here is a clearer explanation of my understanding of the problem, and what I believe is the answer, and some proof why.

Consider random points along an infinitly long number line, with infinite resolution.

Multiplying or scaleing this line, can have no effect on the distribution of random points along the line.

Therefore, if at least one player chooses randomly, the result of the multiplication will be random, therefore so will the most significant digit.

In this case the expected winnings are A=3N/9 B=6N/9, seeing as A has 3 winning digits, and B 6 winning digits out of 9 digits.

For any non-random strategy to effect this, a non-random strategy must be applied by BOTH players.

In this case, one player will improve his winnings only at the cost of the other player, therefore the strategy applied by the other player is less than optimal (compared to choosing random numbers).

So the optimal strategy for both players is to choose randomly, for the expected winnings of A=N/3 B=2N/3.

[superprismatic]

Even choosing randomly, a few trials will show you that A wins most of the time. Thus, something is wrong with your analysis. So, join the group -- much of my analyses of problems has been that way!

Seeing as we haven't heard back from the OP, here is a clearer explanation of my understanding of the problem, and what I believe is the answer, and some proof why.

Consider random points along an infinitly long number line, with infinite resolution.

Multiplying or scaleing this line, can have no effect on the distribution of random points along the line.

Therefore, if at least one player chooses randomly, the result of the multiplication will be random, therefore so will the most significant digit.

In this case the expected winnings are A=3N/9 B=6N/9, seeing as A has 3 winning digits, and B 6 winning digits out of 9 digits.

For any non-random strategy to effect this, a non-random strategy must be applied by BOTH players.

In this case, one player will improve his winnings only at the cost of the other player, therefore the strategy applied by the other player is less than optimal (compared to choosing random numbers).

So the optimal strategy for both players is to choose randomly, for the expected winnings of A=N/3 B=2N/3.

[superprismatic]

You got quite close to the actual best winning probabilities. I must admit that I have no idea how you came up with that nice strategy. But, alas, it is possible to get a precise answer to the problem with a quite simple strategy. I am very curious as to how you came up with that 13 number set.

Here is a rough stab at the strategy,

At every turn, let player B choose a number with equal probability from the following 13 number set

( 10, 2.5, 6.25, 1.5625, 3.90625, 9.765625, 2.441406, 6.103516, 1.525879, 3.814697, 9.536743, 4, 2)

It is easily shown that this strategy has a worst case winning probability of 5/13 for player B. This strategy can be improved marginally, but I think player B optimal winning rate couldn't get pass 2/5.

[bushindo]

You got quite close to the actual best winning probabilities. I must admit that I have no idea how you came up with that nice strategy. But, alas, it is possible to get a precise answer to the problem with a quite simple strategy. I am very curious as to how you came up with that 13 number set.

Sorry for the late response. I didn't internet access for the last few days. Here is how I approached the problem,

I first summarize the game with a win/loss map that plots player A/player B numbers and the corresponding outcome. As noted before, it is only necessary to consider numbers between [1, 10). In the following map, the x-axis represent player B's strategy, and y-axis player A's. The red areas are regions where player B would win. The areas are separated by three lines whose equations are displayed on the map,

So the strategy is as follows. Suppose we can only pick 5 numbers as player B, how much red 'areas' can we cover using only 5 points? I started out by picking x1 = 10 as the first number, as it can win over all numbers inside between 4 and 10 from player A (see graph below for illustration). I then project horizontal line (y=4) and see where it meets with the next red region (xy = 10), and then choose that as my next point (x2 = 2.5). The number x2 can beat numbers between 1.6 and 4 from player A. I then draw a horizontal line (y=1.6) and compute to see where it crosses the line (xy = 10). That gives me my third point x3 = 6.25. The graph below carries out the procedure for x1 to x5.

Notice that after these 5 numbers, almost every single number on the y-axis can be between by 2 out of 5 of player B's number. I'm saying 'almost' because the fifth number x5 = 3.90625 has a little bit of white areas under neath it, so the numbers interval (1, 1.024) on the y-axis is only covered once by these 5 numbers. This is not much of a problem, since we can simply add in 5 more numbers using the same procedure with a result that almost every number on the y-axis can be beaten by 4 out of 10 of player B's numbers. I cut the procedure short after 13 numbers (with the resulting winning rate 5 out of 13), but we can repeat this procedure for a longer time and get a winning rate that is approaching 2/5.

This is a wonderfully crafted problem, thanks for posting it. I would love to hear about your strategy on this problem.