Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Choose the smallest number not chosen yet

amolas.dev

Post reply on HN
Print view View original

71–80 of 88 posts

Re: Choose the smallest number not chosen yet

#71

Post by riversflow »

seanw265 wrote: post #66
seanw265 wrote: post #59

There must be something I'm missing. I borrowed the author's choice probabilities and wrote a script to verify the probability of winning by simulating 10 million rounds of gameplay. It seems it's true that when all three agents are following the same choice probability distribution the result is a win about 29.6% of the time. However, when one of those three agents follows an alternative choice probability distribut…

Diving into this further, I've found another situation that appears to interfere even more. Our baseline (once again): Agent 1 (nash distribution): .296 Agent 2 (nash distribution): .296 Agent 3 (nash distribution): .296 Another case: Agent 1 (always chooses 1): .489 Agent 2 (even distribution -- equal chance of any number 1-10 being chosen): .411 Agent 3 (nash distribution): .054 In this situation, the nash strategy…

> I fail to understand how this can be considered an optimal strategy.

Aye, I mean it doesn't even pass the sniff test to me.

If all actors are a) informed of the number of participants and b) are trying to win in earnest, I can not understand why a rational actor would ever pick a number larger than the number of participants. It seems an obviously bad strategy that's an artifact of infinite calculus.

Really though, I think using tools made for real numbers are a bad fit for a problem firmly bounded to natural numbers. I haven't formally studied game theory, but it's my impression this is the exact type of problem it's designed for, and discrete games are a significantly studied subject.

My intuition is there is no reason to ever pick a number greater than participants-1. I feel weird saying that, because everyone, you included, keeps bounding on 1-10 and not 1-n, and I don't have a lot of the formal math training that is fairly ubiquitous here, especially in this thread I would assume. I'd be interested to see the way the distributions play out when one of the Agents randomly select 1 or 2, might have to code this up, but I'm trying to resist the urge to jump down a rabbit hole. I definitely think that "everyone is using the same strategy" is a special case of the question, not a generalized solution.

My thinking is: in any case where you would pick 3+, why wouldn't you pick 1 or 2?

Re: Choose the smallest number not chosen yet

#73

Post by seanw265 »

yifanl wrote: post #68
seanw265 wrote: post #59

There must be something I'm missing. I borrowed the author's choice probabilities and wrote a script to verify the probability of winning by simulating 10 million rounds of gameplay. It seems it's true that when all three agents are following the same choice probability distribution the result is a win about 29.6% of the time. However, when one of those three agents follows an alternative choice probability distribut…

The nash equilibrium is defined by a strategy that cannot be improved by changing your own strategy, assuming the other players' strategies stay the same. Agent 1 doesn't care if Agent 2 and 3 win less than him, he only feels a strategy is better than the Nash strategy if his expected score becomes higher than .296, which your simulation seems to show has not been achieved.

Please see my follow-up comment with another simulation that shows how the expected score can rise well above .296.

https://news.ycombinator.com/item?id=33025759

Re: Choose the smallest number not chosen yet

#74

Post by yifanl »

seanw265 wrote: post #73
yifanl wrote: post #68

Earlier quoted context omitted.

The nash equilibrium is defined by a strategy that cannot be improved by changing your own strategy, assuming the other players' strategies stay the same. Agent 1 doesn't care if Agent 2 and 3 win less than him, he only feels a strategy is better than the Nash strategy if his expected score becomes higher than .296, which your simulation seems to show has not been achieved.

Please see my follow-up comment with another simulation that shows how the expected score can rise well above .296. https://news.ycombinator.com/item?id=33025759

I don't believe cases where changing your strategy in a non-equilibrium state are considered, as the assumption that no other player will shift their own strategy will not hold.

Otherwise, you might as well consider the case P1 always chooses 1, P2 always chooses 1 and P3 always chooses 2.

Re: Choose the smallest number not chosen yet

#75

Post by rawling »

riversflow wrote: post #71
seanw265 wrote: post #66

Earlier quoted context omitted.

Diving into this further, I've found another situation that appears to interfere even more. Our baseline (once again): Agent 1 (nash distribution): .296 Agent 2 (nash distribution): .296 Agent 3 (nash distribution): .296 Another case: Agent 1 (always chooses 1): .489 Agent 2 (even distribution -- equal chance of any number 1-10 being chosen): .411 Agent 3 (nash distribution): .054 In this situation, the nash strategy…

> I fail to understand how this can be considered an optimal strategy. Aye, I mean it doesn't even pass the sniff test to me. If all actors are a) informed of the number of participants and b) are trying to win in earnest, I can not understand why a rational actor would ever pick a number larger than the number of participants. It seems an obviously bad strategy that's an artifact of infinite calculus. Really though,…

> I can not understand why a rational actor would ever pick a number larger than the number of participants.

If there are two of you and you're both always picking 1 or 2, you're going to both lose half the time when you collide. You'll win 1/4 of the time.

If you instead pick from 1-3 you're only going to collide 1/3 of the time, and you'll win 1/3 of the time.

1-4, 1/4 collision, 3/8 win rate.

(I think I've got the maths right, based on picking numbers uniformly.)

If you accept this is logical but decide to actually only ever pick 1 or 2, your logical opponent will surely decide the same and you'll both be worse off.

Re: Choose the smallest number not chosen yet

#76

Post by credulousperson »

seanw265 wrote: post #66
seanw265 wrote: post #59

There must be something I'm missing. I borrowed the author's choice probabilities and wrote a script to verify the probability of winning by simulating 10 million rounds of gameplay. It seems it's true that when all three agents are following the same choice probability distribution the result is a win about 29.6% of the time. However, when one of those three agents follows an alternative choice probability distribut…

Diving into this further, I've found another situation that appears to interfere even more. Our baseline (once again): Agent 1 (nash distribution): .296 Agent 2 (nash distribution): .296 Agent 3 (nash distribution): .296 Another case: Agent 1 (always chooses 1): .489 Agent 2 (even distribution -- equal chance of any number 1-10 being chosen): .411 Agent 3 (nash distribution): .054 In this situation, the nash strategy…

Indeed the Nash equilibrium is not always what we would like to call "optimal", especially in games with more than two players.

As you notice, it is possible the Nash equilibrium strategy will be crushed if more than one agent chooses a different strategy (i.e. a situation where players are deviating from a strategy in a non-unilateral fashion). If Agent 1 and Agent 2 work collude beforehand they can completely crush Agent 3. The Nash equilibrium only says the agent will lose more if they change while the others use the follow the same strategy (i.e. a unilateral deviation).

In defense of the Nash equilibrium, there are some reasons we can sort of assume that the two players will pick a strategy which happen work together to beat us by a lot. For example, one of the two other players could just play the Nash strategy along with us, in which case we know the other player will not be able to exceed the equilibrium value. There is no way the player can pick a strategy all by themselves which is guaranteed to win more than the equilibrium value. For the other players to actually have a guaranteed higher probability of winning, they must coordinate playing their strategy with the other player and trust that the other player will keep their word. This is known as forming a coalition.

There are some other notions of equilibrium which take this into account and do not permit coalitions to change the value (see: strong Nash equilibrium), but it won't exist for many games (like this one).

Re: Choose the smallest number not chosen yet

#77

Post by HWR_14 »

theptip wrote: post #67
HWR_14 wrote: post #56

Earlier quoted context omitted.

This is only true if your goal is to have a score higher than your opponent. It's not true if your goal is to have the highest possible score. If ties are with 0, you always choose 1 in either situation. If ties are worth -1, choosing 1 always achieves a greater than or equal to score but the number will be much lower than if you some percentage of the time choose another number.

> This is only true if your goal is to have a score higher than your opponent That is what “dominant” in game theory means, which was the specific claim that’s being discussed.

No you are incorrect in what a "dominant" strategy means. It has nothing to do with dominating your opponent.

Re: Choose the smallest number not chosen yet

#78

Post by civilized »

seanw265 wrote: post #66
seanw265 wrote: post #59

There must be something I'm missing. I borrowed the author's choice probabilities and wrote a script to verify the probability of winning by simulating 10 million rounds of gameplay. It seems it's true that when all three agents are following the same choice probability distribution the result is a win about 29.6% of the time. However, when one of those three agents follows an alternative choice probability distribut…

Diving into this further, I've found another situation that appears to interfere even more. Our baseline (once again): Agent 1 (nash distribution): .296 Agent 2 (nash distribution): .296 Agent 3 (nash distribution): .296 Another case: Agent 1 (always chooses 1): .489 Agent 2 (even distribution -- equal chance of any number 1-10 being chosen): .411 Agent 3 (nash distribution): .054 In this situation, the nash strategy…

The Nash equilibrium strategy is optimal when the other players are also playing optimally.

If your opponents never choose 1, you can choose 1 and win 100% of the time. But if your opponents are very smart, know your strategy, and will exploit any weakness your strategy presents, it's best to play the Nash equilibrium strategy.

Re: Choose the smallest number not chosen yet

#80

Post by tomerv »

jetrink wrote: post #25
tromp wrote: post #10

Earlier quoted context omitted.

Yes, the only case in which there's no winner is if all 3 pick the same number. Which is why the author skips the case of two players. Because then picking 1 always is a dominating strategy in which neither player wins.

I wonder what would happen to the two player game if the rewards were set up so that win=1, lose=0, tie=-1? It would be interesting to see how the strategy changed as the penalty for tying is increased.

All the other answers in the thread focus on maximizing head-to-head score. I'll try to answer the question for the goal of greedily maximizing your own score.

Using the same definitions from the article, we now have (for a 2 person game):

  Q_i = -P_i + (1 - sum_{j=1..i}(P_j))
Where the first term is for the case of choosing the same number as your opponent, and the second when it's larger than your opponent.

Now solve the same set of equations, but with our new Q_i. Solving Q_1 = Q_2 analytically is easy, then Q_2 = Q_3 and so on... You get P = (1/2, 1/4, 1/8, ...)

So that's the result for this specific 2-player game. You could also ask about the 2-player game with tie=t for any negative t (the above is for t=-1). Now we get

  Q_i = t*P_i + (1 - sum(P_j))
Again, solving Q_i=Q_{i+1} is easy and gives

  P_{i+1} = (t / (t-1)) * P_i
For example, if t=-2 then (using the fact that all P_i's sum to 1): P = (1/3, 2/9, 3/27, ...)

I did not try to tackle the 3-player game with tie=t.

Post reply on HN