The Greater Than Game is a playable adaptation of
Always Greater. The rules of the Greater Than Game are as follows:
Players
- At least two players are needed to play, plus one more person acting as an impartial moderator.
Gameplay
- A game consists of a series of rounds described as follows:
- The moderator announces an integer N and then secretly chooses a random integer R in the range 1 to N. The value of N should be much greater than the number of players.
- The first player then calls out an integer in the range 1 to N. In subsequent turns, the players alternate calling integers greater than the previously called integer but not more than N.
- The round ends when one player calls an integer which is greater than or equal to R, at which point the moderator will announce the player has 'busted', meaning he has matched or exceeded R and lost the round.
Scoring
- When a player busts, he loses points equal to the amount he went over R, if he said exactly R then there is no penalty.
- Each other player scores the difference between their last call and the call before that. If a player has not made any calls, then he scores 0.
Example game 1
Three players A, B, C. N=20, R=18
A:8, B:12, C:15, A:17, B:19=busted
A scores 17-15=2, B penalized 19-18=1, C scores 15-12=3
Example game 2
Three players A, B, C. N=20, R=7
A:4, B:7=busted
A scores 4-0=4, B penalized 7-7=0, C scores 0
What is a player's best strategy if he wants to simply avoid busting?
What is a player's best strategy if he wants to maximize his expected points for a round?
I just found this interesting problem, 11 years late.
If all of the other players are also trying to maximize their points, then you want to pick a number which exhausts fraction p of the remaining numbers. For instance, if the N = 1000 and the last number picked was 200, then there are 800 numbers remaining. If the optimal p = 25%, then pick 200 + 25%*800 = 400.
And what is p? After doing some work, I find that the best strategy to maximize your points depends on how many players there are in total.
You want to maximize expected gain - expected loss due to the immediate pick. Let R = number of numbers remaining and n = number of total players. The probability of busting on this turn is p. The probability of not busting is (1-p).
The expected loss = (1/2 the numbers exhausted)*(probability of busting) = (Rp/2)*p
The potential gain is Rp (the numbers exhausted), but you only gain this if (a) you do not bust and (b) one of the remaining (n-1) players does bust on their next turn. Algother, this makes the expected gain Rp*(1-p)*(1-(1-p)^(n-1)).
The expected gain - expected loss, which we want to maximize is Rp*[(1-p)*(1-(1-p)^(n-1)) - p/2].
Clearly, this does not depend on R, but it does depend on n. I have done some exploration with Excel, and find as follows.
When n = 2, exhaust 1/3 = 33.333% of the remaining numbers.
When n = 3, be bold and exhaust 40.693% of the remaining numbers
When n = 4, be less bold and exhaust 40.53% of the remaining numbers
When n = 5, exhaust 39.457% of the remaining numbers
...
When n = 10, exhaust 32.252% of the remaining numbers
...
When n is infinite, one of the later players is guaranteed to bust.
Maximize p*((1-p) - p/2).
p = 1/3 = 33.333%
I am not quite sure why one gets bolder and then more cautious and then more bold and then more cautious. Probably I have made a small mistake, but I am confident that I am close to the best strategy.
Edited on August 19, 2018, 8:06 pm
Part B (spoiler?)
