9 ms·
Choose the smallest number not chosen yet
- gus_massa 4y agoIf 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.
- alexmolas 4y agoI'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 4y agoThere 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 4y agoThe 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.
- gus_massa 4y agoIt'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!
- planede 4y ago> unknown non-optimal strategy The hard part is to establish a prior for this "unknown". Otherwise you can't say anything.
- tromp 4y agoYes, 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 4y agoI 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 4y agopicking 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 4y agoFor 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 4y agoThis 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.
- 4y ago
- civilized 4y agoWait, 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 4y ago0.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
- deleted 4y ago[deleted]
- monktastic1 4y agoI mean sure I like a little "choose the smallest number" on the weekends, but I wouldn't say I'm a fiend. Gosh.
- civilized 4y agoYou don't have to be one, you just want to play with some. I recommend sacrificing a goat.
- xnorswap 4y agoThis 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/guide/page/reverse-auctions https://www.gamblingcommission.gov.uk/public-and-players/gui...
- civilized 4y agoInteresting 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/ 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 4y agohi! thanks for your comment. which inequality is the wrong direction?
- deleted 4y ago[deleted]
- jasonjayr 4y ago(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 4y agohi! 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?
- izietto 4y ago> What does it mean to put a scheme in a cname? It means that https:// https:// shouldn't be mentioned in the DSN records > How can I solve the problem? You should edit your DNS records and remove it
- wodenokoto 4y agoSo 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?
- jetbooster 4y agoThe "missing" probability occurs when all 3 players vote for the same number, and thus all three lose.
- alexmolas 4y agothat's an interesting question! I'll do the simulations later and add the plots to the post. Thanks for the suggestion :)
- planede 4y agoWhat'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.
- alexmolas 4y agooh, 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.
- Revery42 4y agoThis 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 4y agoThis is obviously wrong. If you choose one million billion trillion every time you will not win 28% of the time.
- planede 4y agoYou will, your opponents will choose matching numbers 28% of the time if they use the Nash-equilibrium mixed strategy.
- wikfwikf 4y agoYou 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.
- MauranKilom 4y agoI 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?
- lisper 4y agoI 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 4y ago[deleted]
- Jyaif 4y agosometimes all 3 players will choose the same number
- ZetaZero 4y agoI believe this strategy will work against any other strategy, not just mirror strategy. Of course, against mirror strat, 1/N is correct.
- andrewla 4y agoIt 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 4y ago> 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.
- deleted 4y ago[deleted]
- planede 4y agoGot 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 https://en.wikipedia.org/wiki/Geometric_distribution
- bryan0 4y agoThere 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
- RcouF1uZ4gsC 4y ago> 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 4y agoBecause 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
- seanw265 4y agoThere 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 4y ago[deleted]
- seanw265 4y agoDiving 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.
- riversflow 4y ago> 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?
- LucasBrandt 4y agoThere 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-unique-number-koth https://codegolf.stackexchange.com/questions/172178/smallest...
- oneoff786 4y agoThe 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.
- fransr 4y agoI 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.
- deleted 4y ago[deleted]
- deleted 4y ago[deleted]
- ncmncm 4y agoIt 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.