JOURNAL OF ECONOMIC THEORY 21, 1-9 (1979) Equilibrium in Supergames with the Overtaking Criterion* ARIEL RUBINSTEIN Department of Economics, The Hebrew University, Jerusalem, Israel Received October 17, 1977; revised September 14, 1978 . 1. INTRODUCTION There are significant differences between the situation of players under- taking to play a single game, and players who know that they will play the same game repeatedly in the future. Strategy in the first case is a single play; in the second, it is a sequence of rules, each one of which designates the play at the corresponding game and may pertain to the outcomes preceding. The preferences of the participants are determined partly by temporal considera- tions, and the participants may adopt "risky" strategies, "protected" by threats of retribution in the future. A finite sequence of identical games is an inadequate model for examining the idea of repeated games, as is shown by the following analysis. (For a detailed analysis, see[llj). If the number of games is finite and known ini- tially, the players will treat the last game as if it were a single game. Thus the threats implicit in the game before last are proven to be false threats. There- fore the game before last will be treated as a single game, and so on. Thus the situation we wish to describe is not expressed by such a sequence. In order to avoid "end-points" in the model, we define a supergame. A supergame is an infinite sequence of identical games, together with the players' evaluation relations (that is their preference orders on utility sequences). Obviously the assumption of an infinite planning horizon is unrealistic, but it is an approximation to the situation we wish to describe. The literature mainly compares the equilibrium concepts in supergames and singIe games (see Aumann [l-5]). Other papers emphasize the uses of the concept of supergames in economies ([S-lo]). In most of the papers, it was assumed that the participants evaluate the utility flows according to the criterion of the limit of the means of the flows (but see [8].) The drawback of this evaluation relation is that it ingores any finite time interval. The aim of this paper is to extend the discussion to super- games with evaluation relations determined according to the "overtaking * I wish to thank Professor Peleg for his advice and guidance. 1 OO22-0531/79/040001-09$02.00/0 Copyright 0 1979 by Academic Press, Inc. All rights of reproduction in any form reserved. 2 ARIEL RUEIINSTEIN criterion". (The sequence (at}& is preferred to the sequence {bt}& if 0 < lim CF=,a, - b, .) The formal model, described in Section 2, is taken from Roth.' The single game is given in strategic form (see [5]). Let n be the number of players in the game. A (Nash) equilibrium in the supergame is an n-tuple of supergame strategies such that no player on his own can deviate profitable from his strategy. A stationary equilibrium is an equilibrium which, if adhered to by all players, will produce identical outcomes for every game played. The stationary equilibria will be charac- terized in Section 3. The "power" of the threats makes possible the existence of many equili- brium points, some of which may satisfy further requirements. An equilibrium will be called perfect if after any possible "history", the strategies planned are an equilibrium. In other words no player ever has a motivation to change his strategy. This will be treated in Section 4, where it is shown that the requirement of perfection alters the outcomes of stationary equilibria only "marginally". The result corresponds to similar results obtained in [6] and [13] for the limit of the means criterion, and in [IO] for a model of altruistic behavior. Together, these results give the impression that the concept of perfection does not enable the isolation of a small solution set, from the Nash equilibria. In [13, 141 an example is given to demonstrate that perfection is a significant notion considering strong equilibria in supergames where the evaluation relations are according to the overtaking criteria. 2. THE MODEL The single game G is a game in strategic form The set of players is N = (i,..., n}. For each i E N, the set of strategies of i is Si ; Si is assumed non-empty and compact. Each player i has a payoff function 7~~: S -+ W(W - the reals), which is continuous in the product topology. Given u ES, a payoff vector is the n-tuple VT(U)= (~~(a)a)). For convenience we will denote the n - I-tuple (ul ,..., udml, u~a,> by u-i, and the n-tuple u by (u-i, ai). u will be called a (Nash) equilibrium if for all i and for all s, ES, , ~$(u-~, si) < Quj. 1 I wish to thank Professor A. E. Roth for permitting me to use the model described in [12]. EQUILIBRIUM IN SUPERGAMES 3 If the set of strategies is finite and it is possible to adopt mixed strategies, we can identify S+ with the set of mixed strategies, and rri with the expected payoff of i. Examples in a similar context may be found in [8] and [9]. The supergame, G" is (G, >?.a 9 where fi(l) ESi , and for t 3 2, fi(t) : I$:: S(j) -+ Si . Thus a supergame strategy is a choice of strategies at every stage, where each choice is possibly dependent on the outcomes of the preceding games, and where all players know all the choices made by every player in the past. The set of supergame strategies of i will be denoted by Fi , F is the set of n-tuples of strategies; F = I-I;-, F< . GivenfE F, the outcome at time t will be denoted by a(f)(t), and is defined inductively by We will define a relation qi on F, induced by )3t"l byf -', andf by (f -i,h). f EF is stationary if there exists u ES such that for all t, u(f)(t) = u. If f o F is stationary we will denote the corresponding u by S(f). Note that, in contrast with definitions appearing elsewhere in the literature, the stationary strategies produce constant outcomes (as in [12]). f EF is a (Nash) equilibrium in the supergame G" if for all i, and for all hi E Fi ,f = ui I yij if there exists T < t - 1 such that s(l) "fxt>Ml) ***s(t - 1)) = s(T - 1) = u and s-j(T) = u-i and s,(T) # ui . ui otherwise. Then S(f) = u and it is obvious that f is a G* equilibrium. Let f EF be a stationary equilibrium. Denote 6(f) = u. Suppose that a is not a strongly forced outcome. Then there exists i E N and di ESi such that ~~(u-~, di) > am, and for any r E S there is di(r) E St such that vri(rri, d<(r)) > 7ri(u). Now define gi EFi gi(t + W(l) es- s(t)> = d,(f(s(l) *-as(t)>>. Clearly f -=&(f-i, gJ. 6 ARIEL RUBINSTEIN Remark. Consider the following payoff matrix of a two-players game: l,o l,o !- 2,0 0, 2 0,2 2,0 As has previously been mentioned, by identifying mixed strategies and the expected payoff with Si and ni, matrix games are covered by the theory so far. The strategy (0, l/2, l/2) for the row player and (l/2, l/2) for the column player is an equilibrium in the single game, and therefore the outcome is strongly forced. Thus it is a stationary outcome of an equilibrium in supergame, according to our definition of equilibrium. Some alternative definitions are possible in the spirit of [I]. Thus a possible definition is an n-tuple supergame's strategies f is an equilibrium if there is no i andji such that i's payoff sequence resulting from adoption of (j--$,h) if preferable with probability 1 to the expectation sequence resulting from adoption of J We will now show that ((0, l/2, l/2), (l/2, l/2)) is not a stationary outcome of an equilibrium in this second definition. Let f~ F satisfying S(f) = ((0, w, w w, W). The row player may deviate according to the following rule: (i) he plays (0, l/2, l/2) until time T when the total payoff he has accumulated is T + 1, (ii) he then deviates and plays (1, 0, 0), then the probability of such a T occurring, is 1. Since the row player's evaluation is according to the over- taking criterion, his payoff sequence will be preferable with probability 1 to that obtained had he not deviated. 4. PERFECT EQUILIBRIA The definition of equilibrium given in Section 2 was shown to be too general in Section 3. One possible restriction is that a deviation will prove unprofitable to a player at all stages of the game, and not only at the beginning. Given f o F and r(l),..., r(T) ES, the n-tuple of strategies determined by f after a "history" r(l),..., r(T) is denoted byfjr(l),.,.,s(T); thus u-l&).....r(T))i(~>MlL s(t - 1)) =J;(T + t)(r(l) ,..., r(T), s(l) ,..., s(t - 1)). EQUILIBRIUM IN SUPERGAMES 7 DEFINITION. f EF is a perfect equilibrium point if for all r(l),..., r(T) E S, f lru),...,,.o) is an equilibrium. Aumann and Shapley [6] and Rubinstein [13] proved that in a supergame with evaluation relations determined by the limit of the means criterion there is a perfect stationary equilibriumfE F such that B(f) = u iff u is a weakly forced outcome. But not every strongly forced outcome is the outcome of a perfect stationary equilibrium in a supergame, where all players have evaluation relations according to the overtaking criterion. Consider the following matrix game where S1 = {A, , A,}, and S, = {B, , B, , B,}(mixed strategies are not allowed). vI=Oandv,= 1. (A, , BJ is a strongly forced outcome, but is not an outcome of a perfect stationary equilibrium; for if CI; ,fJ EF is a perfect stationary equilibrium such that S(fi ,fi) = (A, , B,), then for all s(l),..., s(t) ES, $a + l)W,..., 4 iffi(t + l)(s(l),...,s(t)) = 4 s(t)) = /B, iffI(t + l)@(l),..., s(t)) = AZ But then the row player can profitably alter his strategy by fi = A, , with a utility flow (1, l,...) xz (2, 2,...). PROPOSITION 4.1. In the supergame (G, x1 where -==Cr are evaluation relations according to the overtaking criterion, and s E S satisfies vi < nri(s) for all i, there exists f EF, a stationary perfect equilibrium such that 8(f) = s. Proof. The idea is to construct f EF such that a player deviating from the stationary position, or the punishing strategy of another player, will be punished sufficiently to eliminate his "profit". After punishment, the players return to the stationary position. By assumption, there exist yi such that maxtasi T&-', ti) = n@) < 7ri(s) (y" is strategy punishing i; the i'th component of y* is i's optimal defense strategy). We write Li = ITS - rnax+t. ri(yfwi, ti) > 0. Li is the punish- ment i will receive every time the punishing strategy yi is employed against him. We will write Rc = max,,~s,vl.,.v -t (maxt,ESj dfi , r-9 - d% 4s) - 8 ARIEL RUBII'fSTEIN z-&)} 3 0. Ri is the maximal relative profit a player i can gain by deviating from one of the n + 1 single game strategies deployed inf, and by bringing to an end the punishment of another player. We will now define m&(l),..., s(t)) and h(t + l)(s(l),..., s(t)) inductively as follows: s(t)) is the length of time a player will be punished for participating rni(D) = 0 fi(l) = si . M(l),..., s(t + 1)) = [ I % + 1 if for all j, mi(s(l),..., s(t)) = 0, si(t + 1) # ui and z s-yt + 1) = u-i. (1) [ mi(s(l),..., s(t)) . Ri Li I + 1 if there exists j # i such that mj(s(l),..., s(t)) > 0, si(t + 1) # y( and +(t + 1) = yj-$. (2) miW),.-, s(t)) - 1 if m&(l),..., s(t)) > 0 and +(t + 1) = yimi. (3) 0 otherwise. (4) It is clear that for all s(l),..., s(t) ES, the number of players i for whom %(Jf1)9*-*, s(t)) > 0 is at most 1. Thus we can defme Clearly f is stationary and S(f) = s. Let r(l),..., r(T) ES, and let f=flr(r)We will show that 7 is an equilibrium. Let hi EF~ ; we will prove that fxi (Fi, hi). It is sufficient to show that if there exists t,, such that ~~(a(J?(r,o(f-~, h,)(Q), then there exists to < tl such that l&t, ri(df)(t>) 3 CL, ri(@, hs)(t)). We will denote mi({u@i, hi)(t)}&') by mi . Player i cannot profitably deviate from yi since n,(ri) = maxtiESi ri(yi-', ti). Therefore mi = 0. If mj = 0 for allj, we will define tl = to + [R,/L,] + 1; for all t, < t < f1 , o-*(F", hi) = yi-*, thus EQUILIBRIUM IN SUPERGAMES 9 If mj > 0, we will define t, = to + (mi * R,/L,) + 1; for all to < t < t, , &(fi, hi) = yiei, and thus < m& - ( [TL+] + 1) L; < 0. z Remark. Similarly we can prove that if so,..., sk-l E S satisfy ai < (l/k) Cfzi ni(si> for all i, then there exists a strategy f which is a perfect equilibrium such that o(f)(t) = ?trnod k). Let s E S be a strongly forced outcome such that for any player j who can profitably deviate from s (i.e. there exists tj E Sj such that 'IT~(s-~,tj) > rj(s)) there exists w E Convrr(S) such that wi > ai for all i and nj(s) > wj . Then there existsfe F, a perfect stationary equilibrium, such that 6(f) = s. REFERENCES 1. R. J. AUMANN, Acceptable points in general cooperative n-person game, in "Contri- butions to the Theory of Games," (A. W. Tucker and R. C. Lute Eds.) Vol. IV, pp. 287-324, Annals of Math. Studies No. 40, Princeton Univ. Press, Princeton, N.J., 1959. 2. R. J. AUMANN, Acceptable points in games of perfect information, Pacific J. Math. 10(1960), 381-417. 3. R. J. AUMANN, The core of a cooperative game without side payments, Trans.Amer. Math. Sot. 98 (1961), 539-552. 4. R. J. AUMANN, A survey of cooperative games without side payments, in "Essays in Mathematical Economics in Honor of Oskar Morgenstern," (M. Shubick, Ed.), pp. 3-27, Princeton Univ. Press, Princeton, N.J., 1967. 5. R. J. AUMANN, Lectures on game theory, Stanford University, 1976. 6. R. J. AUMANN AND L. SHAPLEY, Long term competition-A game theoretic analysis, unpublished manuscript, 1976. 7. W. A. BROCK, An axiomatic basis for the Ramsey Weizsacker overtaking criterion, Econometrica 38 (1970), 927-929. 8. J. W. FRIEDMAN, A noncooperative equilibrium of supergames, Internat. Econ. Rev. 12(1971), 1-12. 9. M. KURZ, Altruistic equilibrium, in "Economic Progress, Private Values, and Public Policy: Essays in Honor of William Fellner" (B. Balassa and R. Nelson, Eds.), pp. 177-200, North-Holland, Amsterdam, 1977. 10. M. Kuaz, Altruism as an outcome of social interaction, Amer. Econ. Reu. 68 (1978) 216-222. 11. R. P. LUCE AND H. RAIFFA, "Games and Decisions," Wiley, New York, 1957. 12. A. E. ROTH, Self supporting equilibrium in the supergame, unpublished, 1975. 13. A. RUBINSTEIN, "Equilibrium in Supergames," Research Memorandum No. 25, Center for Research in Math. Economics and Game Theory, The Hebrew University, Jeru- salem, May 1977. 14. A. RUBINSTEIN, Strong perfect equilibrium in supergames, unpublished, 1978.