Identifying Nash equilibria in extensive form game

Question

Is there a systematic way of identifying all (pure strategy) Nash equilibria (not just the subgame perfect ones) in an extensive form game? In the following Entrant v Resident example, there are three NEs, two of which ($(OF,F),(OA,F)$) are not subgame perfect. What I've been doing is to convert the extensive form to normal form, and then find NEs there. While reliable, this method is time consuming, and gets complicated as the number of actions/players increases. For example, I suspect that it'd be much easier to spot NEs in a four-player extensive game (each with two action, say) than its normal form equivalent.

I'd be interested to know if there's any procedure that we can use to find pure NEs in a reasonably simple extensive form game.

Answer 1

As far as I know, No.

While I am not sure why you would want to find non-subgame perfect Nash equilibria in an extensive form game, I am sure you would need to convert it to normal form to do it. Extensive form of a sequential game carries more information than normal form, specifically which moves do not exist within the sequence. In a normal form representation of the sequential game you have to show every possible move available to every player, even the moves that do not exist. So basically when you convert a sequential game from extensive form to normal form, it becomes another game where you then look for Nash equilibria.

If you are doing a two player game where each player gets one move, you can do it in your head just by looking at the game tree, but if the game is any more complex, you would need to do it step by step, first converting it into a normal form.

Answer 2

I find the "algorithm" below quite useful and easy to follow. It works well for most common two-player extensive form games (that do not take a full page to draw). It also works well in games with more than two players and a sufficiently simple information structure (e.g. perfect information).

The idea is that we first conjecture a strategy for the first player (player 1). Then we find out the best responses of the subsequent player(s). Lastly we check whether the initially conjectured strategy for player 1 is a best response to the other players' best responses (to it). If it is, we have a profile of mutually best responding strategies, hence a NE; if it isn't, then we don't have any NE with the initially supposed strategy of player 1.

---

Algorithm for finding NE in a 2-player extensive form game

For each of player 1's pure strategy $s_1$, do the following:

1. Find player 2's best response(s) to $s_1$. Let the set of player 2's best responses be $B_2(s_1)$
2. For each $s_2\in B_2(s_1)$,
   • If $s_1$ is a best response to $s_2$, record $(s_1,s_2)$ as NE
   • If $s_1$ is not a best response to $s_2$, then there is no NE

---

Example with market entry game

Entrant has four pure strategies: $\{OF,OA,IF,IA\}$.

• Consider $OF$
  1. Resident's best response is either $F$ or $A$
  2. Entrant's best responses:
     • If resident plays $F$, $OF$ is a best response $\to$ $(OF,F)$ is NE
     • If resident plays $A$, $IF$ is the best response $\to$ no NE
• Consider $OA$
  1. Resident's best response is either $F$ or $A$
  2. Entrant's best responses:
     • If resident plays $F$, $OA$ is a best response $\to$ $(OA,F)$ is NE
     • If resident plays $A$, $IF$ is the best response $\to$ no NE
• Consider $IF$
  1. Resident's best response is $A$
  2. Entrant's best responses to $A$ is $IF$ $\to$ $(IF,A)$ is NE
• Consider $IA$
  1. Resident's best response is $A$
  2. Entrant's best responses to $A$ is $IF$, not $IA$, $\to$ no NE

Hence all three NEs are found.

---

For an example with a simple 3-player game, see my answer on MSE.

The same procedure can also be used to find perfect Bayesian equilibrium in extensive form games.