[HN Gopher] Choose the smallest number not chosen yet
___________________________________________________________________
Choose the smallest number not chosen yet
Author : alexmolas
Score : 77 points
Date : 2022-09-28 18:55 UTC (1 days ago)
(HTM) web link (www.amolas.dev)
(TXT) w3m dump (www.amolas.dev)
| civilized wrote:
| 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.
| alexmolas wrote:
| hi! thanks for your comment. which inequality is the wrong
| direction?
| civilized wrote:
| > 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.
| alexmolas wrote:
| oh shoot, you're completely right! changing it right now,
| thanks for spotting it ;)
| bryan0 wrote:
| 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
| LucasBrandt wrote:
| 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...
| [deleted]
| jasonjayr wrote:
| (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 ...
| alexmolas wrote:
| 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?
| Sohcahtoa82 wrote:
| 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.
| izietto wrote:
| > 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
| alexmolas wrote:
| thank you! I just did it, let me know if now it works :)
| jasonjayr wrote:
| Also confirmed working for me :) Thanks, and good luck!
| izietto wrote:
| It works now, good job ;)
| bombcar wrote:
| 18 minutes from report to resolution! Amazing.
| londons_explore wrote:
| 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.
| adtac wrote:
| 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.
| planede wrote:
| 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.29559774252208477098
| 09965928515386138989754484466083115379546015...
|
| 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
| fransr wrote:
| 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.
| MauranKilom wrote:
| 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?
| layer8 wrote:
| The links are dark blue with a very light grey underline. A bit
| hard to see, I agree, but not indistinguishable.
| aimor wrote:
| Not on my machine in Firefox 104. For me the links aren't
| styled until the mouse hovers over them.
| alexmolas wrote:
| that's weird, on my Firefox the links are styled always. Do
| you have any idea why this can happen?
| aimor wrote:
| Not sure, could be something on my end. But --link-color
| and --link-underline-color are "not set", so maybe sass
| related.
| RcouF1uZ4gsC wrote:
| > 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.
| LodeOfCode wrote:
| 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
| planede wrote:
| 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.
| Revery42 wrote:
| 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.
| wikfwikf wrote:
| This is obviously wrong. If you choose one million billion
| trillion every time you will not win 28% of the time.
| planede wrote:
| You will, your opponents will choose matching numbers 28% of
| the time if they use the Nash-equilibrium mixed strategy.
| alexmolas wrote:
| 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.
| alexmolas wrote:
| 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.
| wodenokoto wrote:
| 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?
| alexmolas wrote:
| that's an interesting question! I'll do the simulations later
| and add the plots to the post. Thanks for the suggestion :)
| jetbooster wrote:
| The "missing" probability occurs when all 3 players vote for
| the same number, and thus all three lose.
| seanw265 wrote:
| 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?
| [deleted]
| yifanl wrote:
| 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.
| seanw265 wrote:
| 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
| yifanl wrote:
| 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.
| seanw265 wrote:
| 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.
| civilized wrote:
| 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.
| credulousperson wrote:
| 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).
| riversflow wrote:
| > 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?
| rawling wrote:
| > 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.
| gus_massa wrote:
| 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.
| tromp wrote:
| 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.
| jetrink wrote:
| 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.
| ZetaZero wrote:
| 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.
| StevenWaterman wrote:
| 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.
| HWR_14 wrote:
| 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.
| theptip wrote:
| > 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.
| HWR_14 wrote:
| No you are incorrect in what a "dominant" strategy means.
| It has nothing to do with dominating your opponent.
| civilized wrote:
| 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.)
| mughinn wrote:
| 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
| alexmolas wrote:
| 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
| gus_massa wrote:
| 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 :)
| tromp wrote:
| 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.
| planede wrote:
| > unknown non-optimal strategy
|
| The hard part is to establish a prior for this "unknown".
| Otherwise you can't say anything.
| [deleted]
| monktastic1 wrote:
| I mean sure I like a little "choose the smallest number" on the
| weekends, but I wouldn't say I'm a _fiend_. Gosh.
| civilized wrote:
| You don't have to _be_ one, you just want to _play_ with
| some. I recommend sacrificing a goat.
| [deleted]
| [deleted]
| xnorswap wrote:
| 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...
| bombcar wrote:
| Iirc the FTC sat on them pretty damn hard.
| chii wrote:
| i thought these reverse auctions are more similar to penny
| auctions!
| oneoff786 wrote:
| 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.
| lisper wrote:
| 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.
| [deleted]
| Jyaif wrote:
| sometimes all 3 players will choose the same number
| ZetaZero wrote:
| I believe this strategy will work against any other strategy,
| not just mirror strategy. Of course, against mirror strat, 1/N
| is correct.
| andrewla wrote:
| 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.
| alexmolas wrote:
| > 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.
| lisper wrote:
| Ah. I didn't realize that ties were counted as non-wins. I
| thought ties would just be ignored.
| feoren wrote:
| > 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.
| [deleted]
___________________________________________________________________
(page generated 2022-09-29 23:02 UTC)