<p>I find the &quot;algorithm&quot; 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).</p>
<p>The idea is that we first conjecture a <em><strong>strategy</strong></em>  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.</p>
<hr />
<h1>Algorithm for finding NE in a 2-player extensive form game</h1>
<p>For each of player 1's pure strategy <span class="math-container">$s_1$</span>, do the following:</p>
<ol>
<li>Find player 2's best response(s) to <span class="math-container">$s_1$</span>. Let the set of player 2's best responses be <span class="math-container">$B_2(s_1)$</span></li>
<li>For each <span class="math-container">$s_2\in B_2(s_1)$</span>,
<ul>
<li>If <span class="math-container">$s_1$</span> is a best response to <span class="math-container">$s_2$</span>, record <span class="math-container">$(s_1,s_2)$</span> as NE</li>
<li>If <span class="math-container">$s_1$</span> is not a best response to <span class="math-container">$s_2$</span>, then there is no NE</li>
</ul>
</li>
</ol>
<hr />
<h1>Example with market entry game</h1>
<p>Entrant has four pure strategies: <span class="math-container">$\{OF,OA,IF,IA\}$</span>.</p>
<ul>
<li>Consider <span class="math-container">$OF$</span>
<ol>
<li>Resident's best response is either <span class="math-container">$F$</span> or <span class="math-container">$A$</span></li>
<li>Entrant's best responses:
<ul>
<li>If resident plays <span class="math-container">$F$</span>, <span class="math-container">$OF$</span> is a best response <span class="math-container">$\to$</span> <span class="math-container">$(OF,F)$</span> is NE</li>
<li>If resident plays <span class="math-container">$A$</span>, <span class="math-container">$IF$</span> is the best response <span class="math-container">$\to$</span> no NE</li>
</ul>
</li>
</ol>
</li>
<li>Consider <span class="math-container">$OA$</span>
<ol>
<li>Resident's best response is either <span class="math-container">$F$</span> or <span class="math-container">$A$</span></li>
<li>Entrant's best responses:
<ul>
<li>If resident plays <span class="math-container">$F$</span>, <span class="math-container">$OA$</span> is a best response <span class="math-container">$\to$</span> <span class="math-container">$(OA,F)$</span> is NE</li>
<li>If resident plays <span class="math-container">$A$</span>, <span class="math-container">$IF$</span> is the best response <span class="math-container">$\to$</span> no NE</li>
</ul>
</li>
</ol>
</li>
<li>Consider <span class="math-container">$IF$</span>
<ol>
<li>Resident's best response is <span class="math-container">$A$</span></li>
<li>Entrant's best responses to <span class="math-container">$A$</span> is <span class="math-container">$IF$</span> <span class="math-container">$\to$</span> <span class="math-container">$(IF,A)$</span> is NE</li>
</ol>
</li>
<li>Consider <span class="math-container">$IA$</span>
<ol>
<li>Resident's best response is <span class="math-container">$A$</span></li>
<li>Entrant's best responses to <span class="math-container">$A$</span> is <span class="math-container">$IF$</span>, not <span class="math-container">$IA$</span>, <span class="math-container">$\to$</span> no NE</li>
</ol>
</li>
</ul>
<p>Hence all three NEs are found.</p>
<hr />
<p>For an example with a simple 3-player game, see <a href="https://math.stackexchange.com/a/3175076/70119">my answer on MSE</a>.</p>
<p>The same procedure can also be used to find perfect Bayesian equilibrium in extensive form games.</p>

CC BY-SA 4.0
2019-04-05T09:55:49.807Z
Neat. It reminds me of the guess and verify solutions I sometimes see in differential games.
Maarten Punt
CC BY-SA 4.0
2019-04-05T05:05:52.083Z
2019-04-05T05:05:52.083Z
2020-06-17T09:40:54.643Z
Herr K.
<p>As far as I know, No. </p>

<p>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. </p>

<p>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.</p>

CC BY-SA 3.0
2015-11-20T07:09:29.287Z
I find the use of the word 'move' in this answer confusing.
Giskard
CC BY-SA 3.0
2015-11-20T07:59:49.960Z
It is a key technical term that I cannot omit or replace. Moves are components of players' strategies in sequential games. In fact, I could probably replace words 'moves' with 'strategies', but I think it would be a little less accurate and not less confusing. In my opinion the idea of converting extensive form sequential games into normal form is itself confusing and something mathematicians would have fun with. I can't think of any practical use for it.
Arthur Tarasov
CC BY-SA 3.0
2015-11-20T08:25:43.143Z
The problem is that move is not at all a technical term and I cannot easily think of a definition where there are some "that do not exist". It seems to be some mix of action and decision point.
Giskard
CC BY-SA 3.0
2015-11-20T08:28:43.493Z
I am also unsure why you included your opinion about normal form conversion in your comment because I did not bring that up at all. Of course you are free to clarify your answer, but why in this comment, why not in the answer itself?
Giskard
CC BY-SA 3.0
2015-11-20T08:42:07.813Z
Seems like we studied by different books. I think move is the same as action. We can then say that a strategy is a complete set of actions. When these actions are in sequence, they can be referred to as moves. Much like they call actions moves in any sequential sports game like chess.
Arthur Tarasov
CC BY-SA 3.0
2015-11-20T11:23:14.770Z
My problem is that your use of the word is confusing. Would it make sense to say "Boris Spassky just made a move that does not exist"?
Giskard
CC BY-SA 3.0
2015-11-20T12:11:03.533Z
Exactly! It doesn't make much sense from practical perspective, that is why they invented subgame-perfect refinement to Nash equilibrium. Here I found a PDF guide with an example how a game in extensive form has 8 strategy sets and when converted to the normal form, it has 36 strategy sets: http://www.sfu.ca/~shihenl/302/Strategies%20Memo.pdf Twenty eight of those strategy sets do not exist in the extensive form representation. But they have to appear in the payoff matrix to maintain all the theoretical formalities. Ironically, the author of the guide says this transformation is very useful.
Arthur Tarasov
CC BY-SA 3.0
2015-11-20T12:15:18.793Z
Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/31861/discussion-between-denesp-and-arthur-tarasov).
Giskard
CC BY-SA 3.0
2015-11-20T13:06:17.467Z
I'm new to chat, I just sent you two messages there but I don't know if you received them
Arthur Tarasov
CC BY-SA 3.0
2015-11-20T14:41:32.797Z
I got no notification, and I replied.
Giskard
CC BY-SA 3.0
2015-11-20T00:59:32.087Z
2015-11-20T00:59:32.087Z
Arthur Tarasov
<p>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. </p>

<p>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.</p>

<p><a href="https://i.sstatic.net/x8oxN.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/x8oxN.png" alt="enter image description here"></a></p>

CC BY-SA 3.0
2015-11-19T21:04:11.610Z
I think you would have to define the exact class of games you consider simple. Personally I don't consider most four player, two action per player extensive games simple.
Giskard
CC BY-SA 3.0
2015-11-19T22:39:33.457Z
@denesp: I agree that four player games in general are not exactly simple. But my point was to give an example where it may be easier to find pure NEs in an extensive form game than in a normal form.
Herr K.
<game-theory><nash-equilibrium>
Identifying Nash equilibria in extensive form game
Herr K.
# Identifying Nash equilibria in extensive form game

(Asked by: username_0 on 2015-11-19)

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.

[![enter image description here](https://i.sstatic.net/x8oxN.png)](https://i.sstatic.net/x8oxN.png)

**Tags:** game-theory, nash-equilibrium
> **Comments:**
> **username_1**: I think you would have to define the exact class of games you consider simple. Personally I don't consider most four player, two action per player extensive games simple.  
> **username_0**: @denesp: I agree that four player games in general are not exactly simple. But my point was to give an example where it may be easier to find pure NEs in an extensive form game than in a normal form.  

---

## 2 answers

### Answer by username_0 on 2019-04-05. Score: 2 | Accepted answer

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](https://math.stackexchange.com/a/3175076/70119).

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

> **Comments:**
> **username_2**: Neat. It reminds me of the guess and verify solutions I sometimes see in differential games.  

---

### Answer by username_3 on 2015-11-20. Score: 2

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.

> **Comments:**
> **username_1**: I find the use of the word 'move' in this answer confusing.  
> **username_3**: It is a key technical term that I cannot omit or replace. Moves are components of players' strategies in sequential games. In fact, I could probably replace words 'moves' with 'strategies', but I think it would be a little less accurate and not less confusing. In my opinion the idea of converting extensive form sequential games into normal form is itself confusing and something mathematicians would have fun with. I can't think of any practical use for it.  
> **username_1**: The problem is that move is not at all a technical term and I cannot easily think of a definition where there are some "that do not exist". It seems to be some mix of action and decision point.  
> **username_1**: I am also unsure why you included your opinion about normal form conversion in your comment because I did not bring that up at all. Of course you are free to clarify your answer, but why in this comment, why not in the answer itself?  
> **username_3**: Seems like we studied by different books. I think move is the same as action. We can then say that a strategy is a complete set of actions. When these actions are in sequence, they can be referred to as moves. Much like they call actions moves in any sequential sports game like chess.  
> **username_1**: My problem is that your use of the word is confusing. Would it make sense to say "Boris Spassky just made a move that does not exist"?  
> **username_3**: Exactly! It doesn't make much sense from practical perspective, that is why they invented subgame-perfect refinement to Nash equilibrium. Here I found a PDF guide with an example how a game in extensive form has 8 strategy sets and when converted to the normal form, it has 36 strategy sets: http://www.sfu.ca/~shihenl/302/Strategies%20Memo.pdf Twenty eight of those strategy sets do not exist in the extensive form representation. But they have to appear in the payoff matrix to maintain all the theoretical formalities. Ironically, the author of the guide says this transformation is very useful.  
> **username_1**: Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/31861/discussion-between-denesp-and-arthur-tarasov).  
> **username_3**: I'm new to chat, I just sent you two messages there but I don't know if you received them  
> **username_1**: I got no notification, and I replied.  

---

