game theorynash-equilibrium
How can you find the Nash equilibrium of a game directly from the extensive form game/game tree of a game. You can find Nash equilibria from the strategic form (normal form table), but finding it directly from the extensive form seems very interesting as well. A position/strategy profile is a Nash equilibrium if it is a best response to other strategies of the other players. (The photo is in the link). Thank you.
How can we do this for the 3 player game tree below:enter image description here
You should construct an "upper envelope diagram" that describes the best response pure strategies and payoffs of player 2 against the mixed strategies of player 1. For an example, see the left part of figure 1 in the following paper:
D. Avis, G. Rosenberg, R. Savani, and B. von Stengel (2010), Enumeration of Nash equilibria for two-player games. Economic Theory 42, 9-37. http://www.maths.lse.ac.uk/Personal/stengel/ETissue/ARSvS.pdf
(That paper also includes a complete technical exposition of the general problem for m by n games.)
Here is an example of the upper envelope diagram for a 2x5 game, where player I has pure strategies A and B and player 2 has pure strategies a,..,e.
What you are interested in is the "vertices" of this upper envelope. The two vertices at the far left and right correspond to the best responses against the two pure strategies of player one (so for these vertices you just check if the corresponding strategy of player 1 is a best response to this best response of player 2).
Vertices between these correspond to mixed strategies of player 1 that make player 2 indifferent between (at least) two different pure strategies.
Suppose we are at such a vertex defined by the pure strategies of player 2 a and b. For this vertex you need to look at the two columns of player 1's payoff matrix that correspond to a and b and check if the best response of player 1 against a is different from the best response of player 1 against b (or is tied, but let's ignore that case for simplicity). If these two best responses to a and b differ then you can find a mixed strategy for player 2 that makes player 1 indifferent between his two pure strategies. Then this strategy of player 2, paired with the strategy of player 1 given by the point on the x-axis in the best response diagram, is a Nash equilibrium.
You need to check this for every vertex (for the example above, corresponding to {d} at the left, then {d,b},{b,a}, and {a,e} in the interior, and {e} on the far right). Checking the far left and far right vertices correspond to checking for pure Nash equilibria. Checking the "interior" vertices corresponds to looking for equilibria where both players use 2 pure strategies.
Things can be complicated by degeneracies in the payoffs, e.g., three lines meeting in one point on the upper envelope, but I won't go into that here.
To investigate this, you can use our software:
For your first question: In a Nash equilibrium, all strategies chosen with positive probability by a particular player yield the same expected payoff. The reason is that if they didn't, then a player could do better by moving some of his probability from a worse strategy to a better strategy. For a fixed support for each player, this condition gives several linear equations in the probabilities. The nondegeneracy assumption implies that such equations have a unique solution.
But solving these equations is not enough to give a Nash equilibrium. Probabilities have to be nonnegative, so if the unique solution involves negative numbers it cannot be a Nash equilibrium. Furthermore, just because all strategies used with positive probability yield the same expected payoff doesn't mean that is the best possible payoff. Maybe it is the worst, or somewhere in the middle. So you need to check Equation (3.2) to ensure that no player can do better by deviating. If this is confusing, think about how replacing $A$ and $B$ with $-A$ and $-B$ changes the game but essentially does not change the linear equations involved. The inequalities are very important.
Any $x,y$ satisfying the equations, inequalities, and (3.2) define a pair of probability distributions such that players only choose best replies to their opponent's strategy with positive probability. Therefore such $x,y$ form a Nash equilibrium. That all Nash equilibria can be found this way (in particular that both players have the same support size in a Nash equilibrium) makes heavy use of the nondegeneracy assumption.
To answer your second question: a Nash equilibrium of a "subgame" (if I understand your terminology this is different from what is usually meant by subgame) is not necessarily a Nash equilibrium of the original game. In particular, Equation (3.2) holding for a subgame does not imply that it holds for the original game.
Best Answer
It's a bit tedious to describe, but with enough practice, you should be able to follow the steps below to quickly identify NEs (not only the subgame perfect ones) from a game tree.
The idea is that you first suppose player 1 plays a certain strategy. Then you find out the best responses of the other players. Lastly you check whether the initially supposed strategy for player 1 is a best response to the other players' best responses (to it). If it is, you have a profile of mutually best responding strategies, hence a NE; if it isn't, then you don't have any NE with the initially supposed strategy of player 1.
Suppose player 1 plays $A$
Suppose player 1 plays $B$
Overall, there are three NEs: $(A,w,S)$, $(B,v,S)$, $(C,v,S)$, with the first being the only SPE.