Question

3. The extensive form of a 2-person game is as follows: 1/ 2 020210 0 0-25-210 (a) What are the pure strategy sets for players I and II. (b) Derive the normal (strategic) form of the game? (c) Find the Nash Equilibrium(a) of the game (d) Is there any sub-game non-perfect equilibrium? Explain.

Answer 1

EXTENSIVE FORM USING PURE STRATEGY GAME SETS FOR 2 PLAYERS:

An extensive-form game is a specification of a game in game theory, allowing (as the name suggests) for the explicit representation of a number of key aspects, like the sequencing of players' possible moves, their choices at every decision point, the (possibly imperfect) information each player has about the other player's moves when they make a decision, and their payoffs for all possible game outcomes.

Extensive-form games also allow for the representation of incomplete information in the form of chance events modeled as "moves by nature". Some authors, particularly in introductory textbooks, initially define the extensive-form game as being just a game tree with payoffs (no imperfect or incomplete information) and add the other elements in subsequent chapters as refinements. The general definition was introduced by Harold W. Kuhn in 1953, who extended an earlier definition of von Neumann from 1928.  Following the presentation from Hart (1992), an n-player extensive-form game thus consists of the following:

• A finite set of n (rational) players.
• A rooted tree, called the game tree.
• Each terminal (leaf) node of the game tree has an n-tuple of payoffs, meaning there is one payoff for each player at the end of every possible play.
• A partition of the non-terminal nodes of the game tree in n+1 subsets, one for each (rational) player, and with a special subset for a fictitious player called Chance (or Nature). Each player's subset of nodes is referred to as the "nodes of the player". (A game of complete information thus has an empty set of Chance nodes.).
• Each node of the Chance player has a probability distribution over its outgoing edges.
• Each set of nodes of a rational player is further partitioned in information sets, which make certain choices indistinguishable for the player when making a move, in the sense that: there is a one-to-one correspondence between outgoing edges of any two nodes of the same information set—thus the set of all outgoing edges of an information set is partitioned in equivalence classes, each class representing a possible choice for a player's move at some point—, and every (directed) path in the tree from the root to a terminal node can cross each information set at most once the complete description of the game specified by the above parameters is common knowledge among the players.

A play is thus a path through the tree from the root to a terminal node. At any given non-terminal node belonging to Chance, an outgoing branch is chosen according to the probability distribution. At any rational player's node, the player must choose one of the equivalence classes for the edges, which determines precisely one outgoing edge except (in general), the player does not know which one is being followed. Thus strategic form games are used to model situations in which players
choose strategies without knowing the strategy choices of the other players.

Strategic form has three ingredients:
◮ set of players
◮ sets of actions
◮ payoff functions

Extensive form games provide more information:
◮ order of moves
◮ actions available at different points in the game
◮ information available throughout the game
Easiest way to represent an extensive form game is to use a game tree

What’s in a game tree? It consists of the following
nodes ◮ decision nodes, ◮ initial node, ◮ terminal nodes
branches
player labels
action labels
payoffs
information sets.

(a) A pure strategy provides a complete definition of how a player will play a game. In particular, it determines the move a player which will make for any situation he or she could face. A player's strategy set is the set of pure strategies available to that player. The pure strategy sets for player I and II for the above example refers to an action choice at each decision node
of that player. There are two pure strategies in the above example. By using backwards induction method, we know that player 2 will play 'a' if player 1 plays either Give or Share, and be indifferent between 'c' and 'd' if player 1 plays Keep. Hence, there are two sub game perfect equilibria, namely (Share, Accept) and (Keep, Accept).  Therefore pure strategy is explained as an outcome where both players feel like they could not have done better given what the others were doing. In pure strategy, if you play a (with probability 1), the other player for example with the same action 'a,' but with probability 1. There is no random play and that is why it is called pure strategy.

The game on the right has two players: I and II. The numbers by every non-terminal node indicate to which player that decision node belongs. The numbers by every terminal node represent the payoffs to the players (e.g. 2, -2) represents a payoff of II to player I and a payoff of I to player II). The labels by every edge of the graph are the name of the action that edge represents. The initial node belongs to player I, indicating that player I moves first. Play according to the tree is as follows: player I chooses between c and d; player II observes player I's choice and then chooses between 'c' and 'd'. The payoffs are as specified in the tree. There are four outcomes represented by the four terminal nodes of the tree: (c,d), (c,d'), (e,f) and (0,0). The payoffs associated with each outcome respectively are as follows (2.0), (0,0), (2,-2), (0,5) (2,-2) and (-10,-10).  If player I plays d, player II will play e to maximise their payoff and so player I will only receive 1. However, if player I plays c, player II maximises their payoff by playing f and player I receives 2. Player I prefers 2 to 1 and so will play d and player 2 will play f. This is the subgame perfect equilibrium.

(b) In game theory, normal form is a description of a game. Unlike extensive form, normal-form representations are not graphical per se, but rather represent the game by way of a matrix. While this approach can be of greater use in identifying strictly dominated strategies and Nash equilibria, some information is lost as compared to extensive-form representations. The normal-form representation of a game includes all perceptible and conceivable strategies, and their corresponding payoffs, for each player. Thus the number of rows equals the number of P1’s strategies and the number of columns is the number of P2’s strategies so the normal form game is a in a table form.  In order for a game to be in normal form, we are provided with the following data:

• There is a finite set P of players, which we label {1, 2, ..., m}
• Each player k in P has a finite number of pure strategies. A pure strategy profile is an association of strategies to players, that is an m-tuple:  s = (s1, s2.............sm).

A game in normal form is a structure

   $G=\langle P,{\mathbf {S}},{\mathbf {F}}\rangle$

where:

$P=\{1,2,\ldots ,m\}$

is a set of players,

${\mathbf {S}}=\{S_{1},S_{2},\ldots ,S_{m}\}$

is an m-tuple of pure strategy sets, one for each player, and is an m-tuple of payoff functions.

${\mathbf {F}}=\{F_{1},F_{2},\ldots ,F_{m}\}$

In matrix form, we know the normal form is going to be a 6 x 6 table. To simplify on notation, in denoting the strategies, P1’s strategy is simply written as ab, and likewise, P2’s strategy is simply written as ef. Then, the normal form representation of the extensive form game is the following:

	ab	ef	0.0
ab	2, 2	2,0	0
cd	2,0 0,0	2,-2 -10-10	0,0 0,0
cd	2,-2 0,5	0,0 0,0	0,0 0,0

(c)  Nash Equilibrium is a concept within game theory, where the optimal outcome of a game is where there is no incentive to deviate from their initial strategy. More specifically, the Nash Equilibrium is a concept of game theory, where the optimal outcome of a game is one where no player has an incentive to deviate from his chosen strategy after considering an opponent's choice. Overall, an individual can receive no incremental benefit from changing actions, assuming other players remain constant in their strategies. A game may have multiple Nash Equilibria or none at all.

The Nash Equilibrium is the solution to a game in which two or more players have a strategy, and with each participant considering an opponent’s choice, has no incentive, nothing to gain, by switching his strategy. In the Nash Equilibrium, each player's strategy is optimal when considering the decisions of other players. Every player wins because everyone gets the outcome they desire. To quickly test if the Nash equilibrium exists, reveal each player's strategy to the other players. If no one changes his strategy, then the Nash Equilibrium is proven.

Nash proves that if we allow mixed strategies, then every game with a finite number of players in which each player can choose from finitely many pure strategies has at least one Nash equilibrium. Nash equilibrium need not exist if the set of choices is infinite and noncompact. An example is when two players simultaneously name a natural number with the player naming the larger number wins. However, Nash equilibrium exists if the set of choices is compact with a continuous payoff. An example (with the equilibrium being a mixture of continuously many pure strategies) is if two players simultaneously pick a real number between 0 and 1 (inclusive) with player one winnings (paid by the second player) equaling square root of the distance between the two numbers.

The coordination game is a classic (symmetric) of two player, two strategy game. The players should thus coordinate, both adopting strategy a, to receive the highest payoff; i.e., 2. If both players chose strategy b though, there is still a Nash equilibrium. Although each player is awarded less than optimal payoff, neither player has incentive to change strategy due to a reduction in the immediate payoff (from 2 to 0). The best situation is when a game has one Nash equilibrium. If there are multiple Nash equilibria, then there is some hope that only one of them is admissible. In this case, it is hoped that the rational players are intelligent enough to figure out that any nonadmissible equilibria should be discarded. In this case, analysis of the game indicates that the players must communicate or collaborate in some way to eliminate the possibility of regret. Otherwise, regret is unavoidable in the worst case. It is also possible that there are no Nash equilibria, but, fortunately, by allowing randomized strategies, a randomized Nash equilibrium is always guaranteed to exist.

(d) Are there any sub-game non-perfect equilibrium in this 2 player game? The Nash equilibrium is a superset of the subgame perfect Nash equilibrium. The subgame perfect equilibrium in addition to the Nash equilibrium requires that the strategy also is a Nash equilibrium in every subgame of that game. This eliminates all non-credible threats, that is, strategies that contain non-rational moves in order to make the counter-player change their strategy.

Using the backward induction, the players will take the following actions for each subgame:

• Subgame for actions c and d: Player I will take action d with payoff (0, 0) to maximize Player I’s payoff, so the payoff for action b becomes (3,3).
• Subgame for actions a and b: Player II will take action b for 0 > 2, so the payoff for action d becomes (0, 5).
• Subgame for actions e and f: Player II will take action d to maximize Player II’s payoff, so the payoff for action a becomes (-2,-2).
• Subgame for actions a and b: Player I will take action d to maximize Player I’s payoff. Thus, the subgame perfect equilibrium is {Dp, TL} with the payoff (-2, 2).

Thus in the above example non-perfect equlibrum does not exist.