8 ms·
“Are you the one?” is free money
- gus_massa 11mo ago> Score Probability > 0 0.3679 > 1 0.3679 > 2 0.1839 > 3 0.0613 > 4 0.0153 > 5 0.0031 For 0, it's a well known [1] result 1/e, I remember a puzzle where people left their hat and then pick one randomly. Looking at the table it looks like the general formula is 1/(e*n!) that is a Possion distribution. Compare with https://en.wikipedia.org/wiki/Poisson_distribution#Examples_of_probability_for_Poisson_distributions https://en.wikipedia.org/wiki/Poisson_distribution#Examples_... Anyway, I'm not sure if my observation helps too much to solve the original problem. [1] at least I know it :)
- gaogao 10mo ago> Season 8: In this season, they introduced gender fluidity. Whilst an interesting problem on its own, this would have wreaked havoc on my model. Well I guess free money except for that one. In that one, one of the contestants, Danny, did the math for optimizing their remaining Truth Booths and Match Ups to get it down to a 50/50 shot.
- yieldcrv 10mo agohow much free money are we talking here? what are they awarded?
- jdkn 10mo agoHighly enjoyable, high effort blogging
- owenlacey 10mo agoMade my day - thanks
- Medea 10mo agoThey have an example that calculates the expected information gained by truth booths and all of the top ones are giving more than one bit. How can this be? It is a yes/no question a max of 1 bit should be possible
- latortuga 10mo agoBecause when it's true, you also learn about any prior match ups involving those two people.
- MarkusQ 10mo agoThat's not how information works. Learning more from one outcome than the other decreases the probability of that outcome occurring, so the expected information (which is the sum of the outcome probability times the outcome information for each of the two possible outcomes) is always less than or equal to one. If all you can get is a "true" or "false" you expect, at most, one bit of information.
- jncfhnb 10mo agoI’m not really following. But if you’re told that one of A, B, or C is true; you learn more by being told A is True than if you learn D is True, no?
- hatthew 10mo agoYes, you learn more than 1 bit in that case. However, if you are told A is false, you still don't know whether B or C is true, so you gain less than 1 bit. Assuming A, B and C all have equal probability, your average/expected information gain is <1 bit. If you ask the question "which of A, B, or C is true?" then you're not asking a yes/no question, and it's not surprising that you expect to gain more than 1 bit of information.
- jncfhnb 10mo agobut that’s all consistent. “Expected” gain is less than 1 for the truth booths and sometimes > 1 for actuals; and is > 1 on expected value of the match ups, which aren’t binary questions.
- jellevdv 10mo agowhat a nice interactive blogpost, that's amazing all the effort that went into it
- owenlacey 10mo agothanks so much - glad you enjoyed it <3
- verteu 10mo agoFun post. I'd be interested to know: How many consecutive Truth Booths (or: how many consecutive Match Ups) are needed to narrow down the 10! possibilities to a single one? Discussing "events" (ie, Truth Booth or Match Up) together muddles the analysis a bit. I agree with Medea above that a Truth Booth should give at most 1 bit of information.
- jncfhnb 10mo agoIf you can only check pairings one at a time I’m not sure it’s possible to do better than greedily solving one person at a time.
- mnw21cam 10mo agoAgreed. There's an argument elsewhere about how a truth booth can possibly have an expected return of more than 1 bit of information, but in reality most of the time it's going to give you way less than that.
- vitus 10mo agoSo, for 10 pairs, 45 guesses (9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1) in the worst case, and roughly half that on average? It's interesting how close 22.5 is to the 21.8 bits of entropy for 10!, and that has me wondering how often you would win if you followed this strategy with 18 truth booths followed by one match up (to maintain the same total number of queries). Simulation suggests about 24% chance of winning with that strategy, with 100k samples. (I simplified each run to "shuffle [0..n), find index of 0".)
- owenlacey 10mo agoBased on my research, MUs perform better than TBs. For my simulated information theories, the MUs gained ~2 bits of information on average vs ~1.1 for TBs. So if only MUs, we're talking around 10 events - meaning you could get enough information on MUs alone to win the game! Conversely, it would take about 20 events to do this just for TBs. It's not super obvious from the graphs, but you can just about notice that the purple dots drop a bit lower than the pink ones! Hope this helps
- wonger_ 10mo ago> I also pitched this idea to The Pudding, and had a great experience with them nerding out about this subject. Though they didn't take my up on my idea, I left with really great and actionable feedback, and I'm looking forward to my next rejection. Would've been a great Pudding post imo, but oh well, happy to find this nice devblog instead.
- stevage 10mo agoThis was great, but it skipped over the most interesting bit - how you actually choose which matchups and truth booths. That is, an actual strategy that contestants could use that doesn't require a computer.
- owenlacey 10mo agoThank you! This is consistent with feedback I got from the pudding, and is ultimately the reason they didn't go ahead with the post. I tried reverse-engineering the information-theory approach to try see what sort of decisions it made. I noticed that for any match up score of X, the following match up would keep exactly X pairs in common. So if they scored 4/10 one week, they would change 6 couples before the next one. Employing that approach alone performed worse than the contestants did in real life, so didn't think it was worth mentioning!
- vitus 10mo agoIt should be easier to understand the optimal truth booth strategy. Since this is a yes/no type of question, the maximum entropy is 1 bit, as noted by yourself and others. As such, you want to pick a pair where the odds are as close to 50/50 as possible. > Employing that approach alone performed worse than the contestants did in real life, so didn't think it was worth mentioning! Yeah, this alone should not be sufficient. At the extreme of getting a score of 0, you also need the constraint that you're not repeating known-bad pairs. The same applies for pairs ruled out (or in!) from truth booths. Further, if your score goes down, you need to use that as a signal that one (or more) of the pairs you swapped out was actually correct, and you need to cycle those back in. I don't know what a human approximation of the entropy-minimization approach looks like in full. Good luck!
- CmdDot 10mo ago«As such, you want to pick a pair where the odds are as close to 50/50 as possible.» This is incorrect, the correct strategy is mostly to check the most probable match (the exception being if the people in that match has less possible pairings remaining than the next most probable match). The value of confirming a match, and thus eliminate all other pairings involving those two from the search space, is much higher than a 50/50 chance of getting a no match and only excluding that single pairing.
- travisjungroth 10mo agoThis brings up an area that’s been on the edge of my curiosity for years: how do you combine the knowledge of the experts (contestants) with logic to do better either than either strategy individually? It’s mostly about how to elicit the information from the contestants. Once you have the probabilities from them, it seems relatively straightforward.
- Yossarrian22 10mo agoI think you could do some form of Bayesian analysis with the prior being how likely each contestant thought that their available partners were "The One" for each other. Then the truth booth would be used to update your priors.
- jncfhnb 10mo agoI saw an episode of this and felt the contestants didn’t seem that interested in winning the money. Just romance. I was curious how suboptimally they tended to play.
- codebje 10mo agoEverything is lined up for sub-optimal play. For a start, the setting is an emotive one. It's not just a numeric game with arbitrary tokens, it's about "the perfect romantic partner." It would take an unusually self-isolating human to not identify who they feel their perfect match should be and bias towards that, subconsciously or consciously. We (nearly) all seek connection. Then, it's reality TV. Contestants will be chosen for emotional volatility, and relentlessly manipulated to generate drama. No-one is going to watch a full season of a handful of math nerds take a few minutes to progress a worksheet towards a solution each week coupled with whatever they do to pass the time otherwise.
- pants2 10mo agoI'd watch a game show where you put a variety of math nerds on each team and watch them argue about the optimal strategy. Who's strategy will win? The quant analyst or the bioinformatician? Tune in next week!
- bryanhogan 10mo agoReminds me a bit of Devils Plan, or other similar reality game shows in Korea / Asia.
- empathy_m 10mo agoWatched a fantastic film about this on the plane a few years ago, "Liar Game - Reborn". There is some fairly sophisticated logic puzzling and scheming going on (see e.g. sample illustration https://imgur.com/a/0AOb67G https://imgur.com/a/0AOb67G from an interlude about 50min in where there are 3 groups of people who mutually distrust each other, each know a secret collection of 3-4 integers unique to their group, and want to deniably pass share integers with each other which are "not my team's". Another participant watches what happened and realizes in retrospect this is how the info was shared.) A lot more upbeat than "Alice in Borderland".
- akoboldfrying 10mo agoIf the goal is to find the perfect matching in some maximum number of turns or less, it's possible to do even better by using a full game tree that minimises the maximum height of the tree ( = number of turns required), instead of using information/entropy as done here. Basically, using the entropy produces a game tree that minimises the number of steps needed in expectation -- but that tree could be quite unbalanced, having one or more low-probability leaves (perfect matchings) many turns away from the root. Such a leaf will randomly occur some small fraction of the time, meaning those games will be lost. For concreteness, a game requiring 6 bits of information to identify the perfect matching will take 6 steps on average, and may sometimes require many more; a minimax tree of height 7 will always be solved in at most 7 steps. So if you're only allowed 7 steps, it's the safer choice.
- thaumasiotes 10mo ago> For concreteness, a game requiring 6 bits of information to identify the perfect matching will take 6 steps on average, and may sometimes require many more I'm not following your logic. Consider the setup we actually have: 1. You get to ask a series of yes/no questions. (Ignoring the matchups.) 2. Each question can produce, in expectation, up to one bit of information. 3. In order to achieve this maximum expectation, it is mathematically necessary to use questions that invariably do produce exactly one bit of information, never more or less. If your questions do not have this property, they will in expectation produce less than the maximum amount of information, and your expected number of steps to the solution will increase, which contradicts your stated goal of minimizing that quantity. You get the minimum number of steps needed in expectation by always using questions with maximum entropy. Yes. But those questions never have any variation in the amount of entropy they produce; a maximum entropy strategy can never take more - or fewer - steps than average.¹ ¹ Unless the number of bits required to solve the problem is not an integer. Identifying one of three options requires 1.585 bits; in practice, this means that you'll get it after one question 1/3 of the time and after two questions the other 2/3 of the time. But identifying one of 128 options requires 7 bits, you'll always get it after 7 questions, and you'll never be able to get it after 6 questions. (Assuming you're using a strategy where the expected number of questions needed is 7.)
- daturkel 10mo agoAs a math guy who loves reality tv, I was also drawn to the show and wrote a blog post [0] about how to programmatically calculate the probabilities as the show progresses. It was a lot of fun optimizing it to be performant. You can `pip install ayto` to use it to follow along with the show or try out scenarios. The linked post is a very thorough treatment of AYTO and a great read. I really like the "guess who" bit on how to maximize the value of guesses. It's a shame the participants aren't allowed to have pen and paper—it makes optimization a lot trickier! I'm impressed they do as well as they do. [0]: https://danturkel.com/2023/01/25/math-code-are-you-the-one.html https://danturkel.com/2023/01/25/math-code-are-you-the-one.h...
- vasco 10mo agoAnd sometimes they just don't do better as a plot point, staying together an extra week after finding out they are not the one because of the intensity of their love (they met 4 days before)
- daturkel 10mo agoGiving them more credit than they probably deserve but: when you're solving "by hand" like they are in the show, keeping a known non-match couple together may actually be helpful for interpreting the results of a matchup ceremony because you'll know that that couple didn't contribute to the beams.
- owenlacey 10mo ago
- ChristopherDrum 10mo agoI think the part that stings most about this article is when he says, "In my research I came across a boardgame called Mastermind." My lived childhood is old enough to be someone's "research."
- owenlacey 10mo agoSorry :') My wife and I bought the game - it's a great turn based came you can play whilst having trashy reality shows on in the background!
- ChristopherDrum 10mo agoNo no, I was just blindsided by my own feelings when I read that and thought it was kind of funny. Judging from the inexplicable downvoting that comment received (?!) apparently that wasn't clear. I always enjoyed Mastermind, though there is a line of attack on the solution that can render it a little boring. It still maintains a bit of a Wordle-like pleasure.
- rahimnathwani 10mo agoAfter he described the rules, my immediate reaction was 'this is like mastermind'. Sure enough, further down the page: Other than that, in my research I came across a boardgame called Mastermind, which has been around since the 70s. This is a very similar premise - think of it as "Guess Who?" on hard mode.
- shermantanktop 10mo agoMastermind! What a great game. Played it for hours. https://www.mcsweeneys.net/articles/the-mastermind-box-cover-what-the-hell-were-they-thinking https://www.mcsweeneys.net/articles/the-mastermind-box-cover...
- karel-3d 10mo agoA thing to note - the contestants are not allowed to have even pen and paper, as mentioned in the other blogpost. So they need to do these computations in their heads.
- deleted 10mo ago[deleted]
- komali2 10mo agoI would love to know how the author went about constructing those lovely charts. Some library, or done by hand?
- owenlacey 10mo agoHey! It's all vanilla html/js/css - which I'm pretty proud of. I wanted something really minimal, and felt most charting libraries were overkill so wanted to keep my bundle size small. I'm thinking of making the interactive parts open source so people can take a look for themselves if that would be helpful
- komali2 10mo agoWow, that's super cool! I would love to take a peek at the interactive bits.
- AtlasBarfed 10mo agoIsn't 5 impossible in the 6-6 matching?
- owenlacey 10mo agocorrect! I might put a little footnote on this to make that clear, thanks
- 0xkalle 10mo agoWhen my wife and I watched the show I wrote a solver on the side so we always had the current probabilities and impossible combinations on the side. I am thinking about making a website for it when the next season starts. Also: in Germany at least they have 10 x 10 candidates from the start, but sometimes they add a 11th or even 12th of one gender so that there are double matches (e.g. 1 woman has two man as match and needs to find one of it to succeed). This raises the possible combination quite a bit.
- owenlacey 10mo agoWould love to see this! Yes there's a gender fluid season and a season where someone had > 1 match, as well as people leaving part way through the season (apparently perfect matches are interchangeable...). All very interesting spins on the core problem to solve; would be really interested if anyone tries to tackle those seasons.
- zvr 10mo agoSurely you mean 10 + 10 candidates (not 10x10).
- owenlacey 10mo agoWhat are some other gameshows one could nerd out about? I'll start: An obvious one is the traitors, but I dunno if there's much you can do with this one as the contestants rarely gain much concrete information. "Deal or no deal" / "let's make a deal" would have interesting game theory approaches - probably has a lot of parallels with Monty Hall? Countdown (UK) - solving the maths puzzles on here using integer programming would be cool
- ChristopherDrum 10mo ago"Let's Make a Deal" was hosted by Monty Hall and is literally the Monty Hall problem.
- philipwhiuk 10mo ago> This time, one guy has two matches which means that there will be eleven girls, but only ten boys. One thing the show runners do subtle alterations that makes the logic much harder. The Traitors has to do lots of these tricks when not playing the Celebrity edition because there's a self-selection for the sort of person who has already played Werewolf/Avalon-type games.
- yoan9224 10mo agoLove the approach of using information theory to optimize decisions. The concept of "expected information gained" is fascinating - it's basically what good analytics should do: help you ask the right questions to eliminate uncertainty fastest. The interactive visualizations on this post are fantastic. More technical content should be presented this way. Makes complex probability much more intuitive.
- oneeyedpigeon 10mo agoLove this article, OP, especially those interactive demos. One small suggestion: > A truth booth is where a male & female ... The use of "male" and "female" as nouns sounds very unnatural. "A man and a woman" would be a little less jarring, imo.
- pixiemagic 10mo ago[flagged]
- edgineer 10mo agoI hear this commonly about using the words "male" and "female." I think it's unfair. For one thing, the military uses them frequently, and so would veterans. Another reason is that their meanings are age-agnostic which helps to emphasize the intent of the speaker--to differentiate on sex alone, not sex plus age.
- ragazzina 10mo ago"It's used in the military" supports the point the GP is making, that it sounds unnatural in a common context.
- deleted 10mo ago[deleted]
- michaelscott 10mo agoYes because these descriptions are meant to foster dehumanization and detachment, which is very useful in military and scientific study contexts. That's why they also sound unnatural in casual conversation
- joenot443 10mo agoI've always found this to be such a pedantic hill to die on. I don't think the author is an incel and it's pretty rude to throw out that kind of language for what's pretty clearly just a style choice.
- Rperry2174 10mo agoMost hilarious part of this is that if you've ever watched "The Challenge" then you know that these people, truly, often cannot add 3 digit numbers together let alone understand information theory
- CollinEMac 10mo ago> This post is my first foray into content like this. I wanted to scratch the itch of an interesting maths problem, with a light-hearted spin that I hope you enjoyed as much as I did making it. Really impressive imo. I don't remember the last time I was this engaged reading an article on HN.