3.1 Extensive Form Game

Extensive Form & the Game Tree

The extensive form representation of a game $G_E$ is used to illustrate sequential decisions by the decision-makers and is specified by the same three finite sets (players, strategies, payoffs) seen in strategic form games. However:

• Every strategy $s_i$ of a player $i\in N$ in a strategic form game is defined as one complete, rational plan of action for each contingency that might arise in a game.

Outcomes in extensive form games are represented by a directed tree called the game tree. Game trees contain three types of nodes:

• A unique root node which implies the start of the tree.
• Decision nodes that branch from their predecessor.
  • Every non-terminal node in a game tree is a contingency, with the number of its successor nodes implying the number of possible strategies of the player making the decision in that contingency.
• Terminal nodes (leaves) which lack successors and imply the end of a single sequence.
  • Each terminal node represents the payoffs for all players along the path of play (sequence) from the root to that specific terminal node.

Examples

Harry Potter

Consider a game where Harry has £1. He can either give it to Hermione or keep it. If Harry gives the £1 to Hermione, she can either destroy it, or magically double it and give half to Harry. We can represent this using a game matrix:

\begin{document}
 
\begin{tikzpicture}
   % Draw the vertical lines
   \draw (0, 0) -- (0, -3);
   \draw (1.5, 0) -- (1.5, -3);
   \draw (3, 0) -- (3, -3);
 
   % Draw the horizontal lines
   \draw (0, 0) -- (3, 0);
   \draw (0, -1.5) -- (3, -1.5);
   \draw (0, -3) -- (3, -3);
 
   % Add labels for players
   \node at (1.5, 1) {Hermione};
   \node[rotate=90] at (-1, -1.5) {Harry};
 
   % Add labels for Player 2's choices
   \node at (0.75, 0.25) {D};
   \node at (2.25, 0.25) {M};
 
   % Add labels for Player 1's choices
   \node at (-0.25, -0.75) {K};
   \node at (-0.25, -2.25) {G};
 
   % Add payoffs for each cell
   \node[draw] at (0.75, -0.75) {(1, 0)};
   \node at (2.25, -0.75) {(1, 0)};
 
   \node at (0.75, -2.25) {(0, 0)};
   \node[draw] at (2.25, -2.25) {(1, 1)};
\end{tikzpicture}
 
\end{document}

In this strange game where Harry can keep the money and therefore Hermione is indifferent between destroying/multiplying it, one of the Nash equilibria $(K,D)$ is clearly not following rational play. This is because sequence clearly matters. As such, we need to represent it as an extensive form game with the tree:

\usetikzlibrary{trees}
 
\begin{document}
\begin{tikzpicture}[
 grow=east, % grow the tree to the right
 edge from parent/.style={draw, -latex},
 sibling distance=4em, level distance=8em,
 every node/.style = {shape=circle,
   draw, align=center}]
 
 \node {Ha}
   child { 
      node [rectangle, draw=none, fill=none] {1, 0}
  	edge from parent node[draw=none, below] {K}
  	[grow=down] % grow downwards from this node
   }
   child { 
      node {He}
  	
      child { 
        node [rectangle, draw=none, fill=none] {1, 1} 
        edge from parent node[draw=none, below] {M}
     }
      child { 
        node [rectangle, draw=none, fill=none] {0, 0} 
        edge from parent node[draw=none, above] {D}
     }
     
  	edge from parent node[draw=none, above] {G}
   };
 
\end{tikzpicture}
\end{document}

Here, we see that the valid strategies for Harry are $\{G,K\}$, whereas the valid strategies for Hermione given each of Harry’s choices are $\{DD,DM,MD,MM\}$. This is because Hermione is faced with the conditional outcome of Harry’s decision. As such, every strategy is a complete plan of action that responds to Harry’s decision. Take $MD$ for example. This means that if Harry chooses to give the money to Hermione, she will multiply it. However, if he chooses to keep it, she will destroy it.

\usetikzlibrary{trees}
 
\begin{document}
\begin{tikzpicture}[
  grow=east, % grow the tree to the right
  edge from parent/.style={draw, -latex},
  sibling distance=4em, level distance=8em,
  every node/.style = {shape=circle,
    draw, align=center}]
 
  \node {Ha}
    child { 
	    node [rectangle, draw=none, fill=none] {1, 0}
		edge from parent node[draw=none, below] {K}
		[grow=down] % grow downwards from this node
    }
    child { 
	    node {He}
		
	    child { 
	      node [rectangle, draw=none, fill=none] {1, 1} 
	      edge from parent node[draw=none, below] {M}
      }
	    child { 
	      node [rectangle, draw=none, fill=none] {0, 0} 
	      edge from parent node[draw=none, above] {D}
      }
      
		edge from parent node[draw=none, above] {G}
    };
 
\end{tikzpicture}
\end{document}