Choose the smallest number not chosen yet | Hacker News Reader

Choose the smallest number not chosen yet

amolas.dev

88 pointsalexmolas80 comments

Open articleView on HN

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

This is used as a model for "reverse auctions" [1], which also then charges a fee for participation which essentially makes the whole thing a cross between a lottery and a scam.

There were loads advertised on TV with misleading claims about people winning ipods for 37p, etc, which while technically might be true for the winner ignores the overall cost.

I've not seen many advertised lately so either the practice itself or the advertising of it was cracked down on.

[1] https://www.gamblingcommission.gov.uk/public-and-players/gui...

Iirc the FTC sat on them pretty damn hard.

i thought these reverse auctions are more similar to penny auctions!

Interesting problem and I appreciate the author bringing it to our attention. That said, I have to admit I found the Math Overflow post he took the solution from much clearer: https://math.stackexchange.com/a/80743/

For one thing, the Math Overflow post is correct, whereas the blog post states a crucial inequality in the wrong direction. This confuses the whole argument, since the surrounding text isn't clear enough for the reader to easily self-correct the typo.

The other factor is the flow of the exposition. For example, the blog post attempts to define Q before using it, but the definition is too vague and ends up being less useful than the "define in the course of the argument" approach used in the Math Overflow post.

hi! thanks for your comment. which inequality is the wrong direction?

> Since we’re looking for the Nash equilibrium we’ve Q_i >= Q_P, this is, the best winning strategy you have is to follow the strategy P.

oh shoot, you're completely right! changing it right now, thanks for spotting it ;)

If you have no played it, try this game with some friends. It's surprisingly fun.

> To simplify the problem, let’s start with the simple scenario where you are competing against two other persons.

> P(wining)~=0.296

Where does the other 11.2% go? Is the probability of a triple tie? Perhaps you can add it to the article.

I'll play it next time I see them :)

Now I'm wondering which is the best strategy you can follow if the other players follow an unknown non-optimal strategy (like selecting 1,2 or 3 with p=1/3). Maybe it's a good scenario to try some reinforcement learning

There is a nice strategy that is playing always 1, and claiming it.

Everyone else should not play 1 because otherwise they would not win. But if no one else plays 1, you win. So they must take turns to lose and make you lose. It's a good strategy to not meet them again ever :)

The other players then always pick 1 and 2, making the latter the winner, and you always the loser.

But in this case you lose no matter what strategy you use; you only get to decide which of the other players wins. That's why the article analyses the case where the other players use the same strategy.

It's more fun with more players. They can discuss who is going to lose the round because of choosing 1 to block you. Someone can refuse to collude, so another must take the turn. Someone can decide to become a vigilante and choose always 1 to block you. Humans are very fun!

> unknown non-optimal strategy

The hard part is to establish a prior for this "unknown". Otherwise you can't say anything.

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.

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.

> 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.

A dominant strategy in game theory means it's your best strategy, regardless of what strategy your opponents pick.

> https://en.wikipedia.org/wiki/Strategic_dominance

> In game theory, strategic dominance (commonly called simply dominance) occurs when one strategy is better than another strategy for one player, no matter how that player's opponents may play.

That is what is being described above.

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.

Wait, how did you get to 11.2% missing?

I think a triple tie means no one wins, which would explain why the probability of winning is less than 1/3. (If each of the three players is playing the same Nash equilibrium strategy, they should each win with the same frequency.)

0.296 is the chance of one player winning, there are 3 players. 0.296*3 is 0.888, which leaves 11.2% of chance where no player wins/they all tie

I mean sure I like a little "choose the smallest number" on the weekends, but I wouldn't say I'm a fiend. Gosh.

You don't have to be one, you just want to play with some. I recommend sacrificing a goat.

I worked with a nationwide lottery game in Sweden called Limbo around 2005-2006 that used this concept. I believe the winner each day won around $1000 and had the ability to turn it into $10000 in a weekly final doing the same game in a tv-studio.

The game was completely shut down after people in a small little town won three times in a row and they started to suspect foul play. Turned out to be the local store asking people to join and the store distributed the numbers for the people to make sure they had an even distribution across a huge range.

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 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.

sometimes all 3 players will choose the same number

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.

> 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 < 1/3.

> 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.

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

> Also, if all players use the same strategy then it doesn't matter what the strategy actually is.

But it's not very interesting to add "all players use the same strategy" as an assumption, because yes, obviously, if every player randomly picks from the set {33, 247, 17855433344} each has a 29.6% chance of winning. But that's a different game.

In fact the author doesn't assume everyone will use the same strategy; rather, the author simply asks what optimal play is, when you don't know the others' strategies. The fact that all players choose the same strategy (if they're playing optimally) is a consequence of this. Optimal play has to work regardless of the strategy your opponents pick; assuming they'll play optimally too is just a shortcut to figuring out what optimal play is.

For example, let's say you knew the other two players' strategy is to pick from this distribution. If you simply always pick 1, you win any time neither of the others picked 1, which happens with probability (1-0.456)^2 ~ 0.296 -- the same probability of winning as the optimal strategy! So why bother with the distribution? Precisely because you don't know whether your opponents are playing optimally or not. If another player gets the same bright idea as you, you counteract each other and the 3rd player wins 54% of the time (the rest are ties). An optimal strategy has to be optimal even if opponents are not using it; otherwise it's not really optimal (one may not exist).

So all players using the same strategy is not an assumption, but a consequence, and therefore much more interesting.

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.

oh, I didn't think about it!

It seems that it contradicts the principle of Nash equilibrium, since in Nash equilibrium you don't have any reason to change your strategy. However, if you change a "smart" strategy to a "dumb" strategy you're not increasing/decreasing your winning changes, so it still fulfills the Nash equilibrium principle.

This game seems to do weird things if you have a player able to disclose their choice in advance too. Stating that you will choose 42 is stronger than stating you will choose 1, assuming other players only maximize their own odds of winning. It's kind of like a convoluted game of chicken.

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.

You are right.

Choosing a bigger number makes it less likely that you will win by being smaller than the other two, but more likely that you will win by the other two knocking each other out, since there are now more numbers available for them to do so with.

I think most importantly your opponents become less likely to knock your number out. The goal is your number to win, not your opponents to lose.

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.

There was a cool challenge in the Code Golf community in Stack Exchange, where participants wrote python scripts to compete in this problem over 1,000 rounds. The bots had access to previous rounds' results to inform their choice in each round.

https://codegolf.stackexchange.com/questions/172178/smallest...

There was an online game in the 2000s where this game was played at scale (I think it was called limbo??). Lowest number I remembering seeing win was 4 but it would go up into the hundreds

The game is an interesting one. If an opponent declares an intention to always choose one, you’re more or less forced to collude with other players to beat him. With 3 players this is possible to execute without needing to trust the other person. They cannot fake it out to harm you. But you cannot do anything to avoid purposefully giving the win to another player.

> 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

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?

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 comes out far far behind either of the other two strategies.

This makes sense intuitively:

Agent 3 chooses 1 nearly half (45.6%) of the time. It will lose with that choice every time because Agent 1 chooses 1 every time.

When Agent 3 chooses 2-10 (100 - 45.6 = ) 54.4% of the time, it will lose almost every time because Agent 1 already chose 1.

The only case where Agent 3 wins is when Agent 3 chooses a value 2-10 (54.4%) AND Agent 2 chooses 1 (10%), eliminating itself.

54.4% * 10% = 5.4%, which is exactly the value discovered above.

---

The specific strategies chosen by your competitors have a very large impact on your strategy's effectiveness.

I fail to understand how this can be considered an optimal 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?

> 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.

If there's two of you then you are even better off just always picking 1.

You either win, or tie, depending on your opponent's strategy. Your opponent can never win.

That seems extremely optimal.

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).

This was very helpful. Thank you!

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.

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.

It seemed to me by the description that being first, and picking 0 was sure win. But apparently ties mean nobody wins, or somebody not tied wins, or something. Doesn't say.

Zero points for helpful exposition.

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.

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.

So 3 players are following a strategy that leads them to wind just under a 3rd of the times on average.

If they play thousands of times, what will the distribution of wins be?

The "missing" probability occurs when all 3 players vote for the same number, and thus all three lose.

that's an interesting question! I'll do the simulations later and add the plots to the post. Thanks for the suggestion :)

(Slightly off topic) -- I can't connect to this site from my mobile data or home connection. FF, Curl + mobile FF claim to not be able to resolve the host

The DNS records seem odd:

    $ dig  www.amolas.dev
    [ ... ]
    ;; ANSWER SECTION:
    www.amolas.dev.  66 IN CNAME     https://alexmolas.github.io.
    https://alexmolas.github.io. 66 IN A 185.199.111.153
    https://alexmolas.github.io. 66 IN A 185.199.109.153
    https://alexmolas.github.io. 66 IN A 185.199.108.153
    https://alexmolas.github.io. 66 IN A 185.199.110.153

I don't think you can put a scheme in a cname ...

hi! some people told me that they can access the site, but I've never knew why, and I'm not an expert on websites. Thanks for spotting it!

How can I solve the problem? What does it mean to put a scheme in a cname?

> 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 :)

It works now, good job ;)

18 minutes from report to resolution! Amazing.

Luckily the ttl was only 66s.

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

And the actual problem was probably that many browsers don't show the 'https://' in the URL bar, but do include it when copy-pasting.

So a user who copy pasted from the URL bar into the DNS records (probably following some guide) ended up with the wrong thing in there.

While we're on the topic of the site...

Why do you have links styled to look exactly like the other plain text?

At the bottom of the article, it says "This post has been heavily inspired by this question in SO ↩" and I could not for the life of me find the link to said question until I discovered that "question" was a hidden link.

That's weird, because on my computer it looks well. Some people already complained about that, but I don't know why it can happen. Do you have any suggestion?

This reminds me of an old article quote from a game developer on Steam bug reports from Linux vs Windows users:

>The report quality [from Linux users] is stellar. I mean we have all seen bug reports like: “it crashes for me after a few hours”. Do you know what a developer can do with such a report? Feel sorry at best. You can’t really fix any bug unless you can replicate it, see it with your own eyes, peek inside and finally see that it’s fixed. And with bug reports from Linux players is just something else. You get all the software/os versions, all the logs, you get core dumps and you get replication steps. Sometimes I got with the player over discord and we quickly iterated a few versions with progressive fixes to isolate the problem. You just don’t get that kind of engagement from anyone else.

Reply on news.ycombinator.com