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

41–50 of 88 posts

Re: Choose the smallest number not chosen yet

#41

Post by ZetaZero »

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.

Re: Choose the smallest number not chosen yet

#42

Post by jasonjayr »

alexmolas wrote: post #17
izietto wrote: post #16

Earlier quoted context omitted.

> What does it mean to put a scheme in a cname? It means that https:// shouldn't be mentioned in the DSN records > How can I solve the problem? You should edit your DNS records and remove it

thank you! I just did it, let me know if now it works :)

Also confirmed working for me :) Thanks, and good luck!

Re: Choose the smallest number not chosen yet

#43

Post by ZetaZero »

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.

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.

Re: Choose the smallest number not chosen yet

#45

Post by aimor »

layer8 wrote: post #33
MauranKilom wrote: post #29

I read past four links in the text before it became clear that hyperlinks are visually indistinguishable from the rest of the text on this site. Who does this?

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.

Re: Choose the smallest number not chosen yet

#46

Post by StevenWaterman »

ZetaZero wrote: post #43
jetrink wrote: post #25

Earlier quoted context omitted.

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.

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.

Re: Choose the smallest number not chosen yet

#47

Post by wikfwikf »

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.

Re: Choose the smallest number not chosen yet

#48

Post by planede »

Got the closed-form solution:

P_i = a^i (1/a - 1)

where a is the real-valued solution of a^3 + a^2 + a - 1 = 0 .

a = 1/3 (-1 - 2/(17 + 3 sqrt(33))^(1/3) + (17 + 3 sqrt(33))^(1/3))

edit:

The probability to win comes out as a^2 ~= 0.2955977425220847709809965928515386138989754484466083115379546015...

edit2:

To arrive to this solution I expressed the equations in terms of R_i = P(choosing a number larger than i), then substitute P_i = R_{i-1} - R_i . This gets rid of the sums when you evaluate Q_{j+1} - Q_j , and arrives at R_{j+1}^2 = R_{j-1}(2 R_j - R_{j-1}). We know that R_0 = 1, and lim R_i = 0. I just tried R_i = a^i, and it works, with the value of "a" calculated above.

edit3:

To name names: the solution is a geometric distribution [1]

What I ended up reducing the algebra problem to is a homogeneous recurrence relation, albeit non-linear. As it has constant coefficients, a^i is the obvious candidate to test it with.

I got successfully nerd-sniped, this is a fun problem. Next time with 4 players...

[1] https://en.wikipedia.org/wiki/Geometric_distribution

Re: Choose the smallest number not chosen yet

#49

Post by alexmolas »

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, otherwise all players would choose the same number every time.

A player choose its next move using some probabilities P, ie: it's going to choose randomly number 1 the 45% of times, 2 the 25% of times, etc. So there's a random element in the game, which makes players following the same strategy to not choose the same numbers every time.

Re: Choose the smallest number not chosen yet

#50

Post by planede »

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.

You will, your opponents will choose matching numbers 28% of the time if they use the Nash-equilibrium mixed strategy.
Post reply on HN