3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Giskard Nov 19 '15 at 21:04
  • $\begingroup$ @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. $\endgroup$ – Herr K. Nov 19 '15 at 22:39
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I find the use of the word 'move' in this answer confusing. $\endgroup$ – Giskard Nov 20 '15 at 7:09
  • $\begingroup$ 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. $\endgroup$ – Arthur Tarasov Nov 20 '15 at 7:59
  • $\begingroup$ 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. $\endgroup$ – Giskard Nov 20 '15 at 8:25
  • $\begingroup$ 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? $\endgroup$ – Giskard Nov 20 '15 at 8:28
  • $\begingroup$ 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. $\endgroup$ – Arthur Tarasov Nov 20 '15 at 8:42
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Neat. It reminds me of the guess and verify solutions I sometimes see in differential games. $\endgroup$ – Maarten Punt Apr 5 at 9:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.