Three player lottery elimination

No peek yet, but read much of the discussion.
Three players, two draws each maximum, no information passed.
Range 1 to 100 (a percentile draw).

Player 1: draw 65 or less, stand 66 or better
Player2: same as Player 1
Player3: plays the winner of 1/2: draw 74 or less, stand 75+.

Quote: 98Clubs

Player 1: draw 65 or less, stand 66 or better
Player2: same as Player 1
Player3: plays the winner of 1/2: draw 74 or less, stand 75+.

I still fail to see, other than psychological tells, how order plays any effect. For the purpose of the problem, I'd like to suggest we assume three perfect logicians with no tells.

Player 1-2-3 know there are 3 contestants one must beat 2 others, the rationale for standing 66+ by any participant.
All contestants get a maximum of two chances, and all know this.

Given the chance to improve, the contestant must keep a 1 in 3 chance to do so.
The third contestant has to beat potentially 4 draws with a 5th and possibly 6th draw. Thus the rationale for 1 in 4 expectation.
This means Player3 rationalizes a 75 or better to get into the top 1/4.

My strategy differs from the Wiz's answer in that players are labled 1-2-3, and all know the order.
If no player knows the order of the draw, then I will defer to the Wiz's strategy.

Any contestant that draws 84 or better should "expect" to win?

Quote: Dween

In this lottery game, stopping on a number higher than 50 is the right strategy. While the average score of someone who stops at 50+ turns out to be ~62.5, there is no other number than can maximize the play. Stopping at 63+ garners an average of ~61.

Therefore, all players should stop on any number over 50.

My problem with this is for the first player, assuming all other players are playing the same strategy with two draws apiece.

If the first player draws 51 and decides to hold at 51 and all other players play the same strategy, then there are going to be 50 numbers that are lower than 51 available and the first player needs four consecutive draws that are 50 or less in order to win. The probability of such an occurrence is:

(50/99 * 49/98 * 48/97 * 47/96) = 0.06117879829220036

Therefore, if the first player draws 51 he has a 6.11787982922% chance of succeeding assuming that both other players adhere to the same strategy of stopping on anything higher than fifty, meanwhile, if he attempts another draw, he has a 49/99 = 0.494949494949495 or 49.4949494949% chance of ending up with something higher.

I would be inclined to stop when the probability of improvement is less than the probability of my number surviving, for both first and second position, and in third position, I would stop if there was less than a 50% chance that either player drew a number higher than mine.

For position one, I would say that the number would be 73, at that point, there is a 27.32963% chance that all players (using all draws) fail to draw a higher number, and only a 27% probability of improvement if the player takes another selection.

(72/99 * 71/98 * 70/97 * 69/96) = 0.2732962913375285

Actually, absent any tells, it stands to reason that the same number holds for Positions two and three.

Thats an interesting analysis Mission... I like it. Any time my chances to win => my chance to improve I should not improve.

As always, the Human side of the equation(s) differ from the math side. Humans gamble, math does not.

At the start of this discussion it was said that three players play in complete isolation .. and that used cards are put back (assumingly reshuffled) .. therefore each pick is a random number between 1-100 ... logically thinking it might be better to imagine the game with a 100 sided dice.

There is no advantage or disadvange of going first or last since you don't know the results of the others.

Oversimplification of this game would say standing at 50 essentially gives 4 coin flips to beat you if the others use the same strategy. Essentially 1 in 16. Might be less .. but but considering no one would stand at 49 then you definitely would need 4 competing rolls to win with a 50.


That all being said .. it's not that simple .. your aim is to beat statistical averages in order to win over 33.33% .. even taking it to 33.35% win percentage would be a success for this problem.

The other problem to this problem is figuring out what hold strategy the other 2 competitors are using in order to create your own probabilities. But if you're using the assumption they they are using the same "optimal" strategy that you are .. the the actual goal is simply to find that optimal hold number and keep your win% at 33.33% and not below because of poor strategy. So when you think about it that way .. a simple 1 in 3 win percentage is actually a success at this problem! ;)


I still feel the way to tackle this is to figure out the theoretical average winning score between the 2 other competitors (regardless of order or even if you draw first), and then figure out the best strategy to beat that number the optimal number of times (up to 33.33% if your assumption is that they use the same strategy as you .. "possibly" higher if you assume they are using a different strategy.


The irony is .. that even if you select/choose/calculate a number in the 60's, that your "choice" really only comes up 10-20% of the times you play the game .. because 80-90% of the you'll get 1 to 49 or ~65 to 100 .. both cases when you don't really have a choice! lol

Quote: Wizard

Quote: Dween

In this lottery game, stopping on a number higher than 50 is the right strategy.

So, you would stick at 51, despite having to face two opponents that get two chances each. Would you care to back that up with any math?

Here is my math.
Stopping at 51 gives the highest expected value of 63.
Stopping at 63 gives the expected value closest to stopping point, 62.28.
After reading a reply about a stop point being>=expected value, perhaps stopping at 63 is the best choice.

Stop at >=	Will Stop %	Redraw %	Stop value	Redraw Value	Expected Value
1	1	0	50.5	0	50.5
2	0.99	0.01	50.49	0.505	50.995
3	0.98	0.02	50.47	1.01	51.48
4	0.97	0.03	50.44	1.515	51.955
5	0.96	0.04	50.4	2.02	52.42
6	0.95	0.05	50.35	2.525	52.875
7	0.94	0.06	50.29	3.03	53.32
8	0.93	0.07	50.22	3.535	53.755
9	0.92	0.08	50.14	4.04	54.18
10	0.91	0.09	50.05	4.545	54.595
11	0.9	0.1	49.95	5.05	55
12	0.89	0.11	49.84	5.555	55.395
13	0.88	0.12	49.72	6.06	55.78
14	0.87	0.13	49.59	6.565	56.155
15	0.86	0.14	49.45	7.07	56.52
16	0.85	0.15	49.3	7.575	56.875
17	0.84	0.16	49.14	8.08	57.22
18	0.83	0.17	48.97	8.585	57.555
19	0.82	0.18	48.79	9.09	57.88
20	0.81	0.19	48.6	9.595	58.195
21	0.8	0.2	48.4	10.1	58.5
22	0.79	0.21	48.19	10.605	58.795
23	0.78	0.22	47.97	11.11	59.08
24	0.77	0.23	47.74	11.615	59.355
25	0.76	0.24	47.5	12.12	59.62
26	0.75	0.25	47.25	12.625	59.875
27	0.74	0.26	46.99	13.13	60.12
28	0.73	0.27	46.72	13.635	60.355
29	0.72	0.28	46.44	14.14	60.58
30	0.71	0.29	46.15	14.645	60.795
31	0.7	0.3	45.85	15.15	61
32	0.69	0.31	45.54	15.655	61.195
33	0.68	0.32	45.22	16.16	61.38
34	0.67	0.33	44.89	16.665	61.555
35	0.66	0.34	44.55	17.17	61.72
36	0.65	0.35	44.2	17.675	61.875
37	0.64	0.36	43.84	18.18	62.02
38	0.63	0.37	43.47	18.685	62.155
39	0.62	0.38	43.09	19.19	62.28
40	0.61	0.39	42.7	19.695	62.395
41	0.6	0.4	42.3	20.2	62.5
42	0.59	0.41	41.89	20.705	62.595
43	0.58	0.42	41.47	21.21	62.68
44	0.57	0.43	41.04	21.715	62.755
45	0.56	0.44	40.6	22.22	62.82
46	0.55	0.45	40.15	22.725	62.875
47	0.54	0.46	39.69	23.23	62.92
48	0.53	0.47	39.22	23.735	62.955
49	0.52	0.48	38.74	24.24	62.98
50	0.51	0.49	38.25	24.745	62.995
51	0.5	0.5	37.75	25.25	63
52	0.49	0.51	37.24	25.755	62.995
53	0.48	0.52	36.72	26.26	62.98
54	0.47	0.53	36.19	26.765	62.955
55	0.46	0.54	35.65	27.27	62.92
56	0.45	0.55	35.1	27.775	62.875
57	0.44	0.56	34.54	28.28	62.82
58	0.43	0.57	33.97	28.785	62.755
59	0.42	0.58	33.39	29.29	62.68
60	0.41	0.59	32.8	29.795	62.595
61	0.4	0.6	32.2	30.3	62.5
62	0.39	0.61	31.59	30.805	62.395
63	0.38	0.62	30.97	31.31	62.28
64	0.37	0.63	30.34	31.815	62.155
65	0.36	0.64	29.7	32.32	62.02
66	0.35	0.65	29.05	32.825	61.875
67	0.34	0.66	28.39	33.33	61.72
68	0.33	0.67	27.72	33.835	61.555
69	0.32	0.68	27.04	34.34	61.38
70	0.31	0.69	26.35	34.845	61.195
71	0.3	0.7	25.65	35.35	61
72	0.29	0.71	24.94	35.855	60.795
73	0.28	0.72	24.22	36.36	60.58
74	0.27	0.73	23.49	36.865	60.355
75	0.26	0.74	22.75	37.37	60.12
76	0.25	0.75	22	37.875	59.875
77	0.24	0.76	21.24	38.38	59.62
78	0.23	0.77	20.47	38.885	59.355
79	0.22	0.78	19.69	39.39	59.08
80	0.21	0.79	18.9	39.895	58.795
81	0.2	0.8	18.1	40.4	58.5
82	0.19	0.81	17.29	40.905	58.195
83	0.18	0.82	16.47	41.41	57.88
84	0.17	0.83	15.64	41.915	57.555
85	0.16	0.84	14.8	42.42	57.22
86	0.15	0.85	13.95	42.925	56.875
87	0.14	0.86	13.09	43.43	56.52
88	0.13	0.87	12.22	43.935	56.155
89	0.12	0.88	11.34	44.44	55.78
90	0.11	0.89	10.45	44.945	55.395
91	0.1	0.9	9.55	45.45	55
92	0.09	0.91	8.64	45.955	54.595
93	0.08	0.92	7.72	46.46	54.18
94	0.07	0.93	6.79	46.965	53.755
95	0.06	0.94	5.85	47.47	53.32
96	0.05	0.95	4.9	47.975	52.875
97	0.04	0.96	3.94	48.48	52.42
98	0.03	0.97	2.97	48.985	51.955
99	0.02	0.98	1.99	49.49	51.48
100	0.01	0.99	1	49.995	50.995

Quote: Dween

Quote: Wizard

Quote: Dween

In this lottery game, stopping on a number higher than 50 is the right strategy.

So, you would stick at 51, despite having to face two opponents that get two chances each. Would you care to back that up with any math?

Here is my math.

This math is looking in the wrong direction.

Imagine the game gets larger: there are 1 million contestants competing for a single large cash prize. Only the highest number wins. If it helps, imagine you are going last. Would you still stop at 51? No. Way. Only the person who draws 100 has any chance of winning this game.

Fact: The strategy depends on number of players, (but my multi-player game theory is too rusty to back up any of the calculations I've seen already, so I don't know the strategy exactly for 3 players).

Fact: Absent behavioural tells, order doesn't matter.

My answer is 87.

After your first pick, x, you should keep the number if 5 more draws (your second pick plus the other two contestants 2 picks each, regardless of whether you are drawing in first, second, or third position) have less than 50% probability of beating it.

The probability one of those 5 picks will not beat your number is x / 100. The probability of all 5 of those picks not beating your number is (x/100)^5.

(x/100)^5 = .5
x^5 = 5,000,000,000
x = 87.055

You should keep your number at 87 or higher and redraw lower than 87. Round down, since an initial draw of 87 will leave 49.84% chance of being beaten, with 50.16% chance of not being beaten.

The general form, where n is number of players, would be
(x/100)^(2n-1) = .5

For 1 player, x = 50 (ludicrous example, but shows the formula works)
For 2 players, x = 79.370
For 100 players, x = 99.652
For 500 players, x = 99.93
For 5000 players, x = 99.986

The one thing I can't make sense of is, as dwheatley pointed out, with one million players you would redraw on anything but 100. But x will come out to 99.999 and be rounded down to 99.

Edit: Actually, for 1 player, you would want to stay on 51.. hmm...

I've been working on the three-player case and in doing so I think I found an error in my two player case, which I just fixed.

In the case where the players are given numbers from a continuous distribution from 0 to 100, I claim the answer in the three player case is the solution to the equation 2x^4 + x^3 - x^2 + x - 1 =0, which comes to approximately 0.69115. Extending that to the game with 100 cards numbered 1 to 100, my strategy would be to switch with 69 or less and stand on 70 or more.

For the two player case my strategy would be to switch on 63 or less and stand on 64 or more.

But wouldn't the math you need only be based on a 2 player game? All you need to do is beat the (theoretical win of the game between the two other players) .. so add 1 to that number and you're good and groovy to win the targeted 33.33% (or more if others use less optimal strategy).

I'd think doing the math and finding the theoretical average win for 3 players is actually what you'd need if you were a 4th player?

Quote: Wizard

... I think I found an error ....

What was the previous error Wizard?

If there were three other players, would the lowest "stand" number be ~80?

I had fun with a spreadsheet. If all players stop with 70 or more:

Outcome	Ways	Probability	Pays	Return
Win	316329017600	0.326011897	1	0.326011897
2 Way Tie	14095507200	0.01452697282	0.5	0.00726348641
3 way Tie	168686400	0.0001738499164	0.3333333333	0.00005794997212
Lose	639705788800	0.6592872803	0	0
Total	970299000000	1		0.3333333333

You stop at 70, the other 2 stop at 69:

Outcome	Ways	Probability	Pays	Return
Win	316409209400	0.3260945434	1	0.3260945434
2 Way Tie	14067107600	0.0144977039	0.5	0.007248851952
3 way Tie	167899500	0.0001730389292	0.3333333333	0.00005767964308
Lose	639654783500	0.6592347137	0	0
Total	970299000000	1		0.333401075

You stop at 70,the other 2 stop at 71:

Outcome	Ways	Probability	Pays	Return
Win	316425185400	0.3261110085	1	0.3261110085
2 Way Tie	14031882000	0.01446140004	0.5	0.007230700021
3 way Tie	167085900	0.0001722004248	0.3333333333	0.00005740014161
Lose	639674846700	0.6592553911	0	0
Total	970299000000	1		0.3333991086

Quote: Ayecarumba

What was the previous error Wizard?

If there were three other players, would the lowest "stand" number be ~80?

I am away from home so don't have my original notes with me so don't know the mistake. I think a calculus error somewhere.

I don't know about more than three players. As each player is added the problem gets more complicated by a factor of two, at least.

I hope to write up a solution later this week.

Quote: miplet

I had fun ...

Thanks Miplet! Goes to show that if my strategy is to stop on 70 then it can't be defeated by the other two players, at least assuming they both have the same strategy.

Did both Wizard and kubikulann arrive at the same correct answer via two totally different methods?

Quote: Wizard

I've been working on the three-player case and in doing so I think I found an error in my two player case, which I just fixed.

In the case where the players are given numbers from a continuous distribution from 0 to 100, I claim the answer in the three player case is the solution to the equation 2x^4 + x^3 - x^2 + x - 1 =0, which comes to approximately 0.69115. Extending that to the game with 100 cards numbered 1 to 100, my strategy would be to switch with 69 or less and stand on 70 or more.

For the two player case my strategy would be to switch on 63 or less and stand on 64 or more.

Quote: kubikulann

Here is the solution for the 1-100 game.

Let X be the number up to which players redraw (and they stand with a value > X). Let x be X/100 (i.e. the percentage value).
Let k be the value of the final card obtained. Let f(k|X) be the probability distribution of k given strategy X. Let F(k|X) be the cumulative.

f(k|X) = x/100 ...if k=1 to X
(1+x)/100 ... if k>X

F(k|X) = (x/100) k ...if k=1 to X
( (1+x)/100 )k - x ...if k>X

The probability that both opponents are lower or equal to your value k is F²(k|X).
(I assume that you win in case of a tie. Adapt to F²(k-1|X) if a tie is a loss.)

Let Y be the optimal strategy number, given that the opponents use X. You are trying to maximize the expected F²:

SUM { f(k|Y)F²(k|X) }
= SUM_{1 to Y} { (y/100) F² } + SUM_{Y+1 to 100} { ((1+y)/100) F² }
= (y/100) SUM_{1 to 100} { F² } + (1/100) SUM_{Y+1 to 100} { F² }

Maximizing means finding Y such that the difference from Y-1 to Y is positive and the difference from Y to Y+1 is negative.
Those differences are

(1/100)² SUM_{1 to 100} { F² } - (1/100) F²(Y|X) > 0
and
(1/100)² SUM_{1 to 100} { F² } - (1/100) F²(Y+1|X) < 0

In other words, your Y should be the card value whose F² is the average of all F².
Expanding
SUM_{1 to 100} { F² } = SUM_{1 to X} { (kx/100)² } + SUM_{X+1 to 100} { (k(1+x)/100 - x)² }
yields a 4th-power polynomial in X.

The optimal Y|X is hard to express in a formula.
But we don't bother, since we know that in the equilibrium Y(X*) is equal to X*. So we simply have to solve a polynomial

Equation

-2x⁴ -x³ +0.99995x² -0.99995x +1.01505 = 0
Note the small x's (= X/100)

whose solution is X* = 69,3
(unless I made a calculation mistake).

So the Nash equilibrium is to redraw if you get 1 to 69, and stand with your card on a value of 70 to 100.

Thanks, sodawater.

I was wondering if everybody here had blocked me, or simply they don't read the thread before entering their part.

I am presently busy computing the solution of the game where there is no replacement (a card drawn can never be drawn again) and players know what their predecessors did (stand or redraw). Damn hard! Even with as simple a game as with only six cards numbered 1 to 6, it is taking lots of my time.

Definitely, the threshhold for redrawing increases with the rank.

This is no gratuitous fun.
This game has similarities with traditional poker, where each player in turn may change cards.

Here is my solution to the problem. Questions, comments, or corrections?

Quote: Wizard

Here is my solution to the problem. Questions, comments, or corrections?

Fine! I had a slightly different approach but got the same result. (Contrary to the mistaken .46 I posted earlier).

Now, the solution for a continuum [0,1] is an approximation for discrete games with many cards, but does 100 qualify as "many"? It happens to be the case, as I proved here.

Equation in continuous:
2x4 + x3 - x2 + x - 1= 0
Solution .69115
Equation in discrete 100:
-2x4 -x3 +0.99995x2 -0.99995x +1.01505 = 0
Solution .6952

It is to be expected that with fewer cards, the equation changes further and the solution may end up different.

Quote: Wizard

Here is my solution to the problem. Questions, comments, or corrections?

Note that the replacement in the game is not exactly random. It is fairly simple for a player to avoid picking the same card twice, since it is put back in the same position on a small matrix.

I don't think this changes the analysis.

Quote: Ayecarumba

Quote: Wizard

Here is my solution to the problem. Questions, comments, or corrections?

Note that the replacement in the game is not exactly random. It is fairly simple for a player to avoid picking the same card twice, since it is put back in the same position on a small matrix.

I assume they reshuffle the cards if the player chooses to switch. They probably cut that part out of the show. Otherwise, why bother putting it back?

Quote: Wizard

Quote: Ayecarumba

Quote: Wizard

Here is my solution to the problem. Questions, comments, or corrections?

Note that the replacement in the game is not exactly random. It is fairly simple for a player to avoid picking the same card twice, since it is put back in the same position on a small matrix.

I assume they reshuffle the cards if the player chooses to switch. They probably cut that part out of the show. Otherwise, why bother putting it back?

It is possible for someone to get confused and pick it again. The rack is like a spinning display of sunglasses with the same number of items, arranged in rows on each of face. As long as you can remember that you previously picked the second one from the right in the second row, the first time, then change at least one of those parameters the second time, it appears that you will get a different card.