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)

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.

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.

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:

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 is an 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.

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.

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