Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

“Are you the one?” is free money

blog.owenlacey.dev

Post reply on HN
Print view View original

21–30 of 119 posts

Re: “Are you the one?” is free money

#21

Post by akoboldfrying »

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

Re: “Are you the one?” is free money

#22

Post by sebastos »

MarkusQ wrote: post #10
latortuga wrote: post #8

Earlier quoted context omitted.

Because when it's true, you also learn about any prior match ups involving those two people.

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

Right - but coming back to the original question, if I'm not mistaken, the explanation is that the blogpost is measuring information gained from an actual outcome, as opposed to _expected_ information gain. An example will help:

Say you're trying to guess the number on a 6-sided die that I've rolled. If I wanted to outright tell you the answer, that would be 2.58 bits of information I need to convey. But you're trying to guess it without me telling, so suppose you can ask a yes or no question about the outcome. The maximum of the _expected_ information add is 1 bit. If you ask "was it 4 or greater?", then that is an optimal question, because the expected information gain is min-maxed. That is, the minimum information you can gain is also the maximum: 1 bit. However, suppose you ask "was it a 5?". This is a bad question, because if the answer is no, there are still 5 numbers it could be. Plus, the likelihood of it being 'no' is high: 5/6. However, despite these downsides, it is true that 1/6 times, the answer WILL be yes, and you will gain all 2.58 bits of information in one go. The downside case more than counteracts this and preserves the rules of information theory: the _expected_ information gain is still EDIT: D'oh, nevermind. Re-reading the post, it's definitely talking about >1 bit expectations of potential matchings. So I don't know!

Re: “Are you the one?” is free money

#23

Post by tobyjsullivan »

Medea wrote: post #7

They 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

The author defines one “bit” as ruling out half the remaining options.

So a yes might rule out 75% of remaining options (for example) which provides 2 bits of information.

Re: “Are you the one?” is free money

#24

Post by hatthew »

jncfhnb wrote: post #14
MarkusQ wrote: post #10

Earlier quoted context omitted.

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

I’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?

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

Re: “Are you the one?” is free money

#25

Post by hatthew »

tobyjsullivan wrote: post #23
Medea wrote: post #7

They 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

The author defines one “bit” as ruling out half the remaining options. So a yes might rule out 75% of remaining options (for example) which provides 2 bits of information.

We have to make a distinction between "expected information gain" vs "maximum information gain". An answer of "yes" generally gains >1 bit, but an answer of "no" generally gains 1; the maximum possible is precisely 1.

Re: “Are you the one?” is free money

#26

Post by pants2 »

codebje wrote: post #20
jncfhnb wrote: post #15

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

Everything 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 b…

I'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!

Re: “Are you the one?” is free money

#27

Post by hatthew »

kevindamm wrote: post #17
MarkusQ wrote: post #10

Earlier quoted context omitted.

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

It's not a yes/no per contestent, it's per edge between contestants. There are n(n-1)/2 of these. A true answer for a potential match is actually a state update for all of the (n-1) edges connecting either contestant, that's 2(n-2) edges that can be updated to be false. Some of these may already be known from previous rounds' matchups but that's still more than a single binary.

An answer of "yes" will generally eliminate many edges, with potential for >1 bit. However, an answer of "no" will generally eliminate just that one edge, which is generally <1 bit.

Re: “Are you the one?” is free money

#28

Post by nrhrjrjrjtntbt »

codebje wrote: post #20
jncfhnb wrote: post #15

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

Everything 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 b…

Need to find out their psycopath screening technique

Re: “Are you the one?” is free money

#29

Post by tobyjsullivan »

hatthew wrote: post #25
tobyjsullivan wrote: post #23

Earlier quoted context omitted.

The author defines one “bit” as ruling out half the remaining options. So a yes might rule out 75% of remaining options (for example) which provides 2 bits of information.

We have to make a distinction between "expected information gain" vs "maximum information gain". An answer of "yes" generally gains >1 bit, but an answer of "no" generally gains 1; the maximum possible is precisely 1.

The total probabilities add up to 1. But I’m not following how that relates to the average bits.

Despite summing to 1, the exact values of P(true) and P(false) are dependent on the options which have previously been discounted. Then those variables get multiplied by the amount of information gained by either answer.

Re: “Are you the one?” is free money

#30

Post by Yossarrian22 »

jncfhnb wrote: post #15

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

That's because the real game is occurring both before and after the show in modern reality tv competitions. The goal is to be entertaining and get social media followers and potential invites to further reality tv shows.
Post reply on HN