Non-Nashian solution for games in extensive form
Last updated
Last updated
Historically, games in extensive form were the first class of games for which a general non-Nashian solution concept was defined, back in 2004.
More specifically, in his seeding 2000 paper, Jean-Pierre Dupuy expressed his idea and conjectures on a particular class of games in extensive form called centipede games. As its name indicates, a centipede game has a particular structure in which, at each node, the current player can either choose to stop or continue the game. If they stop the game, the corresponding payoffs are immediately paid, and otherwise, it is the next player's turn -- until the last node, in which the last player can pick between two outcomes.
This is an example of centipede game (which, again, is also a game in extensive form):
The Nash equilibrium (more specifically, Subgame Perfect Equilibrium) for this game would be (1,0). It is obtained with a backward induction reasoning: if Alice were to play, she would favor 4 over 3, and thus (2,4) over (3,5). Remember that the payoff she gets is the one on the right.
But then, Bob, right before her, prefers 3 over 2 and thus (3,1) over (2,4).
Knowing this, Alice prefers 2 over 1, and thus (0,2) over (3,1).
And finally, Bob prefers 1 over 0 and thus (1,0) over (0,2).
This is the Subgame Perfect Equilibrium, which is also a Nash Equilibrium.
There is, however, one piece of criticism to this reasoning known as the "Backward Induction Paradox". Indeed, the reasoning of Bob picking (1,0) is that if he had continued the game instead, Alice would have picked (0,2) -- but then, the Alice who picks (0,2) would be in the contradictory position of assuming that Bob is rational, while playing at a node following Bob's irrational play (since it was rational for him to pick (1,0)).
We start by asking: can (0,2) be the solution of the game? In other words, if both Alice and Bob had known in advance that this would be the solution they will reach, will they play toward it? The answer is no: if Bob knew in advance that (0,2) would be the solution, he would deviate to (1,0) and get a guaranteed better payoff. This is a contradiction, because then (0,2) is not going to be the solution.
Thus, (0,2) is eliminated because logically impossible. This reasoning was suggested by Dupuy in 2000 and is known as preemption: (0,2) is preempted by (1,0). He also calls this the First Principle (of Non-Nashian reasoning).
The next step of the reasoning is that Bob, now knowing that (2,0) is impossible, is guaranteed to get at least 2$ if he continues the game. Thus, (1,0) is eliminated as well.
This is known as Dupuy's Second Principle: Rational Choice.
Note that the Second Principle can also, which is subtle, be seen as some consequence of the First Principle: (1,0) can also be considered to be preempted by going to the right, with the same algorithmic consequence, but this is less natural to explain. In our discussions with Stéphane Reiche and Jean-Pierre Dupuy, we liked to compare this to taking the lift to the last-but-one floor and then taking the stairs to the last floor.
From a philosophical viewpoint, Dupuy also views this as a direct form of Kantian categorial imperative: "Never act in such a way that, had your action been anticipated, it would not be within your power to carry it out". Thus. Alice continues the game.
The next step is to see that (2,4) is preempted by (3,1). This is again an application of the First Principle.
Then, the Second Principle has Bob continue the game.
And Alice too:
Now, what happens is extremely interesting: this outcome (5,3) is immune to its foreknowledge: knowing in advance that this is the future, and with non-Nashian reasoning, both Alice and Bob willingly play their way towards (5,3). Furthermore, all the reasoning is carried out on nodes that are actually on the path to the solution -- unlike with a backwards induction, in which recursive reasoning is done at nodes that end up not being reached in the first place.
Let us take another example that is more generic than a centipede game, still with two players (it is easy to generalize to any number of players).
The game starts with Bob, whose payoffs are the left numbers on the outcomes. Alice's payoffs are the payoffs on the right.
The non-Nashian resolution with the Perfect Prediction Equilibrium also goes as an iterated deletion of impossible outcomes, assuming Perfect Prediction.
Can (-1,5) be known as the solution in a way both Alice and Bob will play towards it? No, this is absurd: Bob would have known and would have played to the right, where he is guaranteed a payoff of at least 0.
Thus, (-1,5) would lead to a Grandfather's Paradox, and it is logically impossible.
Knowing this, can (0,4) be the solution of the game? Also not: Bob would have deviated to the left, because he knows that (-1,5) is impossible and that he would be guaranteed an outcome of 1.
Thus, (0,4) is also logically impossible and cannot be the solution. At that point, Bob, who knows that (-1,5) and (0,4) cannot be anticipated as the solution, sees that any outcomes on the right (the minimum is 2) are better than any outcome on the left (1). Dupuy's Second Principle of rationality applies, and we now know that Bob will move to the right.
We now know that, on the equilibrium path, Alice will get to play. Alice's payoffs are intertwined (4 vs. 2,3 and 5) so we need again try to apply the First Principle of preemption.
Can (5,0) be known as the solution? No: Alice would be guaranteed to get 1 on the left, which is better than 0 (she knows that (0,4) is impossible already). So (5,0) is preempted by Alice's going to the left.
We see that Alice's payoffs are no longer intertwined, so that the Second Principle applies and Alice goes to the right (any of 2 or 6 is better than 1).
It is now Bob's turn. Here the Second Principle can directly be applied: Bob goes to the right.
The Perfect Prediction Equilibrium is thus (3,2). It is immune to being anticipated as the solution from the very beginning: both Alice and Bob knowing this in advance will play towards (3,2) -- because they both reason transparently and eliminate all the other outcomes following the non-Nashian reasoning.
Here, Dupuy's theory is genuinely beautiful: it was shown that the Perfect Prediction Equilibrium, on games in extensive form with perfect information (we will see later what imperfect information means), always exists, and is always unique. Thus, because it is always unique, it can be predicted in advance, which reinforces the assumption of Perfect Prediction!
Another property of the Perfect Prediction Equilibrium is that it is always Pareto-optimal. This means that no other outcome would give higher payoffs for all players. A Nash equilibrium does not generally have this property. It makes the Perfect Prediction Equilibrium desirable from an micro-economic perspective.
The Perfect Prediction Equilibrium, which is a non-Nashian resolution discovered in 2004 and with co-authors Jean-Pierre Dupuy and Stéphane Reiche, is obtained via a forward induction, from the left to the right. Like in the normal form, the reasoning consists of a series of eliminations of logically impossible outcome, based on reductio ad absurdum.
Next, Alice continues to the game: she is logical and rational and knows that (0,2) cannot be the solution. If this is not natural to you, go back to the Chapter on the . Alice can do whatever she wants, but she knows that, if she had played (0,2), Bob would have known it and played (1,0), and then she would not be in a position to play.
