# K-level thinking

**K-level thinking** refers to a class of logic problems in which all actors are perfectly rational and possess infinite intelligence. In other words, all actors are able to reason perfectly about their situation, and know that everyone else shares the same capability. Without further qualification, the term "logic puzzle" or "logic problem" usually refers to this type of situation.

K-level thinking is highly useful in analyzing the Nash equilibrium of games and situations.

But it's so simple. All I have to do is divine from what I know of you: are you the sort of man who would put the poison into his own goblet or his enemy's? Now, a clever man would put the poison into his own goblet, because he would know that only a great fool would reach for what he was given. I am not a great fool, so I can clearly not choose the wine in front of you. But you must have known I was not a great fool, you would have counted on it, so I can clearly not choose the wine in front of me.

-Vizzini, The Princess Bride (1987)

#### Contents

## Formal Definition

K-level thinking is defined recursively, with a nonrational level-$0$ player designed for the particular situation (usually acting uniformly randomly), and a level-$k$ player (or a depth $k$ player) basing his actions on the assumption that all other participants are level-$(k-1)$ thinkers. For example, a level-2 player assumes that everyone else is a level-1 player, who in turn assumes that everyone else is playing randomly.

Infinite intelligence is defined as having unbounded/infinite depth, and in K-level thinking problems, it is common knowledge that all actors have infinite depth.

## Examples

Consider a game in which participants choose a number between 0 and 100 (inclusive), with the goal of guessing as close to $\frac{2}{3}$ the average as possible. For example, if five players chose 56, 66, 39, 60, and 47, $\frac{2}{3}$ of the average would be $35.7\overline{3}$, and the third player would win.

In this instance, a level-0 player would choose randomly as usual. A level-1 player would assume that every other player is level-0, so they would guess the average to be around 50, leading them to choose $33.\overline{3}$ as their number. A level-2 player would assume that every other player is level-1, who would choose $33.\overline{3}$, so they choose $22.\overline{2}$ as their number. Level-3 players select the best response to level-2 players, and so on, with the optimal guess decreasing at each level. As a result, when common knowledge of perfect rationality is assumed, the optimal guess is (counterintuitively) zero.

Another example concerns a two-player game in which there are two piles of coins, originally containing four coins and one coin respectively. At each turn of the game, a player may choose to end the game by taking the larger pile, or double the number of coins in each pile. The game also ends after a fixed number of rounds, if neither player has chosen to end the game yet.

In this case, the level-0 player is defined by always choosing to double the piles. A level-1 player will assume his opponent is a level-0 player, and will thus choose to double the piles on every turn except his last. A level-2 player will choose to double the piles on every turn except his second-to-last, since he knows if he were to double the piles on that turn, his level-1 opponent would choose to end the game, resulting in less coins for the level-2 player. Again, this continues inductively, so that an infinitely intelligent player would choose to end the game on the very first turn.

## Backwards induction

Both of the examples above illustrate the thinking behind **backwards induction**, which is the process of determining an optimal starting action by working backwards: by determining the optimal action at the last possible point of the game, the optimal action at the second-to-last possible point of the game can be determined, and so on until the optimal play at the starting time is discovered.

The major advantage to backwards induction is that all players share perfect rationality, so the game can be consistently reduced to a simpler one by determining any player's optimal action on their move. For example, in the doubling game above, the number of possible turns is effectively reduced at each step of the analysis, because players would choose to end the game on their last few possible turns (and, therefore, at any time).

The pirate game:## Three pirates discover 100 gold coins, and must decide how to divide up the treasure. They decide that the oldest pirate should propose a distribution, and all the pirates (including the proposer) will vote on whether they will accept the distribution, or throw the proposer overboard, in which case the next oldest pirate will propose a distribution, continuing the game. Ties result in an accepted distribution.

Assuming all the pirates are perfectly rational, extremely greedy, and bloodthirsty (so they will vote to throw the proposer overboard unless they earn more coins otherwise) how many coins can the oldest pirate earn?

Suppose the game is reduced to the two youngest pirates. Clearly, the older one will propose a "distribution" of 100 coins to himself; since ties go to the proposer, this distribution is guaranteed to be accepted.

Thus, the proposer knows that the youngest pirate will vote for any distribution in which he gets any coins at all, since if he votes no, he will get no coins. So, the oldest pirate can earn himself 99 coins by giving the youngest pirate a single coin, winning the vote 2 to 1.

Here is an extension of the pirate game seen above:

Five pirates have obtained 100 gold coins and have to divide up the loot. The pirates are all extremely intelligent, treacherous and selfish (especially the captain).

The captain always proposes a distribution of the loot. All pirates vote on the proposal, and if half the crew or more go agree with him, the loot is divided as proposed, as no pirate would be willing to take on the captain without superior force on their side.

If the captain fails to obtain support of at least half his crew (which includes himself), he faces a mutiny, and all pirates will turn against him and make him walk the plank. The pirates start over again with the next senior pirate as captain.

What is the maximum number of coins the captain can keep without risking his life?

You met a magician on a train, and after a little chat, he took out $3$ squares of different sizes, as shown below. (The figure may not be drawn to scale.)

**Magician:** "These squares' side lengths are **distinct** digits (from $1$ to $9$ inclusive) whose greatest common factor is $1$."

With a flip of his hand, he transformed the squares into one whole rectangle.

**Magician:** "Now this rectangle's area is the same as the combined area of those $3$ squares. The width of the rectangle is equal to the sum of the $3$ squares’ side lengths, while the height of the rectangle is another **distinct** digit."

**You:** "How amazing! Can you tell me that height then?"

**Magician:** "No. Even if you know it, you still can’t work out the area of the rectangle."

**You:** "Can you at least tell me just one side length of the squares then?"

**Magician:** "No. Even if you know just any one square's length, you still can’t work out the area of the rectangle."

**You:** "Thanks! Now I know the area of the rectangle."

The magician became baffled after he had been advertently tricked to slip out a big clue.

What is the area of the rectangle?

Inspired by Digitalize This.

Sherlock Holmes and I were called to investigate the brutal clash between two gangs, taken place in a bar, a few nights ago. It was rumored that all ensued from burglary, for gold coins, to be exact. There were reports of burly men snatching numerous bags, each containing the same amount of gold coins, into their vehicle before they fled away in a hurry. Just a moment ago, Holmes returned with words from his informant, who had been spying at the thieves' whereabouts.

Holmes: My guy was there just in time to eavesdrop on the thieves' conversation outside as they were dividing the gold coins among themselves. Unfortunately, their voice was muffled, so the best clue he got was these three numbers, which I'm certain that they refer to the number of bags, the number of gold coins in each bag, and the number of thieves, of course. You can see that the difference of the highest and the lowest numbers is less than the lowest number itself.

The puzzle is that we don't know which number is for which, and there are $6$ possible combinations of these mysterious numbers . Nonetheless, my guy took a look through a peephole and saw a remainder of $6$ gold coins on the table after their division.

I: Well, with these numbers in our hands, can't we distinguish them by trying out all possible divisions?

Holmes: No, my friend, Watson. Even if we know all these numbers, we still can't rule out any combination.

What would be the least possible number of thieves in this incident?

**Inspired by** 3 Brothers Riddle

## Strategic dominance

Another type of analysis is **strategic dominance**, in which strategies strictly worse than another are discarded as possible actions, until only "reasonable" strategies remain. For example, another way to analyze the '2/3 the average' game is as follows: selecting a guess between $66.\overline{6}$ and 100 is strictly dominated by any other guess, since 2/3 of the final average cannot possibly be this large. This effectively reduces the maximal possible guess to $66.\overline{6}$. But then, by the same logic, selecting a guess between $44.\overline{4}$ and $66.\overline{6}$ is strictly dominated by any other guess. This logic continues, so that 0 strictly dominates any other guess, and is thus the optimal play.

The same principle applies to deductions made from additional evidence, in which actors eliminate impossible starting cases from the information they are given throughout the course of the scenario.

Prisoners and hats:## A warden gathers three prisoners, puts them in a row, and blindfolds them. He says "I have two black hats and three white hats, and I will put one on each of your heads. If any of you can guess the color of your own hat, you can all go free. But if you guess wrong, you will be executed. If you don't guess, nothing will happen".

The warden takes the blindfold off of the prisoner in the back, who can see the hats of the two prisoners in front of him. He says "I don't know the color of my hat".

The warden takes the blindfold off of the second prisoner, who can only see the hat of the prisoner in front. He says "I don't know the color of my hat."

Finally, the warden takes the blindfold off of the last prisoner, who says "I know the color of my hat". What color was it, and how did the prisoner know?

He was wearing a white hat.

The prisoner in the back didn't know the color of his hat, so both of the other two prisoners know that they aren't both wearing black hats (otherwise, the prisoner in the back would know his hat is white). If the second prisoner saw the prisoner in front wearing a black hat, he would have been able to say his hat was white, since he already knew they weren't both wearing black hats. But the second prisoner didn't know the color of his hat, so he must have seen a white hat on the prisoner in front. The first prisoner thus knows he is wearing a white hat.

The census problem:## A census taker reaches a logician's home.

Census taker: “How many children do you have, and how old are they?”

Logician: “I have 3 children. The product of their ages is 36."

C: “What? Couldn't you just tell me their ages?”

L: “The sum of their ages is the same as my house number.”

C: “That really doesn't help me.”

L: “My eldest child is learning the violin.”

C: “Ah, I see. Have a nice day!”What were the ages of the three children?

The children's ages are 2, 2, and 9.

Since the census taker didn't have enough information after being told the sum of the children's ages, there must be more than one triple of numbers with that sum and with product 36. We can list out the possibilities:

Ages Sum Ages Sum 1, 1, 36 38 1, 6, 6 13 1, 2, 18 21 2, 2, 9 13 1, 3, 12 16 2, 3, 6 11 1, 4, 9 14 3, 3, 4 10 Thus, the logician's house number must be 13, as any other sum would allow the census taker to figure out their ages.

The final piece of information, that the oldest child is learning the violin, tells the census taker that there

isan oldest child, thus ruling out the possibility of the children being 1, 6, and 6. The only remaining possibility is that the children's ages are 2, 2, and 9.

Alice thinks of two positive integers, secretly tells Bob one, and secretly tells Charlie the other. Then the following conversation occurs:

Alice: "The product of my numbers was 8. Or maybe it was 16."

Bob (to Charlie): "I don't know your number."

Charlie (to Bob): "I don't know your number."

Bob (to Charlie): "I don't know your number."

Charlie (to Bob): "I don't know your number."

Bob (to Charlie): "I know your number!"

What was Charlie's number?

Albert and Bernard just became friends with Cheryl, and they want to know when her birthday is. Cheryl gives them two unknowns: $M$ and $D.$

$M$ is the month of Cheryl's birthday (1-12)

$D$ is the day of Cheryl's birthday.

Cheryl then tells Albert the sum $M+D$ and she tells Bernard the product $M \times D$.

Albert: "I don't know when Cheryl's birthday is, but I know that Bernard does not know too."

Bernard: "I could not figure out when Cheryl's birthday is, but I can now."

Albert: "Then I also figured out when Cheryl's birthday is."

What is the earliest Cheryl's birthday could be?

*Input the month and day concatenated; e.g. September 14th is 914*

Four friends named A, B, C, D were challenged to play a weird "Guess-A-Word" game. The 4 contestants would be separated into 4 different chambers, where they couldn't see or hear each other unless permitted, with the following conditions:

- One of the contestants would be blindfolded such that he could not see anything but could still listen and speak well. (The Blind)
- One would be ear-plugged such that he could not hear the others but could still see and speak a word to others. (The Deaf)
- One would be mouth-sealed such that he could not speak but could see and listen well. (The Mute)
- The remaining one would not be constrained by any means at all and perceive all senses. (The Normal)

Initially, none of them knew who was which. Then the game would proceed as follows.

First, A would be secretly shown a word in text. They would then need to verbally tell B by voice. (The walls made B only would hear this. B couldn't see A even B was not blind, so A couldn't communicate using sign language or anything else though if A was deaf and B was blind, B could still hear A's word.) B would then have to say the word aloud to get a point.

Next, it's B's turn telling a new word to C, with the same rules as above. Then it's C's turn telling D, and lastly D's turn telling A.

After the game concluded, the four friends didn't get any point. They then discussed the game:

**B**: That was a hard game!

**A**: Indeed! I wonder what word you've got, C?

**C**: Not a chance. I've only known one word in this game. I'm going to keep it my secret.

**D**: Such a pity. I wish I could know your word, C.

What identities were A, B, C, D during the game? Let 1 = The Blind, 2 = The Deaf, 3 = The Mute, and 4 = The Normal; enter your answer as the identities of A, B, C, and D in order. For example, if you think A is The Blind, B is The Deaf, C is The Mute, and D is The Normal, then you should enter $1234$ as your answer.

## Practical application

Under classical principles, all participants are assumed to have the *common knowledge* of perfect rationality, meaning that every player is aware that other players are perfectly rational (and that they are aware that other players are aware that other players are rational, etc.). However, this is not usually the case in practical settings, as equilibrium rarely occurs in actual play.

In fact, the perfectly rational agent is often at a *disadvantage*, since they overestimate the depth of other players. For example, in the '2/3 of the average' game described in the previous section, classical principles would suggest that the perfectly rational agent would select the number 0. However, the winning number is usually much higher in practice. For example, 21.6 was the winning guess in a competition with over 19,000 participants [1], which is slightly below the number a level-2 thinker would select. Interestingly, although level-0 thinking is generally understood to exist only in the calculation of higher-depth strategies, that experiment saw multiple guesses near 100 (despite the fact that the winner is necessarily at most $\frac{2}{3} \cdot 100=66.\overline{6}$, suggesting some players exhibited level-0 thinking.

Similarly, in the coin game, classical principles suggest that one should choose to end the game on their very first turn. However, in an experiment performed at Caltech with a maximum of four rounds of play, 94% of participants doubled on the first turn, and less than half demonstrated level-3 thinking or higher. When the experiment was repeated with six rounds of play, just 2% of games ended on the first turn. [2]

Interestingly, when chess grandmasters played the doubling game, they generally chose to double when playing against student subjects, but chose to end the game when playing against other grandmasters [3]. This suggests that players take their specific opponents into consideration, rather than making general assumptions.

Nonetheless, players tend to gravitate towards equilibrium after they play the same game multiple times. For example, in the Caltech experiment, 40% of games in the first two rounds exhibited level-0 or level-1 thinking, but just 19% of the subsequent eight rounds showed the same, and the proportion of games ending on the first turn went from 0 to 8%, demonstrating that "learning" occurred. This suggests that, given sufficient time, the game would eventually achieve its equilibrium state. In this sense, K-level thinking can be viewed as a generalization of classical principles, analyzing not only the equilibrium state but the process of reaching it.

## References

[1] Astrid Schou. *Gæt-et-tal konkurrence afslører at vi er irrationelle* (translation: *Guess-a figure competition reveals that we are irrational*). Retrieved January 19, 2016 from http://politiken.dk/oekonomi/ECE123939/gaet-et-tal-konkurrence-afsloerer-at-vi-er-irrationelle/.

[2] Teck-Hua Ho and Xuanming Su. *A Dynamic Level-k Model in Centipede Games*. Retrieved January 19, 2016 from http://rady.ucsd.edu/faculty/seminars/2011/papers/hua-ho.pdf.

[3] Levitt, S. D., J. A. List, and S. E. Sadoff (2009) ‘Checkmate: Exploring Backward Induction Among Chess Players,’ Working Paper, University of Chicago Economics Department.

**Cite as:**K-level thinking.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/k-level-thinking/