# Coming to Agreement, a logic puzzle for Oxford admissions interviews

Let me dive right in with the main puzzle.

Main puzzle. You are a contestant on a game show, known for having perfectly logical contestants. There is another contestant, whom you’ve never met, but whom you can count on to be perfectly logical, just as logical as you are.

The game is cooperative, so either you will both win or both lose, together. Imagine the stakes are very high—perhaps life and death. You and your partner are separated from one another, in different rooms. The game proceeds in turns—round 1, round 2, round 3, as many as desired to implement your strategy.

On each round, each contestant may choose either to end the game and announce a color (any color) to the game host or to send a message (any kind of message) to their partner contestant, to be received before the next round. Messages are sent simultaneously, crossing in transit.

You win the game if on some round both players opt to end the game and announce a color to the host and furthermore they do so with exactly the same color. That is, you win if you both halt the game on the same round with the same color. lf only one player announces a color, or if both do but the colors don’t match, then the game is over, but you have lost.

Round 1 is about to begin. What do you do?

Before getting to solutions, I should also like to mention several variations of the puzzle.

Alternation variation. In this variation of the puzzle, the contestants alternate in their right to send messages—only contestant 1 can send on round 1, then contestant 2 on round 2 and so forth, but still they aim to announce the same color on a round. You are contestant 1—what do you do?

Collision variation. In this variation, players may opt on each round either to end the game and announce a color, to send a message, or to do nothing. But the new thing is that if both players opt to send a message, then the messages collide and are not delivered, although an error message is generated (so the players know what happened). What do you do?

Pigeon variation. This version is like the alternating turn variation, except that now the contestants are separated at much greater distance, and the messages are sent by carrier pigeon, so neither can be sure that the messages actually arrive. You are contestant 1—what do you do?

—————————–

Several of these puzzles are rather open-ended, not necessarily with a clear-cut objectively correct answer, although there are certain important issues that arise and that we had hoped the candidates would realize. So let me now discuss the puzzles in detail and the aspects of them that I find interesting.

For the main puzzle, it seems clear that one should not announce a color to the host straight away in round 1, because it seems not likely enough that the other contestant would also do so with exactly the same color. Rather, one should use the messaging capability somehow to agree on the color and round number on which to end the game. We should only announce, if we have both clearly expressed a plan to announce a specific color on a specific round.

At first, it might seem reasonable to send a message along the lines of “Let’s both announce red on round 3; please confirm in round 2.” The hope would be that the other player would indeed confirm on round 2, and then both would announce the final color of red on round 3.

That idea would work, if we were taking turns in sending messages, as in the alternation version of the puzzle. But in the main puzzle, the players are sending their messages simultaneously, and there is a difficulty for the previous proposal that can be realized by considering what kind of message we might expect to be receiving from our partner on round 1. Namely, perhaps they had a similar idea. It would be a lucky case indeed, if they had had exactly the same idea, also proposing to announce red in round 3. In that event, we would both confirm in round 2 and win with red in round 3.

But a more problematic case would occur if our partner had had a very similar idea, but happened to have made the proposal with a different color. Perhaps in round 1 our partner would have sent the message, “Let’s both announce blue on round 3; please confirm in round 2.” What shall we do then in round 2? If I decide to try to stick with my original red color, I might say, “Let’s use red in round 3”, then the other player might similarly decide to stick with blue, and we would still be at an impasse. Alternatively, if I decide to defer and switch to blue, perhaps they also defer and switch to red. What is clear is that we can’t be sure of confirming on the same color in round 2, and clearly we shouldn’t announce in round 3 with the color choice still unsettled. So the procedure we have discussed so far seems unsuitable.

A deeper contemplation of the problem reveals that this issue of the other contestant doing something very similar, but perhaps with a different color, is a fundamental obstacle to many solution attempts. There is a fundamental symmetry in play between the contestants. Since the messages are sent and received at the same time, and both players are equally logical, it could be that we both end up sending the same kind of message each time, except with different colors. We need somehow to agree on a color and a round number, but it seems that however we decide to make a proposal, it would be equally logical for our partner to make a similar proposal, but with colors permuted somehow.

We seem to need to break the symmetry somehow. Perhaps one might hope to use the alphabetically least color, amongst the two colors that have been proposed so far. That would seem to be a perfectly reasonable way to break the symmetry. But the problem here is that there are also many other perfectly reasonable ways to break the symmetry—the shortest wavelength color, the shorter color word, the color proposed by the younger person, by the older person, and so on. The difficulty is that any given proposal might be faced with a similar but equally reasonable proposal about how to break the symmetry. If I had proposed one such criterion, perhaps my partner proposes another, and we haven’t made any progress, but rather only replaced the difficulty of agreeing on the color with the difficulty of agreeing on the decision criterion of how to decide.

A key insight comes with the idea to use randomness. Suppose I had said in round 1, “I suggest we both announce red next round; I shall do so, if you also suggest this,” but you had said, “I suggest we both announce blue next round; I shall do so, if you also suggest this.” But I have got a coin in my pocket, and from now on, I intend each round to flip the coin, sending the red message on heads and the blue message on tails. If you do likewise, then we are very likely in a few rounds to hit upon the same message, and then we shall win on the next round by following through, announcing the agreed-upon color. That is, if in the first round we each happen to mention a color (whether or not my partner’s message was of the specific form I had mentioned), then I am going on every round to send a message as above, but using one of the two colors randomly. If you logically also choose to do this, then we are very likely to happen to choose the same color on some round eventually, and then win on the following round. This randomzing strategy thus seems fairly sound as a means to come to agreement, and if the partner also realizes this we should expect to win quickly, in just a few rounds with high likelihood. For this reason, I find this to be the best strategy.

A slightly more abstract way to describe the strategy I am proposing is that the symmetry between the players will need to be broken by us agreeing which of us will be leading the process and which of us will follow. I can flip a coin each round to decide if I should try to be leader or follower on that round. On heads, I shall propose a specific plan, “let’s say red next round, if your message indicates that you will follow my suggestion.” On tails, I shall send a message saying, “I am going to follow your plan of action, if you send one this round.” In this way, we are likely in a few rounds to have established a leader and follower, and win shortly afterward.

Some student candidates and commentators had proposed an interesting idea of trying to blend the two colors. This would be a way of coming to an agreement, but without needing to break the symmetry between the players. If I had proposed initially that we should announce red and you had proposed blue, then the idea is that logically we should both try to average these colors and say purple. I like this idea a lot, but it seems problematic in light of the fact that we don’t have such a clear and unambiguous means of combining colors. For example, should we mix the colors in the manner of mixing paint or rather in the manner of mixing colored light, which produces completely different results? Even when mixing red+blue, I might say purple and you might say violet. And what of stranger color combinations, such as orange+green? If we were using rgb colors, then some colors are simply adjacent in the color space (or an even distance away), and so they have no exact average mixing. Furthermore, why should we use rgb rather than cmyk or another color space system? And color mixing does not work identically for these two systems. For these reasons, I find the color mixing idea ultimately less than completely successful.

The alternation variation of the puzzle admits an easy solution, since the symmetry is broken already by the rules of the game. Player 1 will be the first to send a message, and can simply say, “I shall announce red on round 2; if you do so as well then we shall win.” There would be no reason for player 2 not to follow along, and so the players can expect to win on round 2.

Some candidates had suggested a confirmation round, having player 1 say, “let’s say red on round 3, confirm if that is agreeable.” Then both players would confirm the intention on round 2, and win on round 3. This is also successful, but it seems to me that the confirmation step is not strictly needed.

The collision variation is an interesting hybrid, because although there is a symmetry between the players in terms of how the rules apply to them, the symmetry is broken in the event that one sends a message and the other does not. The best solution here seems to be a random solution. Namely, flip a coin to decide whether to send a message or stay silent. On heads, send the message “Announce red on next round, if this message gets through.” On tails, do nothing, and plan to follow whatever is suggested on the message that might be received. Because of the randomness, it is very likely that in a few rounds a message gets through one way or the other, with a quick win straight afterward.

The pigeon variation is simply a version of the two-generals problem. The first player can try to propose a specific plan, naming a round and color, and ask for confirmation. But the confirmation itself will need to be confirmed, if the other player is to want certainty. But in this case the confirmation of the confirmation will need to be confirmed, and so on ad infinitum. No finite number of confirmations of receipt will be enough, even if all are received, since if $n$ confirmations suffice to attain mutual certainty, then the last confirmation needn’t be sent, since the protocol would work even if it didn’t arrive, and so $n-1$ should also suffice, a contradiction.

In the admissions interviews, which were generally less than 25 minutes, we were happy if a candidate got to the realization of the symmetry issue in the main puzzle, before going on to the alternating version, which most students got quickly, and then the collision version, where the randomness idea seemed to arise more naturally. The best candidates were then able to realize how to apply the randomness idea to the main version. With the pigeon version of the puzzle, successful candidates realized the need to achieve confirmation and confirmation of confirmation, and a few put this together to mount the impossibility argument for the case of certainty, and most realized how to increase the likelihood of success by picking a distant round and repeating messages. It was quite enjoyable for me to discuss these problems with so many very sharp student candidates.

Let me close by mentioning a few observations that surprised me about using the puzzles in an interview setting.

The first observation is the remarkable amount of personality that was revealed by the candidate’s choices in the puzzles. Some candidates tended to follow what might be called a leader’s approach (or the bully strategy?), attempting in the main puzzle to achieve agreement by conveying obstinateness in the color choice, to convince the other person to change sides as a way of coming to agreement. An equal number of other candidates tried instead to be deferential, sending messages that they would agree to use whichever color the other person wanted. Of course, each of these strategies works fine when paired with the other, but when paired with exactly the same personality, the methods face the symmetry problem we discussed earlier. Some brilliant candidates pointed out that the role that these personality differences played in the puzzle—it was very unlikely that the two contestants would be perfectly balanced in their personalities, and so the symmetry would be broken simply because one candidate would be slightly more insistent or slightly more deferential. And I have to say that realistically, this is how the puzzle would actually be solved in practice.

Another observation was that the candidates overwhelmingly chose red as their color, whenever they mentioned a specific color. About 2/3 or more did so. Far behind this was blue, in second place, and then we had a very small number of mentions of orange, green, yellow, and black.

I really enjoyed using this puzzle for the interviews, and I feel it helped us to choose a really great incoming class.

Art by Erin Carmody.

## 45 thoughts on “Coming to Agreement, a logic puzzle for Oxford admissions interviews”

1. Here is the message I would send:

“In round 7, end the game and announce blue.

In the event that you have sent me a similar message this round, I will defer to whoever recommended the highest round to end on.

In the event that you recommended we end in round 7, I will defer to your color choice in that round.

Please confirm your action in the message for the next round and all subsequent rounds. I will send no more messages.”

• Suppose that your partner, being just as logical as you are, sends an exactly similar messsage, but with red instead of blue. What will you do?

• Here’s the message you receive in Round 1:

“In round 9, end the game and announce red.

In the event that you have sent me a similar message this round, I will defer to whoever recommended the LOWEST round to end on.

In the event that you recommended we end in round 9, I will defer to your color choice in that round.

Please confirm your action in the message for the next round and all subsequent rounds. I will send no more messages.”

• And what if they send you a similar message, but suggest to defer to whomever suggested the highest round? Will you still make the announcement on the lower round, if they had suggested a lower round?

2. Would this work?
Toss a coin

– If heads, say: “I am waiting to see what you say and if you suggested a strategy compatible with a colour to coordiate on, I will follow this coordination, otherwise I will toss a coin and next term will do [[insert entire strategy from ‘Toss a coin’]]”

– If tails, say: “lets coordinate on red next turn, unless you have suggested something that is not compatible with this red, in which case next turn I will do [[insert entire strategy from ‘Toss a coin’]]”

3. In round 1, contestant 1 asks 2nd contestant to choose a colour for round 3 and send it as a message in round2.so both can exit with same colour in round 3

• This works for the alternating version of the puzzle, but it doesn’t work for the main puzzle, since perhaps the other contestant sent exactly the same message in round 1 at the same time. So now in round 2, neither knows who is to send the chosen color.

• Round 1 (no matter what the second contestant writes) I send the following: “I suggest you propose the round we end the game and the color we choose. No matter what you have written in the message you send me during the first round, I give the choice to you. Let me know in round 2”. My next messages will contain the same text until the second contestant tells me the number of rounds we end and the color. If his has the same common sense (or logic) like I do, as described in the rules of the game, we will have no problem coordinating this way…

4. My thought was to establish who decides on the plan first, originally by age but seeing as two people could have the same age I decided on a random draw from the real numbers. Something like:

“Pick a real number of your choice. My choice is 7. Whoever’s is larger will decide which color we play on which turn to end the game. If we both pick the same number, I will choose a new one. Otherwise I will keep my choice.

I’ll send this message repeatedly until one of us picks a greater number and we’ll proceed from there.”

Similar element of randomness to the coin flip idea, tho that has a certain elegance to it.

• How will you respond if there initial message is very similar, except that they said whosever number is smaller will be the one to decide?

5. Unless I missed it, there is no prohibition on messages that refer to the two-way epistemic structure of the game, to motivate a collaboration process. “Let’s not announce until we both know we have agreed a round and a colour” etc. Agreement on a round and a colour can then be achieved in stages, but premature announcement is avoided, as both are known to each other to be rational and wishing to avoid a losing move.

6. Hi Joel, I like your “I suggest we both announce red next round; I shall do so, if you also suggest this” strategy and I came up with something similar. However, there is always a problem of converging on the same strategy, whatever that strategy maybe.

A funny way out can be: “I’m going to suggest red whatsoever, and I will announce it immediately after you comply.” And I’m well aware that my counterpart might suggest something else and be very stubborn as well. I’m going to think of a very large number and keep writing the same sentence, until that number of times, I comply. This is not a guaranteed survival, but since the probability of us both complying at the same large number is extremely low.

7. “A key insight comes with the idea to use randomness. Suppose I had said in round 1, “I suggest we both announce red next round; I shall do so, if you also suggest this,” but you had said, “I suggest we both announce blue next round; I shall do so, if you also suggest this.” But I have got a coin in my pocket, and from now on, I intend each round to flip the coin, sending the red message on heads and the blue message on tails. If you do likewise, then we are very likely in a few rounds to hit upon the same message, and then we shall win on the next round by following through, announcing the agreed-upon color. This randomzing strategy thus seems fairly sound as a means to come to agreement, and if the partner also realizes this we should expect to win quickly.”

That’s just getting the problem to a different layer and the same examples from before apply. What if they have the exactly same message but just with red instead of blue? You are always at the question which meta strategy should be used.

Each message could either be: a) the exact same strategy b) the same strategy with a small variance that is also reasonable c) a completely reasonable other strategy d) just a color e) waiting or something unrelated to the problem itself
The problem is that every proposal of a-e could get matched with something of a-e that ruins it.

Examples:

1. I say just a color, they say just a color. You stay by the color they also stay, you decide to switch they also do it at the same time.

2. You propose something to confirm, so did they and we are back at 1.

3. You decide to do something random and they also decide to do something random with the same outcome

So you could try to get to know each other and just chat to something unrelated but there is still the problem that they could exactly mirror your messages again.

So you both come to the conclusion that there is no 100% strategy. You could now decide that you should continue playing the game forever or decide that a strategy with less than 100% is good enough.

You can now both skip the meta part because both have realized that it just takes the problem to a different layer and the fastest way is to just announce random colors. As soon as the color is matched you end the game and announce it on the next turn. If the colors never match (which could theoretically happen) the game never ends.

• The point with randomness is you only say announce a colour if in one round you’ve both said the same one (so if they said blue and you red, like you raise, you will not announce a colour). The advantage of randomness is that it ensures with probability 1 you’ll eventually give the same proposed colour.
I guess it’s possible to have one layer deeper problems if you’re always saying “I will choose X in next round if you agree” and their messages always refer to rounds other than the next one, but if you randomise between the type of message you started with and the types of messages they’ve ever used then you’ll eventually match provided their strategy doesn’t involve devising a new style of message every time.

8. My first message would be “My name is Sean. What is your name?”. Since life and death are on the line and the number of rounds is unlimited, we would send hundreds of messages back and forth getting to know each other and eventually filling in enough back story to make this episode of Squid Game (presumably) interesting. Only once we are sure we have established enough conversational protocol that at least we don’t talk over each other, we can finally agree color and round number to end on.

• I like this idea very much. I’d like to be partnered with you. I suppose one could reintroduce a sense of urgency, however, by imagining that the prize was greater for winning sooner. What would you do in this case?

• This does sound more and more like Squid Game. I think I’m the character who is content to escape with his life.

• This seems like a good idea but has also the same problem that they could simply mirror your messages the whole time by accident or you could write with each other and decide at the same time to finally propose a color at the same time as they do.

• In normal conversation, people seldom speak over each other. My point is that with enough practice we will be able to communicate effectively, which is what it’s all about.

9. Some initial thoughts: First version:
Choose a random colour, say red, and send “I will choose red next round unless you have said you will choose another colour, in which case I will not end the game, regardless what you have said”. Then repeat every round until a match.
Alternation “I will choose red next round”
Collision: flip a coin, if heads send “I will choose red next round”, if tails send nothing and act on any received message.
Pigeons: choose a random large number, say 1007 send a message saying “I will choose red in round 1007 unless I receive a message identical to this with a larger number in it in which case I will follow your lead. I will not end the game prior to round 1007 regardless what you’ve said. If you have also chosen round 1007 and a different colour, I will not end the game that round regardless what you have said.” then send the same message multiple times. With a large enough number some of those should get through.
The main issue is what happens if I’ve said I won’t end the game and you’ve said you will, I think both players will naturally accept the more cautious non-ending of the game till consensus is reached.

• I didn’t read carefully enough to see that one player goes first in the pigeon version, which as noted in the article breaks the symmetry and reduces the chances of the other player trying to form their own plan!

10. “Choose a random colour, say red, and send “I will choose red next round unless you have said you will choose another colour, in which case I will not end the game, regardless what you have said”. Then repeat every round until a match.”

What if they write the exact same thing but with blue instead of red?

• You re-randomise every round, sorry if that wasn’t clear. So the second round maybe you’ve picked brown instead of red. The probability you match them eventually is 1 (better if, as the post suggests, you randomise only between colours one of you has previously mentioned, assuming they don’t have a strategy of choosing a completely new colour to suggest every round)

• But why make it so complicated? We are both perfect logicans, we both know that its obvious that as soon as someone writes the same color as the other have sent we stop and announce it next round. We don’t have to establish this rule. So we can skip this part and just write random colors until they match. But even then the chance that they will eventually match is never 100%.

• They might have been doing some different strategy: for example you could use the strategy for the collision version in the original game. So making it concrete under what circumstances I’ll make a guess and what circumstances I won’t has value even if it’s a bit redundant.
With two colours, the probability of no match within n rounds is 0.5^n, and as n tends to infinity this tends to zero, so they will match at some point with probability 1 by the law of large numbers (just like the probability of flipping heads every round forever is zero, you’re sure to get tails at some point). It’s confusing in probability that something can in principle be possible (heads forever) and yet have probability zero, but that’s how it works

11. 1st message to partner: Choose a colour at random from n available colours and at round n, announce the colour.
1st round partner chooses colour and I send a message with the colour I chose.
2nd round partner chooses colour and I send a message with colour I chose.
nth round round partner chooses colour and I send a message with my colour which should be matching his/her colour, asking to verify and announce.

• Is it a problem if they had sent you a similar round 1 message, but with a different value for n and a different list of colors?

12. I send this message and follow it to the letter:

” I will send this message until you reply with “I will follow your plan.” Once I have received the message, the plan will go in to effect the following round. We restrict ourselves to three colors: Red Blue and Green. On the first round of the plan, we each send the other a message containing one of the three colors. On the second round, we both end the game. The color we say depends on our messages. If we sent the same color, we both say that color. If we sent different colors, we both send the color neither of us sent.”

I know the other player will not end the game on round one, since they have no information and are perfectly logical. I will not end the game until I receive conformation of the plan, so the perfectly logical other player will be compelled to follow it. After that, we are guaranteed to say the same color.

• I will send this message until you reply with “I will follow your plan.” Once I have received the message, the plan will go in to effect the following round. We restrict ourselves to three colors: Yellow Violet and Cyan. On the first round of the plan, we each send the other a message containing one of the three colors. On the second round, we both end the game. The color we say depends on our messages. If we sent the same color, we both say that color. If we sent different colors, we both send the color neither of us sent.

• What if they send the same message over and over again until you decide to obey?

• That’s a good point. Add a clause then that says “if we both do the send-until-obedience trick, then the following turn we both send the message “plan B,” and then each randomly select one of the plans to carry out, and message which plan we have selected. If we have chosen the same plan, carry it out. Else, randomly pick a plan again and repeat.”

With probability 1, we will eventually pick the same plan

13. It’s a funny puzzle because it actually works much better for non-logicians. I suspect normal people would open with something like ‘hello’, rather than the hypothetical logician’s plan which usually amounts to some sort of logical screed.

One aspect I am considering is opening the transmission with one’s own program’s code. If both players know the other’s program, atleast there is complete information available.

This reminds me a bit of the TCAS system in aviation… although in that system, each participant has a unique id assigned.

14. We send a number to each other, and whoever has the largest number decides what to do, and then the one with the smallest number can only reply “agree”. If the numbers are the same, we continue to send another number to each other until we get the result
1. If you agree please reply agree in the next round, then send a number in the next round after reply agree, because I will send you a number when i receive agree, and finally we will do as mentioned above
2. If you don’t agree, I will keep sending this message until you agree
3. If I get a message with the same idea in the next round, I’ll just go ahead and send you a number

15. 1. “…whom you can count on to be perfectly logical, just as logical as you are.”

I’m quite unlogical at times. Like every other human I know, I make mistakes quite often. In some sense, I don’t view the main puzzle as too much different than the pigeon variation. There is always some chance for miscommunication. (For instance, even after reading this reply multiple times, am I absolutely sure there are no typos?)

Moreover, I think it is important for us to realize this in ourselves, so that we actively look for errors in our own work as mathematicians. Sanity checks are an important practice.

I’d further argue that one of the consequences of proof theory is that the “perfectly logical” thinker is an inconsistent notion.

2. “You are a contestant on a game show… []…the stakes are very high—perhaps life and death.”

I’m not the kind of person to willingly participate in such a “game”. That said, this situation could easily be modified to a new situation where the stakes are high, and I would willingly want to come to a consensus with someone else.

If I really was forced to be on such a life-or-death game show, I’d question whether my partner even spoke English, that my communications would be left unchanged, and so forth.

3. Finally, my solution to the problem would be exactly like oli cairns proposed, based on a coin toss.

Those familiar with von Neumann’s solution to the Sherlock Holmes “Final Problem” might naturally think about introducing randomness to remove issues related to the thought process of the other agent.

I find it quite interesting that there is no general solution without randomness. It might be interesting to point out that a common language is also necessary.

16. I’d rely on a proposal that suggests we pick a simple protocol that allows us to take advantage of the randomness of a coin flip. Eventually we’ll agree on a coin flip, and whoever gets heads will then pick the color the subsequent round, to be communicated and then announced on the round after that. (Both heads or tails means we flip again.)

I’m counting on being able to agree on that protocol. I think with a little bit of back-and-forth, we’d agree on that or something similar and good enough.

17. The first and only message will be The Colors of the rainbow and end(defining the pattern). This means there will be 7 rounds and in the 8th round the game will end, following this pattern the colors confirmed in the game show will be Red, orange, yellow, green, blue, indigo, violet, and END. Toodaloo

18. My message would be;

“I will end the game in round 3. In round 2, please confirm you will also end in round 3 and tell me any primary colour (Red, Yellow, or Blue), however this is not the colour we will end the game with in round 3.

In round 2, I will also chose a primary colour and tell you that colour; but again, this is not the colour to end the game with.

Instead, when we end the game in round 3, we will mix the two colours we’ve each chosen in round 2 to create the final colour to end the game in round 3.

If in round 2 one of us says red and the other blue, then we’ll know to end the game in round 3 with purple.

If in round 2 one of us says red and the other yellow, then we’ll know to end the game in round 3 with orange.

If in round 2 one of us says yellow and the other blue, then we’ll know to end the game in round 3 with green.

If we both chose the same colour, we will go with that colour. If we both say red in round 2 then we end on red in round 3.

If we both say yellow in round 2 then we end on yellow in round 3.

If we both say blue in round 2 then we end on blue in round 3.

Thanks for working with me”

19. I believe, in practice, things are less complicated. Assuming both contestants are smart enough not to end the game abruptly in round 1, the message sent should be “I suggest {color}, we could end the game if our suggestions match”. Candidates are assumed to be logical, so they will not suggest exotic colors (like magenta, aqua etc.) and will reach an agreement within first four or five tries at max. Most of the people are likely to suggest red as the first thing (often, bright colors come to our heads as the first thing) and if not, first few suggestions are likely to be red, blue, green or yellow. But this is not fool proof as one could argue.

Writing a message like “Unless you have already suggested that you want to be the leader in your latest message, I announce myself as the leader and you should follow me” leave a collision risk if the other party sends exactly the same message. But in practice, this is how some of the leadership election protocols in computer science works.

By flipping a coin, you are reducing the search space to 2 items and in return, gain a 50% chance of agreement in each round. But it makes an implicit assumption that other party catches this pattern.

20. Message 1: MTWTFSS. ROYGBIV.

Today is Wednesday, so we both play Yellow next round.

21. I’m going to play rock, paper, scissors, with a colour every round until one of us wins, then will end the following game with that colour.

2/3 chance of ending it in 2 further rounds.

Not much can scupper that. What other game can be played with no pre-agreement? Just requires the second player to realise your plan is great, abandon their idea and play.

22. Thanks for this and your other puzzles! You say in the blog here that the puzzles do not necessarily have “a clear-cut objectively correct answer”, but I feel like what you say in response, and perhaps this is all hashed out in conversation with interviewees, but especially in the way the puzzle is framed in the Guardian piece (https://www.theguardian.com/science/2022/feb/21/did-you-solve-it-an-oxford-university-admissions-question), the solution you offer seems to have a problem.

You actually mention a couple solutions – randomly choose colors, or randomly choose a dictator, until there is convergence. But what if one partner starts randomly choosing colors, or proposes that both partners randomly choose colors until there is convergence, but the other partner instead randomly appoints a dictator (who will on the next round propose a color that both will choose the following round), or proposes that both partners randomly choose a dictator until there is a convergence? (Or what if one partner wants one extra round where both say OK to confirm, but the other partner doesn’t want an extra round to confirm, or wants two rounds to confirm just to be doubly sure?)

The concern is that just as partners will be unable to guarantee agreement on a color directly, they will be unable to directly guarantee agreement on a method to choose a color. And they will be unable to directly guarantee agreement on a method to choose a method. The issue is that the symmetry problem is the same at every level.

Randomness is necessary when there are identical agents or algorithms stuck in symmetry. But I’m not sure that randomization is a core feature of the best solution here, because the parties aren’t said to be identical, and they would have to agree on the randomization strategy, and that’s just as hard to agree upon as the the color announcement itself.

My sense is that the best way, even for the first problem, is going to be to propose shooting for an agreement on round 50 or something, taking time, and coming to a gradual agreement. (I like the proposal above to use early rounds to develop rapport with the partner. And that might also randomize the round by which the first person would make the first concrete proposal, which might avoid symmetry conflict.)

(Note: This is partly influenced by a facebook thread with Tim Maudlin, David Chalmers, and Bernard Kobes.)

• The parties don’t have to agree on the randomization strategy. If a person randomly decides to act as follower or leader on each round, then the symmetry will be broken, for if on a round I decide to be a follower and say something like “if you make a proposal this round I will follow it”, then as long as the other player did have a plan (for a color and round and such regarding the issue of an extra round of confirmation) then my message indicates that we have found a plan. They don’t need to have been following my style of leader/follower randomness for this to work. So while I agree with some of your remarks, I find the leader/follower random strategy much more robust than you suggest.

• I suppose the quibble here would be if neither party was willing to be a leader.

A new symmetry appears, the symmetry of fear/indecisiveness.