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

51–60 of 88 posts

Re: Choose the smallest number not chosen yet

#51

Post by lisper »

alexmolas wrote: post #49
lisper wrote: post #37

I must be missing something here. > if we follow this strategy we’ll win a little bit less than one-third of the time. That is not possible. If N players use the same strategy then by symmetry each of them must win on average 1 time in N. So against two other players we should win exactly one third of the time, not "a little bit less" than one third of the time. Also, if all players use the same strategy then it does…

> If N players use the same strategy then by symmetry each of them must win on average 1 time in N. The point here is that there's an option of tying, if all players choose the same number. So P_1_win + P_2_win + P_3_win + P_tie = 1, means P_i_win > Also, if all players use the same strategy then it doesn't matter what the strategy actually is. The only requirement is that it have some probabilistic element, otherwis…

Ah. I didn't realize that ties were counted as non-wins. I thought ties would just be ignored.

Re: Choose the smallest number not chosen yet

#52

Post by alexmolas »

wikfwikf wrote: post #47
planede wrote: post #26

What's super surprising if that I'm "dumb" and I play against two "smart" players then I can't have a bad strategy. Assuming that the "smart" players play the Nash-equilibrium mixed strategy then whatever strategy I execute, I have the same chance of winning.

This is obviously wrong. If you choose one million billion trillion every time you will not win 28% of the time.

but still (1) there's some probability of both players choosing a number bigger than one million billion trillion, and (2) there's some probability of both other players choosing the same number. Actually, the probability that the other both players choose 1 is pretty big (~0.21). So even if you choose a super-big number, there's a big probability of you still winning.

Re: Choose the smallest number not chosen yet

#53

Post by alexmolas »

aimor wrote: post #45
layer8 wrote: post #33

Earlier quoted context omitted.

The links are dark blue with a very light grey underline. A bit hard to see, I agree, but not indistinguishable.

Not on my machine in Firefox 104. For me the links aren't styled until the mouse hovers over them.

that's weird, on my Firefox the links are styled always. Do you have any idea why this can happen?

Re: Choose the smallest number not chosen yet

#55

Post by RcouF1uZ4gsC »

> To start, assume that the other two players use the equilibrium probabilities P

If we can assign strategies (but no coordination) to other players, then how about having every player generate a uniform random 64-bit number.

Given the low chances of collision with this setup, this will result in a 1/3 chance of winning which is higher than the 0.296 chance given in the article.

Re: Choose the smallest number not chosen yet

#56

Post by HWR_14 »

StevenWaterman wrote: post #46
ZetaZero wrote: post #43

Earlier quoted context omitted.

picking 1 would still dominate over any other strategy, in a head-to-head. However, if you are trying to maximize your H2H score against a pool of contestants, a cooperation strategy, where you both alternated taking the lower number would be close to optimal.

For a short intuitive proof of that 1st sentence, imagine both players pick 1 every time. You both lose 1 point. If you're tied for score, you're still tied after the round. Now imagine you change your number to stop ties. Well now you've picked a number bigger than 1, and you lose every time. If you were tied, now you're losing.

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.

Re: Choose the smallest number not chosen yet

#57

Post by andrewla »

ZetaZero wrote: post #41
lisper wrote: post #37

I must be missing something here. > if we follow this strategy we’ll win a little bit less than one-third of the time. That is not possible. If N players use the same strategy then by symmetry each of them must win on average 1 time in N. So against two other players we should win exactly one third of the time, not "a little bit less" than one third of the time. Also, if all players use the same strategy then it does…

I believe this strategy will work against any other strategy, not just mirror strategy. Of course, against mirror strat, 1/N is correct.

It seems like there are pathological counterexamples. If you're player three, and player one chooses 1 always, and player two chooses 2 always, then the player using this strategy can never win.

Player 2 wins with probability .45 (only wins when player 1 gets "knocked out"), and player 1 with probability 1-.45, and player 3 never wins.

Re: Choose the smallest number not chosen yet

#58

Post by LodeOfCode »

RcouF1uZ4gsC wrote: post #55

> To start, assume that the other two players use the equilibrium probabilities P If we can assign strategies (but no coordination) to other players, then how about having every player generate a uniform random 64-bit number. Given the low chances of collision with this setup, this will result in a 1/3 chance of winning which is higher than the 0.296 chance given in the article.

Because then defecting is optimal: if the other players follow through, you win ~100% of the time by picking 1.

The point of the equilibrium is that even if your respective strategies are public knowledge, nobody can benefit from changing theirs

Re: Choose the smallest number not chosen yet

#59

Post by seanw265 »

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 distribution, the percentages change significantly.

*Example:*

Agent 1 (nash distribution): .296

Agent 2 (nash distribution): .296

Agent 3 (nash distribution): .296

*However:*

Agent 1 (always chooses 1): .296

Agent 2 (nash distribution): .248

Agent 3 (nash distribution): .248

My results indicate that the nash strategy is not optimal in an environment where agents can choose their own strategy.

What did I miss?

Re: Choose the smallest number not chosen yet

#60

Post by aimor »

alexmolas wrote: post #53
aimor wrote: post #45

Earlier quoted context omitted.

Not on my machine in Firefox 104. For me the links aren't styled until the mouse hovers over them.

that's weird, on my Firefox the links are styled always. Do you have any idea why this can happen?

Not sure, could be something on my end. But --link-color and --link-underline-color are "not set", so maybe sass related.
Post reply on HN