Game theory analyses multi-agent situations in which the payoff to an agent is dependent not only upon his own actions but also on the actions of others. Zero-sum games assume that the payoffs to the players always sum to zero. In that case, the interests of the players are diametrically opposed. In non-zero-sum games, there is typically room for cooperation as well as conflict.

The normal or strategic form characterizes a game by three elements. First, the set of players, N = {1, 2,…, n}, who will be making decisions. Second, the set of strategies, Si, available to player i∀i ∈ N where a strategy is a rule which tells a player how to behave over the entire course of the game. A strategy often takes the form of a function which maps information sets (that is, a description of where a player is at each stage in the game) into the set of possible actions. Thus, an action is a realization of a strategy. Finally, the normal form specifies the payoff function, Vi(·)of player i∀i ∈ N. A payoff function is a composition of a player’s von Neumann–Morgenstern utility function over outcomes and the outcome function which determines the outcome of the game for a given set of strategies chosen. The normal form of a particular game is presented in Fig. 1. The set N is {1, 2} while S1 = {α, β, γ} and S2 = {a, b, c}. The payoff to player 1 (2), for a given pair of strategies, is the first (second) number in the box.

figure 1428figure 1428

Non-cooperative Games, Fig. 1

A game is classified as either cooperative or non-cooperative, a distinction which rests not on the behaviour observed but rather on the institutional structure. A cooperative game assumes the existence of an institution which can make any agreement among players binding. In a non-cooperative game, no such institution exists. The only agreements in a non-cooperative game that are meaningful are those which are self-enforcing. That is, it is in the best interest of each player to go along with the agreement, given that the other players plan to do so. In analysing the pricing behaviour of firms in an oligopolistic industry, a non-cooperative game is generally appropriate since, in most countries, cartel agreements are prohibited by law. Therefore, firms do not have access to legal institutions for enforcing contracts and making agreements binding.

Let us examine the game in Fig. 1 under the assumptions that it is non-cooperative and that players are allowed preplay communications. After discussing how they each plan to behave, players 1 and 2 will simultaneously make a decision as to which strategy to play. After the strategies are chosen, the payoffs will be distributed. It is straightforward to show that the class of self-enforcing agreements for this game is {(α, a), (γ, c)}. Consider the agreement that player 1 chooses α and player 2 chooses a. By choosing a, player 2 maximizes his payoff under the assumption that player 1 goes along and plays α Similarly, player 1 finds it optimal to choose α if he believes player 2 will go along with the agreement. Thus, (α, a) is a self-enforcing agreement.

To understand the cost imposed by the restriction that an agreement must be self-enforcing, consider the agreement (β, b) Since it yields payoffs which are Paretosuperior to both (α, a) and (γ, c) the two players obviously have an incentive to try and achieve those strategy choices. However, even if they came to the agreement (β, b) it would be ineffectual. If player 1 truly believe that player 2 would honour the agreement and play b, player 1 would be better off reneging and choosing α instead. Because agreements cannot be made binding, the two players are then forced to settle on a Pareto-inferior outcome.

A solution concept for non-cooperative games which encompasses the notion of self-enforcing agreements is Nash equilibrium. Originally formulated by Nash (1950, 1951), the concept finds its roots in the work of Cournot (1838).

FormalPara Definition

An n-tuple of strategies, (s*1, …, s*n) is a Nash equilibrium if

$$ {\displaystyle \begin{array}{l}{V}_i\left({s}_1^{\ast },\dots, {s}_n^{\ast}\right)\ge {V}_i\left({s}_1^{\ast },\dots, {s}_{i-1}^{\ast },{s}_i,{s}_{i+1}^{\ast },\dots, {s}_n^{\ast}\right)\hfill \\ {}\times \forall {s}_i\in {S}_i,\forall i\in N.\hfill \end{array}} $$
(1)

A profile of strategies forms a Nash equilibrium if each player’s strategy is a best reply to the strategies of the other n-1 players. The appeal of Nash equilibrium as a solution concept rests on two pillars. First is the stability inherent in a Nash equilibrium since no player has an incentive to change his strategy. Second is the very large class of games for which it can be proved that a Nash equilibrium exists. To substantiate this last remark, we will first need to introduce an additional concept – the mixed strategy. A mixed strategy takes the form of a probability distribution over the set of pure strategies Si (for example, for the game in Fig. 1, a mixed strategy for player 1 could be to choose α with probability 0.4 and β with probability 0.6). A pure strategy is thus a special case of a mixed strategy in which unit mass is placed on the pure strategy. A game is said to be finite if the strategy set Si is finite ∀i ∈ N

FormalPara Theorem

(Nash 1950, 1951): In any finite non-cooperative game \( \left\langle N,{\left\{{S}_i\right\}}_{i\in N},{\left\{{V}_i\right\}}_{i\in N}\right\rangle, \) there exists a Nash equilibrium in mixed strategies.

The ease of existence of Nash equilibria also brings forth the major drawback to the concept – the lack of uniqueness. It has also been observed that when multiple Nash equilibria exist, some of them can be quite unreasonable. For the two-player game in Fig. 2, there exist two pure-strategy Nash equilibria, {(α, a), (β, c)}. However, (α, a) is rather unreasonable as it entails player 1 using the strategy α which is weakly dominated by β (That is, by choosing β instead of α he would never be worse off and could end up better off.) In attempting to define what is meant by reasonable and to achieve a unique solution, work by Selten (1975), Myerson (1978), Kreps and Wilson (1982), Kalai and Samet (1984) and others has developed solution concepts that are more restrictive than Nash equilibrium.

figure 1429figure 1429

Non-cooperative Games, Fig. 2

Due to the difference in institutional structures, the issues analysed under a non-cooperative game setting tend to be quite different from those dealth with in cooperative games. Since all agreements can be made binding in cooperative games, much of the analysis is concerned with determining which point in the Pareto-efficient set the players will settle on. Issues of importance are then coalition formation and the division of gains among coalition members. In contrast, in a non-cooperative game, at issue is whether players can even reach the Pareto-efficient frontier; in the game in Fig. 1, they do not. However, it has been observed in both experimental and real world situations (e.g., see Axelrod 1984) that when the game is repeated players are indeed able to achieve Pareto efficiency in a non-cooperative game like in Fig. 1. An important issue in non-cooperative games is then to understand the role of repetition in allowing players to overcome the inability to cooperate.

Let us suppose the one-shot game in Fig. 1 is repeated T times, where \( T\geqslant 2, \) and the players are fully aware of the repetition. A strategy for player i now takes the form of a sequence of functions, \( {\left\{{G}_i^t\right\}}_{t=1}^T \), where Gti maps the history of play over {1,…, t – 1} into the set {α, β, γ}{(a, b, c)} if i = 1(2). Assume that the payoff to a player is the (undiscounted) sum of the single-period payoffs.

Let gti denote the observed action of player i in period t. Consider the following pair of strategies:

$$ {\displaystyle \begin{array}{l}{G}_1^1=\beta \\ {}{\boldsymbol{G}}_1^t=\left\{\begin{array}{l}\beta \kern0.24em \mathrm{if}\kern0.24em {\boldsymbol{g}}_1^{\tau }=-\beta, {\boldsymbol{g}}_2^{\tau }=\boldsymbol{b},\tau =1,\dots, \boldsymbol{t}-1,2\le \boldsymbol{t}\le \boldsymbol{T}-1\hfill \\ {}\gamma \kern0.24em \mathrm{if}\;{\boldsymbol{g}}_1^{\tau }=\beta, {\boldsymbol{g}}_2^{\tau }=\boldsymbol{b},\tau =1,\dots, \boldsymbol{T}-1,\boldsymbol{t}=\boldsymbol{T}\hfill \\ {}\upalpha\ \mathrm{otherwise};\hfill \end{array}\right.\end{array}} $$
(2)
$$ {\displaystyle \begin{array}{l}{G}_2^1=\boldsymbol{b}\\ {}{\boldsymbol{G}}_2^t=\left\{\begin{array}{l}\boldsymbol{b}\kern0.24em if\kern0.24em {\boldsymbol{g}}_1^{\tau }=\beta, {\boldsymbol{g}}_2^{\tau }=\boldsymbol{b},\tau =1,\dots, \boldsymbol{t}-1,2\le \boldsymbol{t}\le \boldsymbol{T}-1\hfill \\ {}\boldsymbol{c}\kern0.24em if\;{\boldsymbol{g}}_1^{\tau }=\beta, {\boldsymbol{g}}_2^{\tau }=\boldsymbol{b},\tau =1,\dots, \boldsymbol{T}-1,\boldsymbol{t}=\boldsymbol{T}\hfill \\ {}\mathbf{a}\kern0.24em \mathrm{otherwise}\hfill \end{array}\right.\end{array}} $$
(3)

The strategy of player 1 says that he will start off by playing β and will continue to do so as long as (β, b) has been observed in all previous periods. If (β, b) was observed for all t ∈{1,…, T − 1} player 1 will choose γ in the final play. However, if the path ever deviates from (β, b) for any \( t\leqslant T-1 \), he will choose α for the remainder of the game. The strategy of player 2 is similarly defined.

If the two players pursue these strategies, the path of play will be (β, b) for t ∈{1,…, T − 1} and (γ, c) for period T. Each player will earn a total payoff of 5 T – 1. The key issue, however, is whether these strategies form a Nash equilibrium. Given that player 1 pursues \( {\left\{{G}_1^t\right\}}_{t=1}^T \), can player 2 earn a payoff higher than 5 T – 1 by choosing a strategy different from \( {\left\{{G}_2^t\right\}}_{t=1}^T \)? If not, then player 2’s strategy in (3) is optimal. The strategy in (3) calls for player 2 to cooperate over {1,…, T – 1} in the sense of not maximizing his single-period payoff. The alternative strategy is to choose a rather than b for some t ≤ T − 1 and earn 6 rather than 5 in that period. Since the gain from cheating is only in that period, it is best to cheat at the last moment so as to maximize the time of cooperation. The best alternative strategy for player 2 is then to choose b over {1,…, T – 2} and cheat in period T – 1 in playing a. The resulting payoff is 5(T – 2) + 6 + 2 = 5 T – 2. Since this is less than 5 T – 1 then \( {\left\{{G}_2^t\right\}}_{t=1}^T \) is a best reply to \( {\left\{{G}_1^t\right\}}_{\mathrm{t}=1}^T \). Similarly, one can show that this is true for player 1 as well and therefore the two strategies from a Nash equilibrium.

Repetition on the one-shot game has allowed players to earn an average payoff of 5 – (1/T) compared with 4 or 2 in the one-shot game. Furthermore, as the horizon tends to infinity, the average payoff converges to the Pareto-efficient solution. Repetition expands the set of self-enforcing agreements by allowing players to be penalized in the future for cheating on an agreement. The penalty here is that the game moves to the Pareto-inferior single-period Nash equilibrium of (α, a) Because it is a Nash equilibrium, this threat is credible. Cooperation is rewarded by settling at the preferred solution (γ, c) in the final period. Note that cooperation cannot be maintained over the entire horizon since, in the final period, it is just like the one-shot game. Thus, the players must settle at either (α, a) or (γ, c) Development of cooperative behaviour in the finite horizon setting is due to work by Benoit and Krishna (1985), Friedman (1985), and Moreaux (1985). However, the original work for the infinite horizon game goes back to Friedman (1971).

When players are allowed preplay communication, there is a very strong basis for requiring a solution to be a Nash equilibrium because such equilibria are self-enforcing. However, when players cannot communicate, Nash equilibrium loses some of its appeal as a solution concept. (Actually, if there are multiple Nash equilibria, this is also true for games with preplay communication as players may fail to come to an agreement.) Work by Bernheim (1984) and Pearce (1984) suggests that there can be profiles of strategies which are reasonable for players to choose yet which do not constitute a Nash equilibrium.

Let us start with the basic premise that each player holds a subjective probability distribution over the strategies and beliefs of other players. Furthermore, impose the axiom that ‘rationality is common knowledge’. That is, it is common knowledge that each player acts to maximize his payoff subject to his subjective beliefs. A set of beliefs is said to be consistent if it is not in violation of the ‘rationality is common knowledge’ axiom. In particular, you do not expect another player to pursue a nonoptimal strategy. A strategy is rationalizable if there exists a set of consistent beliefs for which that strategy is optimal.

To understand rationalizability as a solution concept, consider the game in Fig. 3. The unique pure-strategy Nash equilibrium is (β, b). It is easy to show that every Nash equilibrium strategy is rationalizable. β is optimal for player 1 if he believes player 2 will choose b. This belief is consistent if 1 believes that 2 believes that 1 will choose β so that b is a best reply for player 2. Similarly, the belief of player 1 that 2 believes that 1 will choose β is consistent if 1 believes that 2 believes that 1 believes that 2 will choose b and so forth. Thus, Nash equilibria are always rationalizable. However, one can show that γ is also a rationalizable strategy even though it is not part of a Nash equilibrium. γ is optimal for 1 if he believes 2 will choose a. That belief is consistent if 1 believes that 2 believes that 1 will play α so that a is a best reply. Now that belief is consistent if 1 believes that 2 believes that 1 believes that 2 will choose c so that α is a best reply. Finally, if 1 believes that 2 believes that 1 believes that 2 believes that 1 will play γ then c is a best reply and we have a cycle of (γ − a − α − c). By repeating this cycle we have a consistent set of beliefs which makes γ rationalizable. Actually, all the strategies in that cycle can be rationalized by a set of beliefs generated by that cycle. Thus, each strategy in this game is consistent with some basic premise concerning rational behaviour.

figure 1430figure 1430

Non-cooperative Games, Fig. 3

In this light, we gain a better idea of what the Nash equilibrium concept actually demands. It is not only a restrictions on strategies but also on beliefs. It requires that strategies be best responses to some set of conjectures and that these conjectures about other players’ strategies be fulfilled in equilibrium. In a game without preplay communication, such a restriction on beliefs is by no means natural. On the other hand, rationalizability opens up a much wider set of possible outcomes and thus makes it difficult to come to a conclusion concerning behaviour. Since players themselves are faced with the same problem, they may resort to Nash equilibria as a focal point, as defined by Schelling (1960). On this basis, Nash equilibrium regains some of its appeal as a solution concept for non-cooperative games.

See Also