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

Coming to Agreement, a logic puzzle for Oxford admissions interviews

jdh.hamkins.org

Post reply on HN
Print view View original

71–80 of 99 posts

Re: Coming to Agreement, a logic puzzle for Oxford admissions interviews

#71

Post by jedberg »

MauranKilom wrote: post #65
jedberg wrote: post #49

This is basic consensus protocols, so it requires one person to "write" while the other does not. Each variation requires each person to randomly select if they will be the writer and then confirm that with the other person. Here are my solutions without reading theirs first (Edit: I finished reading and it looks like we pretty much agree): Main puzzle: "On each following turn, we will flip a coin and randomly choose…

> Main puzzle: [...] Confirm you agree with the strategy on your next turn, as well as sending a color or null What if they disagree with the strategy? How do you resolve the situation where their strategy is just as valid as yours? > Will I know when it is my turn again, or is that part of the lost information? The turns proceed as in the main variation, you just don't whether the message of each round arrives. As t…

> What if they disagree with the strategy? How do you resolve the situation where their strategy is just as valid as yours?

Then presumably their strategy would also involve a confirmation message, so I would randomly choose my second message to either be "I agree with your strategy" or "I disagree" and then re-propose my strategy. It's all about being random in your choices.

> The turns proceed as in the main variation, you just don't whether the message of each round arrives.

Right, but the strategy changes if I have a fixed counter telling me what turn it is, because then I can reliably say "Pick a color and turn number to announce it and repeat your message on every turn" and as long as the turn number is high enough then the probability of me getting the confirmation is high and we are certain to announce on the same turn.

But if the turn counter has to be kept independently, then we need more information, because first we need to send many messages to determine the baseline delivery success rate so we can have a high probability of being on the same turn number.

Re: Coming to Agreement, a logic puzzle for Oxford admissions interviews

#72

Post by y7 »

mjmahone17 wrote: post #69
y7 wrote: post #57

Just looking at the main puzzle, I don't think the author's solution of randomness works. He suggests using a coin flip between two colors, say red and blue, but it suffers the same problem as the other solutions that he shoots down, namely that you have to get consensus on the pair {red, blue} first. If the other person suggests the pair {green, yellow} in the same round, you're out of luck. If you can get consensus…

The coin flip on the main puzzle is assuming each person proposes exactly one color: do you switch or stay the same. So there is guaranteed to be at most a pair of colors, and the goal is to eventually get agreement between those two options.

What do you do they come up with a different but equally compelling strategy at the same time? One of you is going to have to start following the other person's strategy, but what if you do so at the same time?

Re: Coming to Agreement, a logic puzzle for Oxford admissions interviews

#73

Post by eaglelamp »

MauranKilom wrote: post #60
eaglelamp wrote: post #43

For the first scenario send the message: If two primary colors end and state the color that results from mixing, . If the other participant sends a primary color in the first round you can end immediately. Given that your partner understands primary colors and mixing you will be done after one round. The benefit of this solution is that no matter what your partner sends over to you they have the instructions needed t…

The problem with your suggestion is that your partner might send a different but equally "guaranteed success" strategy (e.g. "...opposite color of the mixing result"). Then how do you agree on which strategy to use? Or, take the critique mentioned in the article: Is red + blue called violet or purple? Same problem: You would need to agree on one name, and this conflict is not solved by you sending what you would call…

I see where you're coming from, but for the problem to be solvable at all we need to presuppose some base level of agreement about the world between you and your partner. To take your critique even further (I haven't seen the article, original sub was a twitter link) how do I know that my partner agrees with me on the set of primary colors?

Ultimately the problem is constructed to prompt a discussion so any reasonable "solution" would do, or if the stakes were life and death maybe the rational solution is to play forever as suggested by other commenters.

Re: Coming to Agreement, a logic puzzle for Oxford admissions interviews

#74

Post by MauranKilom »

Most commenters seem to completely miss the problem of agreeing on the strategy before agreeing on the color. That agreement is at least as difficult as the problem of agreeing on a color itself (because the space of possible strategies is, in some sense, larger than the space of colors), so this is in some sense a recursive problem. The article itself touches on this meta-strategy agreement problem, but then completely ignores it when presenting other strategies (and doesn't go above the first "meta" level).

You could argue that humans have a certain inbuilt meta-strategy for agreeing on strategies and are all inherently different enough to symmetry-break the situation eventually. But the problem supposes everyone is a perfect logician (not a fallible human), and so relying on this "inbuilt meta-strategy" is as mathematically interesting as the answer "people put into this situation will often succeed". (Note that, when pairing up most top-level comments in this thread, if they were executed as written, you would end up with people either failing or never finishing.)

I also think that randomness is, mathematically, a cop-out for two reasons: It requires some external source of "symmetry breaking" (although I suppose humans are decent enough at picking random numbers), and it only gives a probabilistic solution (although this will be good enough in practice). And it does not in itself contribute to solving meta-problem of strategy agreement either.

In terms of a solution to the problem as posed, we can reason that, since the other side is a perfect logician, they will not choose a (meta-)*strategy that can possibly result in a "deadlock". For example, they will not choose "I wait until you write 'blue' and then say 'blue' to the host, and I will never diverge from this strategy" as this runs into a deadlock with the same strategy but different color. "Deadlock" here doesn't necessarily mean "fails to break symmetry", as some strategies don't require that ("choose the average of the two RGB values").

The question remains whether there exists any provably non-deadlockable (meta-)*strategy. If, for every communicated strategy (and this includes any level of meta-strategy), a different strategy is conceivable that results in a deadlock, the problem has no solution. I don't know the answer to this, but here are some thoughts:

- Are what I called "deadlocks" above not just symmetry breaking failures on the (or a certain) meta-level?

- We can average colors to avoid the need for symmetry breaking in color choice. Can we do the same on the (meta-)*strategy level somehow?

- If messages must not be of finite length, it feels like there should be some trick to obtain a solution. But I guess we are interested only in finite message lengths.

Re: Coming to Agreement, a logic puzzle for Oxford admissions interviews

#75

Post by MauranKilom »

jedberg wrote: post #71
MauranKilom wrote: post #65

Earlier quoted context omitted.

> Main puzzle: [...] Confirm you agree with the strategy on your next turn, as well as sending a color or null What if they disagree with the strategy? How do you resolve the situation where their strategy is just as valid as yours? > Will I know when it is my turn again, or is that part of the lost information? The turns proceed as in the main variation, you just don't whether the message of each round arrives. As t…

> What if they disagree with the strategy? How do you resolve the situation where their strategy is just as valid as yours? Then presumably their strategy would also involve a confirmation message, so I would randomly choose my second message to either be "I agree with your strategy" or "I disagree" and then re-propose my strategy. It's all about being random in your choices. > The turns proceed as in the main variat…

> Then presumably their strategy would also involve a confirmation message, so I would randomly choose my second message to either be "I agree with your strategy" or "I disagree" and then re-propose my strategy. It's all about being random in your choices.

What if their choice of (meta-)strategy for agreeing on the strategy is different?

Unless you can prove that only a single winning strategy exists (which every perfect logician will arrive at), you can't really assume that they will cooperate with whatever strategy or (meta-)*strategy you communicate. Sure, most humans will be on the same page as you very quickly as you go up meta-levels, but if you rely on human nature you also quickly get fallibility (see the host of bad answers in this thread) and not "perfect logicians".

> But if the turn counter has to be kept independently, then we need more information

Every time you have the opportunity to send a message, a new round begins (for both participants). Can you explain how this needs "more information"?

Re: Coming to Agreement, a logic puzzle for Oxford admissions interviews

#76

Post by mjmahone17 »

y7 wrote: post #72
mjmahone17 wrote: post #69

Earlier quoted context omitted.

The coin flip on the main puzzle is assuming each person proposes exactly one color: do you switch or stay the same. So there is guaranteed to be at most a pair of colors, and the goal is to eventually get agreement between those two options.

What do you do they come up with a different but equally compelling strategy at the same time? One of you is going to have to start following the other person's strategy, but what if you do so at the same time?

Right exactly.

So long as at least one of you uses a coin flip to switch between the strategy they last suggested and the strategy you last suggested it will work.

Re: Coming to Agreement, a logic puzzle for Oxford admissions interviews

#77

Post by ttz »

ttz wrote: post #56

am i finding some of the comments here over analyzing? you can assume neither of you will end on the first round with a color. message on round 1 = "if you send me a color, let us choose the most alphabetically earliest of your color and my color, which I am sending as red. if you did not send a color, i will not say anything, and logically, you will not either" repeat each round if they continue to not send colors.

ah, yes, good point. thanks for the catch!

Re: Coming to Agreement, a logic puzzle for Oxford admissions interviews

#78

Post by y7 »

mjmahone17 wrote: post #76
y7 wrote: post #72

Earlier quoted context omitted.

What do you do they come up with a different but equally compelling strategy at the same time? One of you is going to have to start following the other person's strategy, but what if you do so at the same time?

Right exactly. So long as at least one of you uses a coin flip to switch between the strategy they last suggested and the strategy you last suggested it will work.

How will you know when you're in sync?

Re: Coming to Agreement, a logic puzzle for Oxford admissions interviews

#80

Post by goldcd »

MauranKilom wrote: post #67
goldcd wrote: post #12

There's solving the problem - and there's solving the scenario. I'd presume that a logical contestant would google blue to be the most frequently chosen random colour, and the two of you would just scream "blue" at each other other and then you'd end the game.

As the article notes, blue is actually a distant second in color choices mentioned by interviewees.

I must confess, I hadn't actually read the 2nd half.

Also that I'd mis-read the question - I'd assumed it was being played with one of the variations, but the variation being used wasn't shared with the participants.

I was always awful at reading the question..

Also my 'gut random colour' was red, but got blue back from google. Maybe there's something about red being a more assertive colour - or maybe it just helps to identify people who googled this article before an interview.

Post reply on HN