Saturday, September 7, 2013

96. Noncooperative Games and the Nash Equilibrium

'The trouble with the rat race is that even if you win, you are still a rat' (Lily Tomlin).

Noncooperative game theory is concerned with the analysis of strategic choices. Here the details of the ordering and timing of players’ choices are crucial in determining the outcome of a game. In a noncooperative model of bargaining, one defines a specific process in which it is stated who gets to make an offer at a given time. Even cooperation can arise in a noncooperative model of a game when players find it in their own interests to cooperate rather than compete.

In a noncooperative game, communication, correlated strategies, side payments, binding contracts etc. are not available to the players. Let us first consider a two-player game of this type. One usually looks for equilibrium points. Any such point is a pair of strategies such that neither player gains by a unilateral change of strategy. Consider the payoff matrix shown below; it has two equilibrium points (Owen 1995).

(2,3)  (4,4)*
(5,2)* (3,1)

The second-row first-column payoff (5, 2) is an equilibrium point. If player 1 unilaterally chooses the first row instead of the second, his payoff goes down from 5 to 2. Similarly, if player 2 unilaterally chooses the second column instead of the first, his payoff goes down from 2 to 1.

Interestingly, there is one more equilibrium pair of strategies here, namely at first row second column, with a payoff (4, 4). This possibility of more than one equilibrium points is characteristic of nonzero-sum games. It does not occur in zero-sum games (cf. Part 95).

We have seen in earlier posts that the equilibrium-point scenario is not always in the interest of the players. For example, we have seen in the case of the Prisoner’s Dilemma (cf. Part 92) and the Traveller’s Dilemma (Part 93) that the equilibrium-point strategy, even though unique, gives a payoff of only (2, 2), which is not in the best interests of the players.

Some improvements over the equilibrium-point concept are the concepts of undominated equilibrium, and perfect equilibrium (Owen 1995).

For plural games in strategic form, the most well-known solution is in terms of the noncooperative equilibrium, better known as the Nash equilibrium (Nash 1950, 1951, 1953). Suppose there are n players in a game, with the set of players represented by N = {1, 2, ..., n}. Player i selects a strategy si from his set of pure strategies Si. Any vector s = (s1, s2, ..., sn) represents a possible set of strategies chosen by the n players. Suppose we replace the ith component of this vector by a strategy si*. The Nash theorem states that there exists a pure-strategy noncooperative equilibrium vector s* = (s1*, s2*, ..., sn*) which represents an optimal strategy or response, meaning that, given the strategies of all the other players, no individual player i can improve his payoff by unilaterally selecting a strategy si other than si*.

The theorem can be extended to the case of mixed strategies by allowing each player to select a probability distribution over his set of pure strategies.

The Nash equilibrium situation is one of self-fulfilling expectations. Suppose each player is a strictly rational individual, and knows or expects all other players to be rational as well. There is then a mutually consistent set of expectations such that if each player optimizes his expectations, then the predictions of each player will be fulfilled.

But even in the perfect-rationality scenario, the problem with Nash equilibrium is that, as seen above, there may be more than one Nash equilibria.

Moreover, as seen with the Prisoner’s Dilemma and the Traveller’s Dilemma games, the Nash equilibrium choice of strategies in not always the most efficient and profitable way of making strategic moves (Dubey 1986; Dubey and Rogawsky 1990).

The Nash equilibrium solution has been mostly applied to the strategic form of games. Applying it to the extensive form can be illuminating, as the extra detail of information can highlight many additional aspects of the game. An example is the introduction of the concept of perfect equilibrium point in this context by Selten (1975). Such an equilibrium has the property that it is an equilibrium point not only for the game as a whole, but also in every subgame.

I shall consider cooperative games in the next post. As we shall see, when cooperation between players is possible, the focus shifts from strategies to bargaining about how the payoff will be divided among the cooperating players.