Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Elephant Parade]

Lmao

[Crystalizedmire]

"If 1 is the lowest number then everybody is choosing 1, but if everyone is choosing 1 nobody is choosing 1..."

[ToonyMan]

I can't believe no one picked 2.

This is kind of like the first part of Liar Game.

[Quarque]

So what is the optimal strategy for this game?
If everyone else plays a similar suboptimal strategy (as it happened), you can exploit this with a counterstrategy.

But there is an "optimal" strategy that you can't counter if everyone else plays it (the technical term for this is "mixed Nash equilibrium").

After an evening of filling a massive excel sheet and crunching numbers, here is the optimal strategy for this game with 9 players. You play a number from 1 to 5* randomly, with the die weighted according to the following pie chart:



* I ignored numbers above 5, because 5 wins when the other players have played 1 1 2 2 3 3 4 4. If the other players submitted higher numbers, you can either win with a number below 5, or you always lose no matter what number you submit.

[EuchreJack]

Ah, but what if MY random number generator goes 1 thru 4? Would I not then have a superior chance of winning? 

[Quarque]

nope

If everyone else follows the "optimal" strategy, you will have the same chance of winning as the rest if you pick any number from one to five.

A lower number takes precedence, but will collide more often.
A higher number collides less often, but risks being beaten.
Those two factors cancel each other out with this distribution, so you can't outsmart it.

@NJW2000 Where did you find this game, or did you come up with it yourself?

[NJW2000]

I saw it at a talk about stuff like Nash equilibria, used to get people excited about the topic. This was a while ago, it was a younger audience.

I’d be interested in how you worked out the optimal strategy, I don’t know much about calculating that kind of thing.

[Quarque]

The trick is to calculate: "what strategy X makes all of your choices equivalent if the other 8 players play X?"

Step 1: I assumed that the optimal strategy is a random pick between numbers 1 to 5, as I motivated above. (In hindsight it was perhaps not entirely correct, maybe a strategy with a small chance to pick 6 is slightly better, but the outcome I got should still be pretty close.)
So every candidate strategy is a list of 5 probabilities p1 .. p5 to pick the number 1 .. 5.

Step 2: I used excel to calculate your expected probability of winning the game with a given number N, given that the other 8 players picked their numbers with p1 .. p5.
As to how:
Step 2A: I listed all of the possible results of players 1 to 8 in an excel sheet. Five columns for the numbers of players that picked 1 to 5. So for example one possible result is 3 | 0 | 3 | 2 | 0. However, I omitted the results where you can never win, for example when exactly 1 other player picked 1. Those results are irrelevant because your number doesn't matter.
Step 2B: I calculated the odds of each result, given the probabilities p1 .. p5.
(This is easier than it may sound, you can use the formula p1^k1 * p2^k2 * p3^k3 * p4^k4 * p5^k5 * 8! / (k1! * k2! * k3! * k4! * k5!), where k1 .. k5 are the numbers of other players playing 1 to 5)
Step 2C: For each number that you pick, I checked for which results it is winning and added up the probabilities.

Step 3: now play with the probabilities p1 .. p5 until the expected probability of winning is about equal for each number you can play

link to sheet

[webadict]

The optimal max number to pick is the ceiling(number of players /2).  The reason is that players can be maximally pair to that number of choices.

Basically, look at 2 players:  Always picking 1 wins every time it doesn't tie.  You never pick 2 because the other player can't tie if you don't pick 1.

Look at 3 players.  You should pick 1 or 2 because picking 3 never wins where picking 1 or 2 didnt.  It only loses when there isn't a tie, which is 50% of the time.

Keep this going: 4 players, you pick 1 or 2.  Picking 3 only wins when all other players tie at 1 or 2, 25% of the time, but always loses the other 75% of the time.  Conversely, you have a chance to tie from that 75% (equal to 37.5% or 50% of those losses.)

In this case, with 9 players, you should always pick 1 to 5.

[Quarque]

I thought exactly that, too. But it's wrong. To see why, the three player game is a good example. If the other two players play a 50/50 roll to pick 1 or 2, then picking 3 wins half the time. That's more than 33%, so it beats the strategy.

But it gets crazier, the real optimal strategy has a smallchance to pick any number!

proof: if the other players never pick a number greater than N, you get better odds of winning than they do if you follow a strategy that is identical to theirs, except that you pick N+1 whenever they would pick N. Because N+1 wins when N would win, but it also wins when two other players play N.

[webadict]

Hm, doing a bit of math, I think you're right, but with a caveat that if you pick a higher maximum number than someone else, you typically have better odds (just by virtue of having less ties).  So, assuming then that a theoretical optimal maximum is unbounded, your distribution is probably some type of Chi-square, depending on the number of players.