Repeated Games Without Public Randomization

Repeated Games Without Public Randomization: A Constructive Approach Abstract We study discounted infinitely repeated games with perfect monitoring and without public randomization. Both symmetric and asymmetric discounting cases are considered; a new geometric construct called ‘self-accessibility’ is proposed and used to unify the analyses of these two cases. For symmetric discounting, our approach leads to easy computability of a discount factor bound needed to support a specific payoff vector in equilibrium. When discounting is allowed to be asymmetric, we show that any payoff vector that is in the interior of the smallest rectangular region containing the pureaction payoffs is realizable in the repeated game. Next, an easily-verifiable condition, ‘strict diagonalizability’, is offered as a sufficient and almost necessary condition for a payoff vector to be an equilibrium payoff for some discount factor vector. ‘Turnpike strategies’ that support a target payoff are explicitly constructed. Our results thus encompass and generalize Fudenberg and Maskin (1986, 1991). 1 Introduction The pioneering work of Fudenberg and Maskin (1986), hereafter FM 1986, demonstrated that provided the players are patient enough, any FSIR (feasible and strictly individual rational) payoff vector for a game may be supported as the discounted average of payoffs arising from an SPNE (subgame perfect Nash equilibrium) of the corresponding repeated game. Two of the assumptions made in the original FM 1986 paper are of concern to us; the first is the availability of a public randomization device (hereafter PRD) and the second is the assumption that all players have exactly the same discount factor. Dispensing with PRDs is not a minor addendum because it is problematic to argue that all players have access to a correlating device fine enough to realize all FSIR payoffs. While, following Aumann and Maschler (1995), communication can be used to construct ‘jointly controlled lotteries’ that serve as correlating devices, in the industrial organization context, this might run foul of antitrust regulations that forbid communication among firms. Similarly, requiring exact equality of discount factors seems too restrictive; if we allow economic agents to have differential preferences over consumption bundles, why should we require them to hold identical time preferences?1 Lehrer and Pauzner (1999), hereafter LP 1999, have asserted that even when payoffs are monetary and players can borrow in an outside market to smooth their consumption streams, different agents, because of their differential financial standings, may be subject to different interest rates. Finally, it is odd to argue against the importance of asymmetric discounting in complete information games when the literature on incomplete information games is rife with such models. A plethora of interesting and counterintuitive things happen as soon as one disallows PRDs, even when players are patient. For example, in the symmetric discounting case Yamamoto (2010) shows that for large enough common discount factors, the set of SPNE payoffs can be non-convex and non-monotonic with respect to the common discount factor. Salonen and Vartiainen (2008) show that for large enough but unequal discount factors the feasible payoff set of the repeated game can be totally disconnected,2 and the Pareto frontier function can be everywhere discontinuous. For a class of two-player finite games, Olszewski (1998) shows that the undiscounted folk theorem does not hold. To establish whether a given point in the payoff space is an equilibrium payoff vector when PRDs are unavailable, the first question that must be answered is: Is this payoff feasible in the repeated game using uncorrelated (but possibly mixed) actions? If this is answered in the affirmative, the second question is: Is this an equilibrium (SPNE) payoff? To fix terminology, we shall henceforth call these questions those of realizability and supportability respectively. In the context of symmetric discounting, Fudenberg and Maskin (1991), hereafter FM 1 See for example Harrington (1989), Obara and Zincenko (2017) and Haag and Lagunoff (2007) who provide interesting economic models with asymmetric discounting, the first two in the context of pricesetting oligopolies, and the last in the context of collective effort-expending games. 2 A set is totally disconnected if any connected subset of it must be either empty or a singleton. 1 1991, was the first paper to prove a folk theorem without public randomization. They start by addressing realizability and provide a lower bound for discount factors such that any point in the feasible set is representable as the discounted average of an infinite sequence of its vertices. This result goes by the name ‘Sorin’s lemma’ as Sylvain Sorin (1986) had first analyzed a similar representation. Going from realizability to supportability requires work; as the standard text of Mailath and Samuelson (2006) notes, “The difficulty is that some of the continuation values generated by these sequences may fail to be even weakly individual rational.” In trying to address this issue FM 1991 relies on complex as well as non-constructive arguments to build on top of Sorin’s result which in the end, delivers strategies to support a specific payoff vector (like FM 1986), but is unable to yield a computable discount factor bound (unlike FM 1986).3 Our key contribution is to use the the recursion-based notion of self-accessibility to address both realizability and individual rationality simultaneously. A set of payoffs is self-accessible for a discount factor vector if, for any point in the set, there is a pure action that can be played such that the induced continuation payoff also lies in the set. In the case of symmetric discounting we show that closed balls of small enough radii strictly inside the FSIR set are self-accessible for discount factors above a bound that can be explicitly computed using a simple nonlinear program. This insight enables us to strengthen and offer a simpler yet completely constructive argument of the FM 1991 folk theorem.4 Why might knowing a discount factor bound be important? From a practical standpoint, the whole argument of repeated interaction being a prime motivator behind cooperation among otherwise selfish individuals is much more plausible when the required discount factor bound is, say, .7 rather than .9999. From a theoretical standpoint, even when we know that the set of equilibrium payoffs approaches the FSIR set as the common discount factor increases, it is of some interest to know if the approach is fast enough.5 The first paper to systematically study the asymmetric discounting case was LP 1999. They noted that in this setup, unlike in the symmetric discounting case, as the players become increasingly patient, a) realizable payoffs may lie outside the stage game feasible set and b) the limiting set of supportable payoffs could be very different from the FSIR set. However, they only analyze 2-player games, require fixed ratios of log discount factors, and their arguments crucially rely on existence of PRDs. They conjecture that it might be possible to remove this last restriction using techniques similar to those in FM 1991; however, we show by a simple counterexample that the building block of the FM approach, Sorin’s Lemma does not hold in this situation. In the same setting as that of LP, but with possibly more than two players, Chen and Takahashi (2012) show how a sequence of action profiles can be supported in equilibrium if all its continuation payoffs are uniformly 3 As an example of a non-constructive argument, consider covering a compact set S with an infinite collection of open balls and then choosing some characteristic of the finite subcover of S that is guaranteed because of compactness. But then, how does one figure out which finite subcover will do the job? 4 Although the strategies we use are very similar to the ones used in FM 1991, one of our innovations is to design a punishment phase that does not become arbitrarily long as players become arbitrarily patient. 5 A recent paper, Hörner and Takahashi (2016) analyzes this issue comprehensively for the first time. 2 bounded away from minmax values. However, without PRDs, only an ‘approximate’ folk theorem is obtained; the question of realizability is not tackled either.6 Repeated games with imperfect public monitoring are often studied using ‘self-generation’, a technique originally advanced in Abreu, Pearce, and Stacchetti (1990), and subsequently extended by Fudenberg and Levine (1994) and Fudenberg, Levine, and Maskin (1994).7 Making use of this notion, Sugaya (2015) extends LP 1999 to prove a comprehensive folk theorem that applies to any finite number of players, perfect and imperfect public monitoring and possibly asymmetric discounting while dispensing with PRDs.8 He too, works with discount factor vectors exhibiting fixed ‘relative patience’, specifically assuming that pairwise ratios of discount rates 9 are either constants or are converging to constants. He shows that for this setting, as players become more ‘absolutely patient’, the limiting sets of sequentially individually rational payoffs10 and equilibrium payoffs are identical; however his methods does not help us compute either of these sets. This places the folk theorems for repeated games with asymmetric discounting on a very different footing from those with symmetric discounting. One way these theorems inform the applied economist is by ruling out impossible payoffs when rational agents interact repeatedly without him having any knowledge of the exact nature of discounting used by these agents. Hence, if we cannot describe the potential equilibrium set11 in terms of the stage game parameters, the existing results have not fulfilled that role. To elaborate on this point, let F be the set of feasible payoffs in the stage game, and let F ` be the subset of F where each player receives at least his individual rational payoff. Assume that this set is full-dimensional. Next, in the infinitely repeated game without PRD’s, for a discount factor vector δ, let Fpδq denote the set of realizable payoffs and Vpδq the subgame-perfect equilibrium payoffs. Letting D be the set of discount factor vectors Ť where all players discount at the same rate, Sorin’s lemma gives us F “ δPD Fpδq, while Ť the Folk Theorem of FM 1991 gives us F ` « δPD Vpδq (here A « B means that the sets A and B have zero Hausdorff distance between them). The following diagram then captures some of the inter-connections (with all subset relations being generally improper): Vpδq « F ` Ą δPD Ť δPD Ą Ť Fpδq “ 6 F Chen and Fujishige (2013) shows that the set of realizable payoffs in a finitely repeated game with unequal discounting is monotonically increasing in the length of the horizon. 7 The difference between self-generation and self-accessibility is that while the former addresses realizability and supportability simultaneously, the latter addresses only realizability (but with individualrationality). This decoupling is actually helpful as the rest of the paper demonstrates. 8 See also Hörner and Olszewski (2005) who prove a folk theorem for almost-perfect private monitoring without using a PRD, though their results do not encompass unequal discounting. 9 If δi is the i-th player’s discount factor, his discount rate is 1{δi ´ 1. 10 These are payoffs obtained via paths where each period each player’s continuation payoff is at least his minmax payoff. 11 By this we mean the set of payoffs that are equilibrium payoffs for some discount factor vector. 3 Allowing for asymmetric discounting, thanks to LP, we know that for 2-player games, neither the first nor the second horizontal relation holds (with PRDs though). Also, letting F ` pδq denote the set of sequentially individual rational payoffs for a given δ, thanks to Ť Ť Sugaya we know that for n-player games, δPD1 Vpδq « δPD1 F ` pδq for certain subsets D1 Ă p0, 1qn that fix discount rate ratios. However, we do not know what those two sides of the (approximate) equality sign are. What is going on with asymmetric discounting is that there are sets V and R such that the following hold: Ť Vpδq Ť δPp0,1qn Fpδq Ą Ą F` Ą δPp0,1qn Ą F ` pδq « V « Ť Ą F` “ « V “ δPp0,1qn « R Ą F This paper, for the first time allows explicit construction of the sets V and R. As for R (i.e. the set of potentially realizable payoffs), we show that in the repeated game, players can simultaneously obtain essentially anything they can individually get in the stage game. Although this was foreshadowed by LP’s work, the paths that we design to realize target points are more versatile than the ones considered by LP in that they do not force continuation payoffs to eventually settle on one of the vertices of F ; in fact, they can eventually be made to stay close to any point in the interior of F . Next, we offer necessary and sufficient conditions for payoffs to be supportable. These conditions, respectively referred to as the weak and strict diagonal conditions, describe V , a set that we show can be constructed by solving certain linear programs. As in the case of symmetric discounting, for general discounting, not only does one wish to identify the potentially supportable set, but one also wishes to know how (i.e. using what strategies) a specific payoff vector can be supported. Unfortunately, the existing literature has been silent on this question.12 In contrast, we explicitly construct the equilibrium path and strategy profile to support a target payoff vector. The strategies we propose for supporting points in V (but outside F ` ) are best described as ‘turnpike strategies’ for the following reason: The equilibrium path consists of two phases: a finiteperiod turnpike phase when the continuation payoffs are outside the FSIR set and an infinite-period post-turnpike phase when they are inside. If a deviation takes place on the turnpike phase, after punishing the deviant, play returns to the point on the turnpike phase where the deviation took place and continues on the turnpike phase while rewards to the punishers for compliance are offered in the non-turnpike phase only. The paper is structured as follows. In the next section, we formally introduce the model and notation, define self-accessibility and briefly explain its significance. In section 12 Sugaya, relying on fixed point arguments in the payoff space does not provide equilibrium paths or strategies while LP and Chen-Takahashi assume that we are already given an equilibrium path that is sequentially individual rational and only then construct an equilibrium strategy to support such a path. 4 3, a numerical example is discussed to illustrate the constructive nature of our arguments and present the flavor of some of our findings. Section 4 analyzes self-accessibility when discounting is symmetric and presents a constructive extension of FM 1991. Section 5 discusses self-accessibility in the asymmetric discounting case and explores the supportability of payoffs within the interior of the FSIR set. Section 6 addresses the issue of realizability in the asymmetric discounting case outside the feasible set. Section 7 defines weak and strict diagonalizability and shows how these conditions relate to supportability of payoff vectors outside the FSIR set. Section 8 concludes. All proofs are collected in an appendix.13 2 Preliminaries 2.1 Notation and The Model We consider a standard infinitely repeated game of perfect monitoring with possibly unequal discounting. At each t P t0, 1, 2, . . .u the (finite) stage-game G “ hI; pAi qi ; pgi qi i is played, where I “ t1, . . . , nu is the set of players, Ai is player i’s finite set of actions, Ś A :“ i Ai is the set of all pure action profiles, and gi : A Ñ R is player i’s (vNM) payoff function. A mixed action of i is αi P 4Ai , where for any set S, 4S denotes the set of all probability distributions on the set S. Let aptq P A be the (realized) action profile played at time t.14 When player i discounts future payoffs using the discount factor δi , his average discounted utility defined over the infinite sequences of pure actions is 8 ! )8 ´ ¯ ÿ ui p aptq q :“ p1 ´ δi q δi t gi aptq . t“0 t“0 Under perfect monitoring the public history at the end of period t is ht “ pap0q , . . . , aptq q P At`1 . A pure strategy of i is a sequence of maps si pt ` 1q : H t Ñ Ai pfor t “ ´1, 0, 1, . . .) where H t denotes the set of histories at the end of period t (with the convention that H ´1 is the empty set). Mixed stategies are analogous, except that they map to the corresponding mixed actions 4Ai . This formulation implies that strategies cannot be conditioned on anything other than the history of actions actually played; in particular, there is no publicly observable random variable on whose realized value actions may be conditioned, and mixed actions are not observable; only their realizations are. 13 It is worth remarking that although our main objective is to investigate the case of asymmetric discounting without public randomization, the results in Section 4 are not secondary to that goal; both the statement and the proof of the main result in Section 5 depend on the results we prove in Section 4. Similarly, even though we will eventually characterize the entire (possible) equilibrium set in Section 7, to prove those results we first need to establish the ‘partial folk theorem’ that is obtained in Section 5. 14 In what follows vectors are boldfaced while scalars and sets are not. Sequence indices are denoted by superscripts and sometimes they are enclosed in parentheses to distinguish them from exponents or from another sequence denoted by the same letter; for example, cl denotes the l-th vertex of a polytope C, while tcptq u denotes an infinite sequence of vertices each element of which is a cl for some l. Coordinates of vectors are denoted by subscripts. 5 This describes the repeated game G8 pδq, with the discount factor vector δ “ pδ1 , . . . , δn q. In the special case where each player uses the same discount factor δ, we denote the game as G8 pδιq15 . As in Section 1, we use Fpδq, F ` pδq and Vpδq to denote the set of realizable, sequentially individual rational and supportable payoff vectors in the repeated game. Let C “ gpAq. player i’s minmax value is wi :“ minα´i PŚj‰i p∆Aj q maxai PAi gi pai , α´i q, Ś Let mi P nj“1 p∆Aj q be the profile that minmaxes player i, with the latter playing a best response. Whenever it is convenient to do so, we will assume without loss of generality that wi “ 0 for all i. The feasible set is F :“ copCq (convex hull of C), the feasible and weakly individually rational (FWIR) set is F ` :“ tx P F | xi ě wi @i u and the feasible strictly individually rational (FSIR) set is F ˚ :“ tx P F | xi ą wi @i u. The lower boundary of F is BF :“ tx P F : Ey P F such that y ăă xu. We let M “ maxi t|gi paq| : a P Au; with w “ 0, when F ˚ is full-dimensional, this is strictly positive. For later use, we recall the definitions of a few geometric terms. The affine hull of a set X Ă Rn is ˇ # + k k ˇ ÿ ÿ l lˇ l l λ x ˇ x P X, aff pXq :“ λ “ 1, k P N . ˇ l“1 l“1 For x P X, the affine (closed) ball with center x and radius r is BX px, rq :“ ty P aff pXq : d py, xq ď ru, while Bpx, rq denotes the usual (closed) ball in Rn . The relative interior of X is relintpXq :“ tx : D r ą 0 such that BX px, rq Ă Xu. When X “ copCq, where C “ tc1 , . . . , cL u, and every point in C is an extreme point of X, each point in relintpXq can be expressed!as a convex combination of those ) points with řL l řL l l ˇˇ l strictly positive weights, i.e. relintpXq “ l“1 λ “ 1 . The usual l“1 λ c ˇ λ ą 0, interior of a set S is denoted by intpSq. For any set S Ă Rn , and M Ă t1, . . . , nu, P rojM pSq denotes the projection of S along the coordinates in M . For a finite set C of pure action payoffs in an n-player game, we define the corresponding ‘feasible set’ for players 1, . . . , l (l ď n) as F p1, . . . , lq :“ P rojt1,...,lu F . Note that this is also copP rojt1,...,lu pCqq. Finally, we introduce a new terminology: the rectangular hull of a bounded set S in n R , denoted as repSq is the smallest closed rectangle that contains S. Formally, # repSq :“ č R RPR 2.2 where R “ n n ź ź rai , bi s : ai ď bi , rai , bi s Ą S i“1 + . i“1 Self-accessibility We now define self-accessibility, for possibly unequal discounting and explain its usefulness. Definition. Let C Ă Rn be a finite set. A set S Ă copCq is said to be self-accessible relative to C for a vector δ “ pδ1 , . . . δn q P r0, 1qn if for any x P S there exists y P S and c P C such that xj “ p1 ´ δj qcj ` δj yj for j “ 1, . . . , n. 15 ι is a vector of 1’s, while ei , to be used later, is the i’th unit vector. 6 The definition is particularly intuitive for equal discounting. For some x P S Ă copCq, suppose that we can find c P C, y P S and δ P r0, 1q such that x “ p1 ´ δq c ` δy; this is a ‘dynamic programming decomposition’ of the target payoff x, with the restrictions that the current payoff c is generated by a pure action profile and the continuation payoff y lies in the set S itself. If there is a uniform δ P r0, 1q for which any point x P S can be written as the p1 ´ δ, δq convex combination of a pure-action payoff and a continuation payoff within the set itself, then S is self-accessible for δ “ δι. To see the usefulness of the notion with an arbitrary discounting structure, let S Ă copCq be self-accessible for δ and let x P S. It follows that there exists cp0q P C such that p0q xj “ p1 ´ δj qcj ` δj yj1 for each j where y 1 is also in S. Because of the latter, we can p1q write yj1 “ p1 ´ δj qcj ` δj yj2 for each j for some c1 P C and y 2 P S. By induction there is a sequence of vertices tcptq utě0 such that xj “ p1 ´ δj q τ ÿ ptq δjt cj ` δjτ `1 yjτ `1 @j, @τ. t“0 Since δj ă 1 and S is bounded, we have k δjτ `1 yjτ `1 kÑ 0 as τ Ñ 8. Hence any point x in ř ptq a self-accessible set S has a representation xj “ p1 ´ δj q tě0 δjt cj . Thus, any point lying in a set that is self-accessible for a given δ vector can be represented as the coordinate-wise discounted average of a sequence of pure action payoffs for that δ vector.16 3 A Numerical Example In this section we present a numerical example to a) underscore the computational advantages of supporting a specific payoff vector using self-accessibility with symmetric discounting and b) preview our results on asymmetric discounting. Although the general results presented later are valid for any n-player stage game with a full-dimensional FSIR set, in order to abstract away from ancillary issues, we choose an asymmetric version of the Prisoner’s dilemma game. 3.1 Supporting the Nash Bargaining Point with Symmetric Discounting Each of two players simultaneously choose one of two actions (A) and (N) with the payoff matrix displayed below. A N A ( 4, 2) (9, 0) N (0, 7) ( 5, 5) Henceforth, we refer to the payoff vectors p4, 2q, p9, 0q, p5, 5q and p0, 7q as c1 , c2 , c3 16 To make this sequence well-defined, when a point in S can be decomposed in more than two ways, we can use some pre-assigned arbitrary ordering among the vertices to decide which current action to choose. 7 and c4 respectively. The unique dominant strategy equilibrium (A,A) is inefficient. The (efficient) Nash Bargaining payoff vector (where the set of possible agreement payoffs is the feasible set and c1 is the disagreement point) is n “ p5.700, 4.125q, which is a convex combination of c3 and c2 with weights .825 and .175 respectively (see Figure 1). We will like to obtain this payoff vector in an SPNE. 7 c4 6 c3 l n 5 4 r 3 2 c1 1 c2 1 2 3 4 5 6 7 8 9 Figure 1: Realizable Payoffs in an Asymmetric Prisoner’s Dilemma Game Let us first examine the realizability of n. Choose a one-dimensional closed ball S Ă coptc2 , c3 uq containing n, with extreme points l and r (l being closer to c3 ). Let l “ λp5, 5q ` p1 ´ λqp9, 0q “ p9 ´ 4λ, 5λq and r “ µp5, 5q ` p1 ´ µqp9, 0q “ p9 ´ 4µ, 5µq with the requirements 1 ě λ ě .825 and 0 ď µ ď .825 (3.1) to ensure that S contains n. We shall find a cutoff δ above which S is self-accessible (relative to tc2 , c3 u). Any x P S can be written as θp5, 5q ` p1 ´ θqp9, 0q “ p9 ´ 4θ, 5θq, with µ ď θ ď λ. Let δpx, c3 q be the lowest value of δ in r0, 1s such that x “ p1 ´ δqc3 ` δy for some point y P S. Since the farthest continuation payoff within S is r, δpx, c3 q solves x “ p1 ´ δqc3 ` δr “ p1 ´ δqp5, 5q ` δp9 ´ 4µ, 5µq, and therefore δpx, c3 q “ p1 ´ θq{p1 ´ µq. Similarly, define δpx, c2 q as the the lowest value of δ in r0, 1s such that x “ p1 ´ δqc2 ` δy for some point y P S; using an analogous argument this is seen to be θ{λ. If the discount factor δ is at least as much as δ ˚ pxq :“ mintδpx, c2 q, δpx, c3 qu, then x can be attained by playing one of the vertices c2 or c3 with the continuation payoff lying in S.17 Finally, note that the maximum of δ ˚ pxq as x varies over S is achieved for a point x̄ where δpx̄, c2 q “ δpx̄, c3 q, λ . Plugging it in the expression i.e. for θ that solves p1 ´ θq{p1 ´ µq “ θ{λ; hence, θ “ 1´µ`λ 17 More accurately, we mean “...by playing the actions corresponding to the vertices c2 or c3 ...”. Here and elsewhere we indulge in this slight abuse of notation for brevity’s sake. 8 of δpx, c2 q gives δ, a lower bound for the discount factor δ that ensures the self-accessibility of S: 1 . (3.2) δ :“ max δ ˚ pxq “ max mintδpx, c2 q, δpx, c3 qu “ xPS xPS 1´µ`λ When (3.1) and (3.2) hold, any x “ p9 ´ 4θ, 5θq in S can be realized by playing a sequence of actions from the set tc2 , c3 u. For θ ă θ, c2 starts the sequence, otherwise c3 does. Next, to support n, we wish to deter deviation from the prescribed path via a grim trigger strategy à la Friedman (1971): c1 is played forever as soon as any deviation is detected. To this end we note that if the current (on-equilibrium) continuation payoff is given by a θ ă θ, since c2 is to be played next, we need only worry about player 2’s incentive compatibility. This is achieved by the following constraint that ensures that for player 2, receiving the worst payoff in the corresponding region of S (which is 5µ) is at least as good as receiving the best deviation payoff once (which is 2) and then being minmaxed forever: 5µ ě 2p1 ´ δq ` 2δ. (3.3) On the other hand, if the current (on-equilibrium) continuation payoff is given by a θ ě θ, which means the current prescribed action is c3 , we need to deter deviations by both players. Similar reasoning as above shows that player 1’s incentive compatibility requires: 9 ´ 4λ ě 9p1 ´ δq ` 4δ, (3.4) while player 2’s incentive compatibility requires: 5λ ě 7p1 ´ δq ` 2δ. 1´µ`λ (3.5) The minimum δ satisfying (3.1), (3.2), (3.3), (3.4) and (3.5) is .731, and the corresponding ball S is given by λ “ .914, µ “ .547. This suggests that above a reasonable discount factor the Nash bargaining payoff n can be implemented in an SPNE.18 3.2 Expanding Possibilities With Asymmetric Discounting If all players use the same discount factor, any discounted average payoff vector must stay inside the feasible set. What if they do not? Aided by the figure below, we preview some of the results to follow by explaining how they apply in the context of the current example. 18 There is nothing special about the point n; the analysis we just did could be carried out for any (individually rational) point on the Pareto frontier. For instance, Mailath Obara and Sekiguchi (2002) concerns itself with finding a bound for the discount factor that gives one player (say player 1) the highest payoff subject to the other player receiving her individually rational payoff. Since nothing in our analysis disallows the target point to be on the boundary of S, in this case, we will require r to be the point p7.4, 2q and then replacing (3.1) by the following two constraints: λ ě µ and µ “ .4 we could solve the optimization problem as before to find the relevant bound. It works out to be .781. 9 7 c4 6 c3 5 4 3 2 c1 1 c2 1 2 3 4 5 6 7 8 9 Figure 2: Realizable and Supportable Payoffs with Asymmetric Discounting Theorem 3 will later show that any payoff vector in intprepF qq (which in this case is the open rectangle p0, 9q ˆ p0, 7q) can be realized for large enough discount factors if we are allowed to choose the relative patience of the two players by fixing the ratio of their discount rates. Which of these are equilibrium payoffs and for what kind of discount factors? Theorem 5 demonstrates that there are some points in the open rectangle p0, 9q ˆ p0, 7q that can not be supported in equilibrium no matter what the discount factors are. These are points in the small lightly shaded rectangle in the north-east of Figure 2; a payoff vector such as p8.9, 6.9q where both both players receive close to their maximum payoffs is ruled out. On the positive front, Theorem 2 will show that points in the interior of F ˚ (the dotted and darkly shaded region) can be supported in equilibrium for large enough discount factors and arbitrary discount rate ratios. Moreover, using ideas developed in Theorem 6 we can show that if both players are sufficiently patient and player 2 ’s discount rate is sufficiently lower relative to player 1, then it is possible to support points in the open rectangle p4, 9q ˆ p2, 5.4q. The coordinates of this latter rectangle are arrived at by letting player 1’s payoff to range between his minmax payoff (4) and the maximum he can receive in the game (9), whereas player 2’s payoff is allowed to range between his minmax (2) and the maximum he can receive subject to giving player 1 his minmax amount. Analogously, if both players are sufficiently patient and player 1 is sufficiently more patient relative to player 2, points in the open rectangle p4, 7.4q ˆ p2, 9q can be supported (7.4 is the maximum player 1 can receive subject to giving player 2 his minmax amount). Points that are common to both rectangles may be supported by (large enough) discount factors exhibiting a wide variety of relative patience. To summarize then, the dotted region in Figure 2 is the feasible set, points in p0, 9q ˆ p0, 7q are realizable payoffs for some discount factors, while the interior of the darkly shaded region are supportable payoffs for some discount factors. 10 4 The Case of Symmetric Discounting This section discusses how self-accessibility simplifies the arguments of FM 1991’s main result, makes discount factor bounds computable and delivers some new results as well. 4.1 Self Accessibility Under Symmetric Discounting The main building block of the FM 1991 is Sorin’s Lemma which addresses the question of realizability. The lemma states the following: Suppose x P Rn is in the convex hull of C “ tc1 , c2 , . . . , cL u. Then, for all δ ě 1 ´ 1{L there exists a sequence tcptq u8 t“0 in C ř8 t ptq 19 such that x “ p1 ´ δq t“0 δ c . Armed with this result, FM then tackle the problem of ensuring that continuation payoffs stay close enough to the original payoff (so as to maintain individual rationality) via their Lemma 2, which makes critical use of Sorin’s lemma but has a complex argument and offers little computational guidance. Using our terminology, Sorin’s Lemma shows that the entire feasible set is selfaccessible relative to its extreme points for large enough discount factors. However, we can show that for any set of points in Rn , affine balls contained in the relative interior of the convex hull of those points are also self-accessible (for large enough discount factors). When a target payoff is in F ˚ , by placing it anywhere inside a ‘small’ such ball, we can thus achieve both realizability and (sequential) individual rationality in a single step. This approach bypasses the need for Sorin’s Lemma altogether and as a bonus, we can also easily compute a relevant discount factor bound. Proposition 1. Suppose C 1 Ă C “ gpAq is a set of points in Rn where X “ CopC 1 q need not be full-dimensional. Let S “ BX po, rq Ă relintpXq be some affine ball with center o and radius r ą 0. Then D δ P p0, 1q such that S is self-accessible relative to C 1 for any vector δι with δ ě δ. This δ is computable by solving a nonlinear maximization problem with linear/quadratic objective and constraint functions. As this proposition is central to the computability of discount factor bounds, we provide some intuition behind the construction of δ. Fix an affine closed ball S “ BX po, rq in the relative interior of copC 1 q. Take any point x in S. Let δpx, cq be the smallest value of δ P r0, 1s satisfying the dynamic programming decomposition x “ p1 ´ δq c ` δy for some y P S. The geometrical interpretation of this function is as follows: consider the line connecting c and x; it cuts the surface of the ball at two points, one on the same side of x as c and one on the opposite side (they could be same if the line is tangent to the surface). Call this latter point y (y could be x itself). Thus x is a convex combination of c and y with weight δpx, cq on y. It is not hard to find a formula expressing this weight as a continuous function of x. Now we assert that δpx, cq ă 1 for some vertex c. If x is in relintpSq, any vertex 19 Actually the bound stated in this lemma is not tight. Using Caratheodory’s Theorem it can be shown that the exact tight bound is 1´1{m where m “ mintL, n`1u, rather than 1´1{L. Also, in his original 1986 paper, Sorin, using a result from Fenchel (1929) obtains the bound 1 ´ n1 when mixed actions are allowed. 11 c P C 1 works but if x is on the (relative) boundary of S, not all vertices do. However, since S lies in the (relative) interior of the convex hull of C 1 , we can use any point in C 1 that is separated from the ball by the supporting hyperplane to S at x. In the accompanying figure, C 1 “ tc1 , c2 , c3 u and X is the triangular region with those three points acting as vertices (it could be a face of the feasible set). The shaded region is S; x is a point in S. If we try to extend a line from ci to x to the farthest point in S, we reach y i . Here, kx´c2 k kx´c3 k 3 δpx, c1 q “ 1, δpx, c2 q “ ky 2 ´c2 k and δpx, c q “ ky 3 ´c3 k . c1 y3 x y1 c2 y2 c3 Figure 3: How δ ˚ pxq is constructed Let δ ˚ pxq :“ mincPC δpx, cq. For our figure, it turns out that δ ˚ pxq “ δpx, c3 q. Now consider maximizing δ ˚ over S; Weierstrass’s theorem guarantees that the maximum is attained. Since δ ˚ ă 1 throughout, this maximum δ is less than unity and the convexity of S ensures that S is self-accessible above δ. Once the affine ball BX po, rq is self-accessible relative to a set of vertices C 1 for a discount factor vector δ “ δι, as was explained in section 2.2, any vector x in that ball can be expressed as a discounted average of a sequence of vertices from C 1 ; we let taptq px, BX po, rq, δqu8 t“0 denote this sequence. One of the advantages of the self-accessibility approach over the FM 1991 approach is that we are easily able to provide a computable uniform bound on discount factors that guarantees realizability of each point in any geometrically well-described compact set while keeping continuation payoffs within a certain small fixed distance of the original point. Non-constructive arguments involving open covers of compact sets admitting to finite subcovers are not required.20 Extending ideas that are used to prove Proposition 1, our next result shows that we can find a bound on discount factors that makes a collection of balls self-accessible where each has a certain fixed radius (say ω) and a center that lies within a fixed ball with a different radius (say r̄); in Figure 4, these balls are colored dark grey, while the ball within which their centers lie is colored light grey. 20 These uniform bounds become relevant if unobeservable mixed strategies are needed to minmax a player. In such situations, post-punishment plays are not known beforehand; they are calculated based on the realizations of mixed actions during the punishment period. 12 ř řK l l 1 l l Proposition 2. Let x “ K l“1 λ “ 1 and λ ą 0 for each l. Let C “ l“1 λ c with tc1 , . . . , cK u and X “ copC 1 q. Let r̄ ą 0 and ω ą 0 be such that BX px, r̄ ` ωq Ă F ˚ X relintpXq. Then, we can find δ ă 1 such that for any δ P pδ, 1q, any Bpx1 , ωq where x1 P BX px, r̄q is self-accessible relative to C 1 for δ “ δι. Furthermore, δ is computable by solving a nonlinear maximization problem. ω ω x r̄ ω Figure 4: Finding a bound for which a collection of balls is self-accessible 4.2 A Constructive Folk Theorem via Self-Accessibility As soon as we observe that affine balls with small enough radii are self-accessible, there hardly remains any difference between the two problems where we are trying to support a payoff vector with and without PRDs. If, assuming the existence of PRDs, one can find a discount factor bound (say δ 1 ) for which incentive compatibility conditions are strict, then all we have to do in the PRD-less case is to work with small enough balls around points which could potentially be played in the first case, find bounds which will make these balls self-accessible and then we can support the same target payoff vector in the second case using a grand bound which is the maximum of all these bounds and δ 1 . This insight drives the main result of this section which is a fully constructive version of the main result in FM 1991. It differs from the original version in three important aspects. First, because of our reliance on self-accessibility, all paths, whether on or off equilibrium become recursively computable. Second, Propositions 1 and 2 and the fact that our method of proof simplifies incentive compatibility conditions, reducing them to only two linear inequalities, allow us to compute a discount factor bound needed to support a given payoff vector in F ˚ zBF . Third, our proof reveals that the number of punishment periods during which a deviating player is minmaxed need not become arbitrarily large as δ goes to one. While in FM 1991, the punishment length is of the order of p´ln δq´1 , in our proof, we fix it once and for all. Theorem 1. Let F ˚ be full-dimensional and let v P F ˚ zBF . Then, there exists δ P p0, 1q such that for all δ P pδ, 1q there is an SPNE that does not use a PRD and has discounted average payoff v. This bound is computable using the NLPs provided by Propositions 1 and 13 2 and two linear inequalities. All paths, on and off equilibrium, are recursively computable as well. Punishment (minmaxing) period lengths are not δ-dependent. A detailed proof is provided in the appendix for the sake of completeness and also because, the proof applies with little change to a similar theorem in the asymmetric discounting setting. It relies on the standard architecture of equilibrium strategies introduced in FM 1986 characterized in terms of three phases, which is well-understood in the literature. It may be instructive here though to consider what self-accessibility brings to the table that allows us to keep the number of punishment periods δ-independent. To that end, consider the situation where player i has deviated, has been minmaxed, and play now has shifted into the so-called Phase III(i) where players are supposed to receive the (continuation) payoff vector u.21 If one had access to PRD’s, one would prescribe a path where in every period, an action generating u would be played. Without PRDs however, players play a sequence of actions that generates u as a discounted average, while the continuation payoffs stay, say, ε-close to u. But now suppose, after this path is started, at some point, i’s continuation payoff becomes ui ´ ε. Then, if the number of punishment periods is a constant independent of the discount factor, a sufficiently patient i might want to re-start his own punishment by deviating! This is why FM 1991 needs to let the punishment phase become unboundedly large as the discount factor approaches one. In our proof, when Phase III(i) is started, the target payoff is not u, it is u ´ εei , the lowest point (from i’s perspective) in the self-accessible ball Bpu, εq (since there is no requirement that a target payoff must be in its center). Thus the perverse situation described above never arises and δ-independent punishment periods can indeed be devised to wipe out any gain from deviation. Asymmetric Discounting: Supporting Points in intpF ˚ q 5 In this section, we show that any point in the interior of F ˚ is both realizable and supportable provided each player’s discount factor is large enough. In subsection 5.1, we begin by showing that the natural counterpart of Sorin’s lemma in the asymmetric case does not hold which negates Lehrer and Pauzner’s conjecture and makes the FM 1991 approach to the problem inapplicable. We also show that if the discount rate ratios are not fixed, not even small balls are self-accessible (even when the discount factors are large). Hence, to insure self-accessibility for a set S, either we need to keep discount rates fixed or allow S to assume a geometrical shape which is not a closed ball. In subsection 5.2, we provide two positive results to demonstrate these possibilities. Subsection 5.3 offers an asymmetric counterpart of Theorem 1. 21 It is during this phase that players j ‰ i are rewarded for participating in i’s punishment phase. 14 5.1 Two Negative Results One might hope that the following ‘global’ extension of Sorin’s lemma to unequal discounting holds: If C Ă Rn is a finite set there exists δ P r0, 1q such that if δj ě δ for 1 ď j ď n, and x P copCq, there exists a sequence of points tcptq u8 t“0 in C for which ř8 t ptq xj “ p1 ´ δj q t“0 δj cj . It is easy to see that as stated, the conjecture cannot be true: for example, when n “ L “ 2 (whereupon copCq is a one-dimensional set with just two vertices) we need the two discount factors to be equal in order to realize points in copCq. Is this then an artifact of copCq not being full-dimensional or x lying on the boundary rather than in the interior of copCq? Are points that defy the desired representation non-generic? Unfortunately, the problem runs deeper. Counterexample 1. Consider the simple, two-player game with the payoff matrix displayed below. L R U ( 1, 0) (0, 0) D (0, 0) ( 0, 1) Let any δ P p0, 1q be given. We will show the existence of an open set in copCq and a δ1 , δ2 pair where the impatient player’s discount factor is exactly δ, such that no point in that open set is representable using the vertices in C and the given discount factors. To that end, suppose, one can find real numbers ε1 , ε2 , δ1 , δ2 , and an integer T with the following properties: 0 ă ε2 ă ε1 ă 1, (5.1) δ “ δ2 ă δ1 ă 1, (5.2) (5.3) T δ2 ă ε2 , p1 ´ δ1 q δ1 T ´1 (5.4) ą ε1 . We assert that the point p1 ´ ε1 , ε2 q, which is in intpcopCqq by (5.1), is not realizable for discount factors pδ1 , δ2 q. To prove this, we first prove inductively that if x1 “ 1 ´ ε1 “ p1 ´ δ1 q 8 ÿ ptq δ1 t x1 , t“0 then xp0q “ xp1q “ . . . “ xpT ´1q “ p1, 0q, i.e. p1, 0q must be played for the first T periods. If xp0q ‰ p1, 0q, then even if p1, 0q were to be played in each subsequent period, x1 could be at most δ1 . This would mean 1 ´ ε1 ď δ1 , or ε1 ě p1 ´ δ1 q. However, (5.4) rules this out. If xp0q “ p1, 0q but xp1q ‰ p1, 0q, then x1 ď p1 ´ δ1 q ` pδ1 q2 , which implies p1 ´ δ1 q ` pδ1 q2 ě 1 ´ ε1 ; from this it follows that ε1 ě p1 ´ δ1 q δ1 , which violates (5.4). Proceeding this way, p1, 0q must be played at least the first T times. But then x2 ď pδ2 qT , which violates (5.3) if x2 “ ε2 . 15 It remains to show that one can indeed satisfy the properties (5.1) – (5.4) by judicious choice of ε1 , ε2 , δ1 , δ2 , and T . Note that the (strict) inequality p1 ´ δ1 q δ1T ´1 ą δ2 T holds when ˆ ˙T δ1 δ1 ą (5.5) δ2 1 ´ δ1 holds and hence, if we set δ2 “ δ, and choose δ1 to be any real number in pδ, 1q, there will exist an integer T such that (5.5) will hold. We can then choose an open set of ε1 , ε2 pairs such that 0 ă δ2T ă ε2 ă ε1 ă p1 ´ δ1 qδ1 T ´1 ă 1 and we would have fulfilled all our requirements. This shows that, no matter how high the discount factors are forced to be, if we are allowed to choose them unequal, we can find an open set of points in a full-dimensional feasible set of payoffs that cannot be realized without PRDs. The counterexample also demonstrates that the set of realizable payoffs (and even its closure) can fail to be convex in every situation when discounting is not perfectly symmetric. Thus, Sorin’s Lemma is an extremely non-generic, knife-edge phenomenon.22  It then seems natural to invoke self-accessibility. In analogy with the equal-discounting case, one might conjecture the following ‘local’ version of Sorin’s Lemma: If C Ă Rn is a finite set with an n-dimensional convex hull, for any x in the interior of copCq there exists a quantity r ą 0 and a cutoff δ such that the ball Bpx, rq is self-accessible for discount factor vectors of the form δ “ pδ1 , . . . , δn q with δi ě δ. The following shows that this conjecture is false as well. Counterexample 2. Consider another two-player game with the following payoff matrix: L R U ( 1, -1) (-1, -1) D (-1, 0) ( 1, 1) Take any ball Bpp0, 0q, rq with r ă 1. Suppose that the conjecture holds for 0 ă δ ă 1. In that case, if δ “ pδ1 , δ2 q ě pδ, δq and x is in the ball, there exists c P C such that if we define ypδq via the equation xi “ p1 ´ δi q ci ` δi yi pδq for i “ 1, 2, (5.6) then, ypδq P Bpp0, 0q, rq. Write δ “ 1{p1 ` θq and choose δ2 “ δ, and δ1 “ 1{p1 ` k1 θq for k1 P p0, 1q; this ensures that δ1 ě δ. Now specifically let us consider the point x “ pr, 0q and ask which c P C will make the ypδq given via (5.6) lie in the ball. It is easy to see that the vertices p´1, 1q and p´1, ´1q are ruled out. By symmetry, p1, ´1q works if and only if p1, 1q works. For c “ p1, 1q, equation (5.6) gives ypδq “ pr ` k1 θpr ´ 1q, ´θq. Hence, ypδq Ñ pr, ´θq as k1 Ñ 0; for any given θ, this is strictly outside the ball. Hence for every θ, there exists a k1 (i.e. for every δ2 “ δ, there exists a δ1 ą δ) for which ypδq is outside 22 This seems to echo the findings of Salonen and Vartiainen (2008); however, the stage game they use is not full-dimensional, while ours is. 16 the ball no matter what c is used. 5.2  Two Positive Results We now present two positive results on self-accessibility with asymmetric discounting. The first focuses on the self-accessibility of a fixed ball and uses the same parametrization of the discount factors as in Sugaya (2015) where δi is written as 1{p1 ` ki θq with k fixed.23 This result will be used in the next section to examine which points are realizable. The second demonstrates the existence of flexible, δ-dependent self-accessible sets but places no restrictions on discount rate ratios (and hence, relative patience). It will be used in this section to support points inside intpF ˚ q. Proposition 3. Let C Ă Rn be finite, and let X “ copCq be full-dimensional and contain in its interior the ball Bpo, rq with r ą 0. For any k P Rn`` , there exists θ̄po, r, kq ą 0 such that for any θ P p 0, θ̄po, r, kq s, the ball Bpo, rq is self-accessible relative to C for any δ satisfying δi “ 1{p1 ` ki θq for each i. Furthermore, θ̄po, r, kq is continuous in all its arguments. The technique for proving Proposition 3 is similar to that of Proposition 1 though neither follows directly from the other. In particular, note that the current proposition cannot handle affine balls - it must work with full-dimensional balls since, for arbitrary k, the continuation payoff vector need not be in the original affine ball, no matter how small θ is. It is possible to compute θ̄ as the solution of an NLP (the details have been omitted and are available from the authors on request). Our next proposition starts out with a ball that is self-accessible for the equal discount factor δ, and then for any discount factor vector δ where each δi ě δ, proposes a new, ellipsoidal self-accessible set that is contained within the ball.24 Proposition 4. Let C Ă Rn be finite, and let X “ copCq be full-dimensional and contain in its interior the ball Bpo, rq with r ą 0. Assume that Bpo, rq is self-accessible realtive to C for the discount factor vector δι where δ P p0, 1q. For any δ such that δi P rδ, 1q for i “ 1, . . . , n, there exists an ellipsoid Epo, r, δ, δq Ă Bpo, rq given by center o and i semi-axes lengths 1´δ 1´δ r such that Epo, r, δ, δq is self-accessible relative to C for δ. The proposition implies that for any v P Epo, r, δ, δq, there is a sequence of pure actions that realizes v when the discount factor vector δ is used; we let taptq pv, Epo, r, δ, δqqu8 t“0 denote that sequence. 23 Normalizing k1 to 1, the k vector captures the ratios of discount rates, i.e. relative patience among players. With that fixed, one can let θ tend to 0 so as to simultaneously make all players become absolutely very patient. 24 We gratefully acknowledge the fact that this result was first suggested to us by Costas Cavounidis. 17 5.3 A (Partial) Folk Theorem We now present a constructive folk theorem for points in intpF ˚ q under general discounting and without PRDs. The proof of this result uses Proposition 4 and requires only minor re-writing of the proof of Theorem 1. The self-accessibility led approach thus allows us to provide a unified treatment of folk theorems with or without PRDs and with or without symmetric discounting (for points in intpF ˚ q). Theorem 2. Let F ˚ be full-dimensional. For any v P intpF ˚ q, let δ be the discount factor bound computed in Theorem 1 such that v can be supported as SPNE when players use the discount factor vector δι with δ ě δ. Then, v is also an SPNE payoff when the discount factor vector δ ě δι is used. As in Theorem 1, all paths on and off equilibrium are recursively computable and punishment (minmaxing) periods are independent of the discount factors. We remark that the unbridled freedom to have players with any configuration of relative patience works only for supporting points inside F ˚ ; it may not work for points outside it, as the analysis in Section 7 will show. The Fact below extends Theorem 2; its justification follows from the proofs of Theorems 1 and 2 as well as the rich continuity properties that discount factor bounds are endowed with in Theorem 1 thanks to selfaccessibiliy. Fact 1. Let F ˚ be full-dimensional and let u and r ą 0 be such that Bpu, rq P intpF ˚ q. Then there exists a uniform δ ą 0 such that if δ is such that δi ě δ for each i, every v P Bpu, rq is an SPNE payoff for δ. Hence, for a fixed k vector, there exists a bound θ̄, such that if θ ď θ̄, and δi “ 1{p1 ` ki θq, every v P Bpu, rq is an SPNE payoff. 6 Going Beyond the Feasible Set: Realizability In non-cooperative game theory, contracts are assumed to be unenforceable, which is why we are only interested in equilibrium outcomes. However, if contracts are actually enforceable and the set of supportable payoffs is smaller than the set of realizable payoffs, identifying the latter becomes important. Using self-accessibility and results from the previous section, we can show that for n-player games with full-dimensional feasible sets, as long as the players are absolutely patient, for a wide variety of relative patience parameters, any point in intprepF qq is realizable. Thus players can simultaneously obtain virtually anything they can individually get in the stage game. All paths involve pure actions only, making PRDs irrelevant. As an example, consider a two-player game for which F is the shaded region with four vertices c1 , . . . , c6 as in the left panel of the figure below. Our next theorem implies that points like α, β, γ and ρ are all realizable in the repeated game using continuation payoff paths that can be made to (eventually) settle in the vicinity of any point in F we might choose. 18 c6 c6 γ c5 ρ c6 γ γ c5 c5 c1 c4 β α c4 c3 c4 c2 Figure 5: Realizing Payoffs Outside F Theorem 3. Let F be full-dimensional. Then ď Fpδq Ą intprepF qq. δPp0,1qn More precisely, given any target payoff vector v P intprepF qq, any payoff vector u P intpF q and any ν ą 0 such that Bpu, νq Ă intpF q, we can compute positive numbers k1 , . . . , kn 1 with θ ă θ̄ for each i, then, (not necessarily uniquely) and a θ̄ ą 0 such that if δi “ 1`k iθ v P Fpδq and that along the path that realizes v, after a finite sequence of actions, all continuation payoff vectors lie in Bpu, νq. To obtain some intuition behind this result, suppose we are examining the realizability of a specific point v P intprepF qq. If for some k, and low enough θ, playing a certain sequence of vertices brings the continuation payoff (needed to realize v) enter a fixed ball Bpu, νq inside intpF q, we are done thanks to our ability to make the ball self-accessible for any k if a low enough θ is chosen (see Proposition 3). This implies stringing together a ‘pre-entry’ finite path into Bpu, νq and a ‘post-entry’ infinite path that stays in Bpu, νq, we can generate a path that will realize v. In the middle panel of Figure 5, which enlarges the top-right section of the left panel, for the target payoff γ, we show an example pre-entry path using a dotted line stretching from γ to the small ball just below vertex c6 . This path results from the repeated play of c4 until entry inside the ball takes place. The key insight here is to choose the number of periods of playing c4 to be (roughly) inversely proportional to θ; whereupon adjusting the constant of proportionality and the ki ’s, the distance traveled by the continuation payoff in both directions can be exactly ‘regulated’ in the limit (as θ becomes small). For the dashed path in the figure, since player 2’s continuation payoff changes much less than that of player 1, k2 will have to be chosen much smaller than k1 . Many such balls and many k vectors are compatible with this plan of entry into F , but one can achieve more. In the right panel of Figure 5, we want the continuation 19 payoff to eventually enter the specific ball just below the vertex c5 (centered around some specific u). We show that there are many k vectors for which this can be done (for θ small) by playing c4 several times followed by playing c6 several times. The dashed path in the panel describes the trajectory of the continuation payoffs, the kink signifying the point where play switches from c4 to c6 . An induction argument generalizes this to any number of players and any ball inside F and we show that there is an n-phase pre-entry path involving a sequence of vertices c1 , . . . , cn which can be chosen using a simple rule: sgnpcii ´ vi q “ sgnpvi ´ ui q for i “ 1, . . . , n. For n “ 2, Theorem 3 can be sharpened via the next result, which fully characterizes realizable payoffs. Such a full characterization is not possible for n ě 3 without additional requirements on the faces of the feasible set. Theorem 4. For two-player games, if F is full-dimensional, ď Fpδq “ intprepF qq ď F. δPp0,1q2 Our approach to the question realizability is significantly different from that of LP 1999 and the paths we offer are also very different from the paths that were proposed in LP’s paper. For the interested reader, a detailed discussion is provided in Appendix 2. 7 Going Beyond the FSIR Set: Supportability The path described in the proof of Theorem 3, unfortunately does not guarantee that every continuation payoff on that path satisfies individual rationality, even when the target payoff v is strictly individually rational and the eventual continuation payoff is some point in F ˚ . We need additional conditions on v. A permutation π is a 1-1 correspondence between I and itself; by πi we mean πpiq. We represent π by simply stating the vector pπ1 , . . . , πn q. The permutation p1, . . . , nq is called the ‘natural permutation’ or ‘natural order’. An interpretation of these permutations is now suggested: π simply maps the ranks of discount factors into player ‘names’; thus, in a 5-player game, if π2 “ 4, that means player 4’s discount factor is the second-lowest. The inverse function maps names to the ranks; thus if π ´1 pjq ď π ´1 piq, we understand that player i is at least as patient as player j. This interpretation will be useful to keep in mind for the two definitions to follow; the proofs of Theorem 5 and 6 will validate it later. 7.1 The Diagonal Conditions In the definitions below C is any set of points in Rn , F “ copCq and w is some point in repCq. Of course, these objects have their standard interpretations in the context of a game: pure action payoffs, feasible set and minmax point. 20 Definition A payoff vector v P repCq is said to satisfy the weak diagonal condition (WD) if there exists a permutation π, such that @ i, D a vector ui P F with the property uiπi “ vπi and uij ě wj if π ´1 pjq ď π ´1 piq. Definition A payoff vector v P intprepCqq is said to satisfy the strict diagonal condition (SD) if there exists a permutation π, such that @ i, D a vector ui P intpF q with the property uiπi “ vπi and uij ą wj if π ´1 pjq ď π ´1 piq. When v satisfies the first (second) definition we say that it satisfies WD (SD) in the order π. Also, the set of all points satisfying WD (SD) for a given π will be denoted as W pπqpSpπqq. Note that full dimensionality of F ˚ is needed for Spπq to be non-empty, but not so for W pπq. As for the relation between these sets, it is easy to see that for any π, clpSpπqq Ă W pπq and assuming full-dimensionality of F ˚ , intpW pπqq “ Spπq. In a 2-player game, v satisfies WD in some order if it is weakly individual rational and if, from that point, we can draw a line parallel to one of the axes and make that line intersect F ` . This implies that the the darkly shaded region (including its boundary) in Figure 2 in Section 3.2 is the set of points that satisfy WD for some permutation. Specifically, for example, the point v “ p8, 5q satisfies WD in the natural order because u1 can be chosen to be p8, 1q and u2 can be chosen to be p5, 5q. For games with 3 or more players, the following Fact, stated without proof, is helpful in discerning which points will satisfy WD or SD (for some order). Fact 2. v satisfies WD for permutation π iff vi P r v i pπq, v̄i pπqs @i “ 1, . . . , n, where for any given permutation π, vpπq and v̄pπq are defined as follows: v i pπq :“ mintvi : v P F such that vj ě wj @j such that π ´1 pjq ď π ´1 piqu. v̄i pπq :“ maxtvi : v P F such that vj ě wj @j such that π ´1 pjq ď π ´1 piqu. The Fact makes is clear that for any π, computing v i pπq and v̄i pπq and hence describing W pπq is simply a matter of solving a set of linear programs. For symmetric 3-player games, the computations might be even more straightforward as the example below illustrates. Example (The “stand-out” game): Each of three players can play one of two actions: R (right) or W (wrong). All players get 0 if 0, 2 or 3 players play R. Only if exactly one player plays R, that player gets 1 ` 2η while each of the other two players receive 21 ´η where η is some positive number. Thus, C “ tp0, 0, 0q, p1 ` 2η, ´η, ´ηq, p´η, 1 ` 2η, ´ηq, p´η, ´η, 1 ` 2ηqu. In this game the only way to obtain the superior payoff of 1 ` 2η is to uniquely ‘stand out’ (by doing the right thing) whereupon the other players are ‘shamed’ into getting a negative payoff of ´η. Note that for each player, R weakly dominates W . However, if all players play this weakly dominant strategy the total utility is 0, while each of the three action vectors pR, W, W q, pW, R, W q and pW, W, Rq gives the players a total utility of 1. Note also that each player can be minmaxed by the other two players playing R, and hence w “ p0, 0, 0q. Since w is in the feasible set, clearly v i pπq “ 0 @i and @π. Now notice that the Pareto frontier in the feasible set is coptp1 ` 2η, ´η, ´ηq, p´η, 1 ` 2η, ´ηq, p´η, ´η, 1 ` 2ηquq and thus, all points on this frontier belong to the same plane as that of the unit simplex. Hence, if we were to maximize one player’s payoff in F while giving the other two a non-negative payoff, we can give him at most 1. If we were to maximize his payoff while giving one of the others at least 0 and putting no other restriction on the third, apart from requiring that we stay inside F , we can give him at most 1 ` η. Finally, if we tried to maximize this player’s payoff without any restriction on the other two’s payoffs apart from requiring that we stay in F , we can give him at most 1 ` 2η. Hence, for the natural permutation π, v̄pπq “ p1 ` 2η, 1 ` η, 1q and W pπq “ r0, 1 ` 2ηs ˆ r0, 1 ` ηs ˆ r0, 1s. 7.2 Necessity and Weak Diagonalizability Theorem 5. Consider an n-player game and let P denote the set of all permutations of 1, . . . , n. Then, ď ď W pπq Ą Vpδq πPP δPp0,1qn i.e., for any n-player game if v is a SPNE payoff vector for some discount factor vector δ, then v P W pπq for some permutation π. Note that no full-dimensionality assumption is required in the above theorem. Its proof proceeds by asking the counterfactual question: What would the payoff profile look like if the players played the proposed equilibrium path but all of them used one of the player’s discount factor to evaluate their normalized payoffs? We show that an increase in a player’s discount factor can never let his (normalized) payoff to fall below his individual rational level, from which it follows that the u’s needed for the WD property are exactly these freshly evaluated payoff vectors. We now wish to comment on two insights provided by this theorem, one that shows how equilibrium characterization for multiplayer games bears similarity to that of twoplayer games and one that shows how it does not. The proof of Theorem 5 along with Fact 2 rules out arbitrary associations of equilibrium payoffs with relative ordering of patience among the players. For example, going back to the stand-out game, for η “ .5, although the payoff vector p1.9, 1.4, .9q is an equilibrium payoff vector, it is conformable with one and only one ranking of player patience: the one 22 given by the natural order. This suggests that for symmetric stage games the maximum payoff the least patient player can conceivably receive is the largest possible payoff any player can receive in the repeated game. It is noteworthy that in the presence of PRDs and for the two-player case, LP 1999 arrive at the same conclusion. Theorem 5 and Fact 2 also inform us that in the stand-out game, any payoff vector that does not lie in the union of the six cubes of the form r0, as ˆ r0, bs ˆ r0, cs where a, b, c are some arrangements of the 3 numbers 1, 1 ` η and 1 ` 2η, can never be an equilibrium payoff. Thus, again if η “ .5, we can conclude that the payoff vector p.5, 1.7, 1.9q cannot be an equilibrium payoff vector because two of its coordinates lie above 1.5 - it does not matter what the other coordinate is (although, this payoff vector is realizable by virtue of Theorem 3). This is illustrated in Figure 6 below which depicts the set of all weakly diagonalizable payoffs for this game. Clearly, for three-player games, it is not true that in analogy with the two-player game in Section 3.2, the only individually rational payoffs that are excluded from being equilibrium payoffs form an ‘upper north-east’ cuboid. u3 u2 u1 Figure 6: Weakly Diagonalizable Payoffs for the Stand-out Game 7.3 Sufficiency and Strict Diagonalizability Weak diagonalizability, however, cannot be a sufficient condition for a payoff vector to be an equilibrium payoff vector, even when we have full dimensionality of the FSIR set. One can see this for the game in Counterexample 1, where the payoff vector p1, 1q belongs to W pπq for each π, but it is not even realizable for any discount factor vector. Strict diagonalizability, though, ‘works’. 23 Theorem 6. Consider an n-player game with a full-dimensional FSIR set. Let P denote the set of all permutations of 1, . . . , n. Then, ď πPP ď Spπq Ă Vpδq δPp0,1qn More specifically, if v P Spπq for some π, it is possible to determine k ąą 0 (not neces1 sarily uniquely), and θ̄ ą 0 such that if θ P p0, θ̄q and δi “ 1`k for each i, it is possible iθ to specify a SPNE strategy profile that supports v for those discount factors. Since the proof of Theorem 6 uses several new ideas, we now provide some intuition behind our arguments. We will borrow a technique from the proof of Theorem 3: Devise relative patience parameters (k vectors) and an action sequence that will generate a path for the continuation payoffs which will start with the target payoff and for θ small, will end in a ball inside the interior of the FSIR set (rather than the feasible set as in the case of Theorem 3). As before, we will call this the pre-entry path. Once our path enters that ball, Fact 1 takes over, since that result guarantees that any point in such a ball is an equilibrium payoff provided each player’s discount factor exceeds a certain bound. There are two new challenging tasks here: first to create a pre-entry path that stays strictly individual rational throughout and second, to design an equilibrium strategy that takes care of incentive compatibilty along the pre-entry path. Where strict diagonalizability helps is with the first task. To see this for the twoplayer case, suppose our target payoff v is in Spπq where π is the natural order. Then, strict diagonalizability of v guarantees us the existence of a vector u2 in intpF ˚ q where u22 “ v2 and u21 (strictly) exceeds player 1’s minmax payoff. Also, there must exist a vertex c such that each time this vertex is played the continuation payoff of player 1 shifts towards u21 (from v1 ). If we play this vertex T times where T is r θb sq, letting k1 “ 1 and by choosing a suitable b ą 0 and θ small, limiting arguments used in the proof of Theorem 3, show us that it is possible to take the first coordinate of the continuation payoff arbitrarily close to u21 . On top of this if k2 is chosen small, the second coordinate of the continuation payoff barely changes from v2 during these T periods and the continuation payoff vector after T periods gets close to u2 and hence, enters the desired ball. For three or more players, unfortunately, extending this idea runs into difficulties. Suppose n “ 3 and v P Spπq for the natural order π. Now, there is a point in intpF ˚ q, namely u3 , the third element of which is v3 . A small neighborhood of this point suggests itself as the location of entry into intpF ˚ q. This is what we might want to do to accomplish our goal: first we ‘fix’ player 1’s payoff by moving it to u31 (via the play of some suitable vertex). If we keep players 2 and 3 patient relative to player 1 , their payoffs do not fall below their minmax values during this first phase. Next, we try and fix player 2’s payoff by taking it close to u32 playing some other suitable vertex and thereby try and enter intpF ˚ q. The problem with this strategy is that in the second phase, we can ensure player 24 3’s continuation payoff to stay above his minmax levels by keeping him relatively patient vis-a’-vis player 2, but we can’t do the same for player 1 (because by design, player 1 is now impatient relative to player 2). Consequently, when we are trying to ‘fix’ player 2’s payoff, player 1 can find his payoff getting ‘unfixed’. We could try and fix both player 1 and 2’s payoffs simultaneously following the method used in the proof of Theorem 3, but then, we would not have any guarantee that the path will maintain individual rationality throughout. We, therefore, need a new tool: how to move one strictly individually rational payoff vector to another’s neighborhood by playing a sequence of pure actions without violating individual rationality along the path. This can indeed be done for sufficiently patient players, with any relative patience configuration as long as the two payoff vectors are both inside intpF ˚ q; moreover, the length of the sequence can be bounded in terms of θ. In m-dimensional Euclidean space, let ry, zs represent the line segment joining the points y and z and let Cpy, z, rq denote the set of points that are at most distance r from ry, zs, i.e. ď Cpy, z, rq “ Bpo, rq o P ry,zs From now on, we will refer to sets of these types as ‘capsules’. Proposition 5. (The Capsule Lemma) Let D be a finite set in m-dimensional Euclidean space. For y, z in intpcopDqq, let r ą 0 be such that the capsule Cpy, z, rq is in the interior of copDq X Rm `` , which is assumed to be m-dimensional. Then, : a) For any u P Bpy, rq and any vector k P Rm `` , there exists θ pkq ą 0 such that for any ´1 θ P p0, θ: pkqq we can find a finite sequence of points tct uTt“0 in D and a finite sequence of t T points tx ut“0 in Cpy, z, rq such that i) x0 “ u, ii) xit`1 ´ cti “ p1 ` ki θqpxti ´ cti q for i “ 1, . . . , m, t “ 0, . . . , T ´ 1 and iii) xT P Bpz, rq. b) Furthermore, there exists a θ; pkq ď θ: pkq, a strictly positive number m1 and a strictly negative number m2 (both Qdependent on k) such that when θ P p0, θ; q, the T given in part U ? ||y´z|| . a) is less than or equal to 2 2 r´ m1 θ `m2 θ`r The Capsule lemma’s proof offers the remarkable insight that the notion of selfaccessibility is not just useful for keeping continuation payoffs tethered to a point; it can also be used to take them for a ‘walk’ inside intpF ˚ q. Along with strict diagonalizability it can be used to design a k, a bound on θ and a (continuation payoff) path that starts at the target payoff v and ends inside intpF ˚ q, close to un . We sketch how for the n “ 3 case. While u3 is the (approximate) point of entry, our construction will also make use of u2 given by SD. First, let us replace the first coordinate of v by the first coordinate of 3 u2 and create the vector z “ pu21 , v2 , v3 q P R`` (thus z and u2 have the same first two 25 coordinates). Next, we design the pre-entry path of the continuation payoff by splitting it into two phases. In the first phase the path stays very close to the line segment joining v and z while in the second phase it stays very close to the line segment joining z and u3 . Since all three vectors v, z and u3 belong to R3`` , this will guarantee individual rationality along the entire path. For the first phase we choose k1 “ 1 and a vertex such that playing that vertex T1 pθq times makes player 1’s continuation payoff moves from v1 to close to u21 for θ small. As has been argued before, this can be done by making T1 pθq inversely proportional to θ and choosing a suitable constant of proportionality. Next, we choose k2 small enough, so that during the first phase, player 2’s continuation payoff does not change much from v2 . Hence, by the end of phase 1, the continuation payoff (sub)-vector of players 1 and 2 will be (for θ small) very close to pz1 , z2 q. Next, notice that the projection of any vector in F on the first two coordinates belongs to the convex hull of the projection of the extreme points of F on the same two coordinates; further, if the original vector is strictly positive, so is the projected subvector. Hence, we can use the Capsule lemma (in two dimension) to create a sequence of actions that takes the continuation payoff (subvector) from a neighborhood of pz1 , z2 q to one of pu31 , u32 q. If T2 pθq is the number of steps required in the process, now we can determine k3 small enough such that during none of the T1 pθq ` T2 pθq combined steps player 3’s payoff changes much from u33 “ v3 for θ small (this is possible because T2 pθq is also of the order of 1θ ). Thus, at the end of both phases the continuation payoff gets very close to u3 without violating individual rationality in any period (for the chosen k and θ small). Now that the equilibrium path has been described, the equilibrium strategy can be qualitatively described; of course, only the equilibrium prescription along the pre-entry path needs to be spelled out. Play starts and continues on the pre-entry path until one of the players unilaterally deviates whereupon he is minmaxed by the other players for a certain number of periods. After minmaxing, play ‘returns’ to the same point on the pre-entry path where the deviation took place (this is why we referred to these strategies in the introduction as ‘turnpike strategies’). At the completion of the pre-entry path, players play an action sequence corresponding to a point which shifts the target post-entry equilibrium continuation payoff by two ‘adjustment’ terms; one to make any punishing player indifferent among his minmaxing pure strategies, and a second to ‘reward’ the punishers for participating in the punishment. During pre-entry, any deviation from a punishment phase or a new deviation after play has returned to the ‘pre-entry’ path is treated as if a fresh deviation just took place. Why does this “stick now (for the deviant), carrot later (for the punishers)” strategy ensure incentive compatibility for patient players? With rising patience, bad outcomes for a finite number of periods still can wipe out one period gains (if nothing else changes). That is how the ‘stick now’ threat keeps players from deviating. The prospective punishers may also suffer during the punishment periods but they are compensated by a reward coming 26 later. As they become more patient, that future reward overrides the sacrifices they make for a finite number of periods but counteracting this, the time taken to to get one’s reward also grows infinitely large. Fortunately, the second part of the Capsule Lemma bounds the time spent on the pre-entry path in a way that the PDV of the reward tends to a limit. This allows us to incentivize patient players suitably to participate in the punishment of the deviant. Before leaving this section, it is worthwhile mentioning that together, the proofs of Theorems 5 and 6 also help us establish an assertion we made in the introduction: for stage games where F ` is full-dimensional, the set of sequentially individually rational payoffs has zero Hausdorff distance from the set of equilibrium payoffs, or in notation used there: Ť Ť ` δPp0,1qn F pδq « δPp0,1qn Vpδq. This is true because in the proof of Theorem 5, the only property of an equilibrium payoff that is used is sequential individual rationality. Hence, Ť Ť from that theorem we have πPP W pπq Ą δPp0,1qn F ` pδq while from Theorem 6 we have Ť Ť Ť Ť ` δPp0,1qn Vpδq Ą πPP Spπq. Since, δPp0,1qn F pδq Ą δPp0,1qn Vpδq, and since for every Ť Ť π, intpW pπqq “ Spπq which implies πPP W pπq « πPP Spπq, the relation follows. This assertion is comparable to Theorem 1 of Sugaya (2015) which essentially makes the same claim, but having restricted relative patience parameters. 8 Conclusion This paper provides a unified treatment of discounted repeated games with perfect monitoring and without PRDs. The scope of our inquiry follows a logical chain, successively allowing for wider target payoff sets and less restrictive discounting structures. The glue that holds all the results together is the simple geometrical notion: self-accessibility. The analysis culminates in Theorem 6, where we show that any point v satisfying the Strict Diagonal Condition is an SPNE payoff for some possibly asymmetric discounting profile. This easy to check condition translates into the following: there exists an ordering π of the players such that for player πpiq there is a payoff vector in the interior of the feasible set at which πpiq gets the payoff vπpiq and everyone before πpiq in the ordering gets more than their respective minmax values. Our result can be viewed as a new folk theorem for repeated games with unrestricted discounting patterns that is built on fully constructive foundations. 27 9 Appendix 1: All Proofs Proof of Proposition 1 Existence of δ: We assume wlog that the center of the ball is the origin. Also wlog, we assume that C 1 “ tc1 , . . . cK u is in fact, the set of extreme points of X. Fix c P C 1 , x P S and let δpx, cq be defined as the solution of the following problem25 : Min δ P r0, 1s subject to x “ p1 ´ δqc ` δ y, for some y P S. We now characterize δpx, cq. Note that if y satisfies the equation x “ p1 ´ δpx, cqqc ` δpx, cq y, then y must be at the boundary of the ball. Hence, it must be that y.y “ r2 which implies x ´ p1 ´ δpx, cqqc’s dot product with itself is δ 2 r2 . Upon rearranging this shows that δpx, cq must be a root of the following quadratic equation in δ : δ 2 pc.c ´ r2 q ` 2δc.px ´ cq ` px ´ cq.px ´ cq “ 0. (9.1) For any c, given that the left hand side of (9.1) is a convex quadratic (since c.c ´ r2 ą 0), with a strictly positive value at 0 (since px ´ cq.px ´ cq ą 0q and a non-positive value at 1 (since x.x ´ r2 ď 0q, there are two roots: one is greater than 0 and less than or equal to 1 while the other is greater than or equal to 1. We are seeking the smaller root, which is continuous in x, making δpx, cq continuous in x. Furthermore, we assert that for one of the c’s, the smaller root must be strictly less than 1. Clearly this will be true if the quadratic at 1 is strictly negative, i.e. x.x ´ r2 ă 0. So assume that x.x “ r2 . It now suffices to show that the slope of the quadratic at 1 is strictly positive for some c, which will be true if for at least one l, cl . x ą r2 . If not, then cl . x ď r 2 for l “ 1, . . . , K (9.2) If that is the case, we claim that each of these inequalities must actually be an equality. To řK see this note that since x is in the relative interior of X, x “ l“1 λl cl where λl ’s are strictly l positive weights summing to 1. Multiplying each ´ř ¯ inequality in (9.2) by λ and summing over l, K l l on the left hand side we will have . x “ x.x while on the right hand side we will l“1 λ c ´ř ¯ K l have r2 “ r2 and since these two are equal, the claim follows. But now, if for each l, l“1 λ cl . x “ r2 , since the center of the ball (the origin) can also be expressed as a convex cobination of ř the vertices, i.e. o “ θl cl for a set of weights θl summing to one, this will imply o. x “ 0 “ r2 , a contradiction. Hence, for every x P BX p0, rq, there exists a vertex c such that the quadratic in (9.1) has a strictly positive slope at 1, and hence for that vertex, δpx, cq P p0, 1q. Let δ ˚ pxq :“ min tδpx, cq : c P C 1 u, with the minimum attained at c˚ pxq.26 Clearly, δ ˚ is continuous, being the minimum of continuous functions and lies in p0, 1q. Finally, define δ :“ maxtδ ˚ pxq : x P Su. Since S is compact, this maximum is attained at some x˚ . Since for any x, δ ˚ pxq P p0, 1q we must have δ P p0, 1q. It is now easily verifiable that for this δ and any common discount factor above this value S is self-accessible relative to C 1 . 25 For the first part of the proof, to keep the notation simple, when a function depends on the location of the ball, we will drop the center and the radius as arguments (thus, for example δpx, c, o, rq will be simply referred to as δpx, cq). 26 To achieve well-definition, in case of ties, use any arbitrary preference ordering among the vertices. 28 Computability of δ: Having described the problem of determining δpo, rq as Max Min δpx, c, o, rq x P BX po, rq c P C 1 we now show that this two-stage nested optimization problem can be written as one large optimization problem. This is seen from noting the fact that the ‘inside’ problem can be stated as a maximization, rather than a minimization problem as shown: Max δ subject to δ ď δpx, cl , o, rq @cl P C 1 . For affine balls BX po, rq in the relative interior of X, an explicit formula for δpx, cl , o, rq exists in terms of the smaller root of equation (9.1); a numerically simpler way to characterize that root is to just require that the slope of the quadratic is less than or equal to zero, in addition to stating that the quadratic vanishes. For any given o (not necessarily the origin), this leads to the NLP below the solution of which gives us δpo, rq: Max δ subject to δ ď δl @ l “ 1, . . . , K p1q 2 pδ l q2 tpcl ´ oq.pcl ´ oq ´ r2 u ` 2δ l pcl ´ oq.px ´ cl q ` kx ´ cl k “ 0 pδ l qtpcl ´ oq.pcl ´ oq ´ r2 u ` pcl ´ oq.px ´ cl q ď 0 px ´ oq.px ´ oq ď r2 řK x “ l“1 λl cl p5q řK l p6q l“1 λ “ 1 λl ě 0 @ l “ 1, . . . , K @ l “ 1, . . . , K p2q p3q p4q @ l “ 1, . . . , K p7q. In the NLP, constraints (2) and (3) characterize the δpx, ci , o, rq’s (for i “ 1, . . . , K) while constraint (1) finds the minimum of these. Of course, the maximization is also over x and constraints (4) - (7) ensure that each feasible x belongs to the affine ball BX po, rq.27  Proof of Proposition 2 The function δpo, rq defining a discount factor bound that makes BX po, rq self-accessible is continuous in both its arguments - as follows from the continuity of δpx, c, o, rq in po, rq, the proof of Proposition 1 and a straightforward application of the Maximum Theorem. The set BX px, r̄q being compact (wherein the centers of the smaller balls must lie), the existence of the required 27 Note that if the ball was full-dimensional, we could have dropped constraints (5) - (7). 29 uniform bound follows. Now we can state the required NLP. Max δ subject to δ ď δl @ i “ 1, . . . , K p1q 2 pδ l q2 tpcl ´ x1 qpcl ´ x1 q ´ ω 2 u ` 2δ l pcl ´ x1 qpx2 ´ cl q ` kx2 ´ cl k “ 0 pδ l qtpcl ´ x1 qpcl ´ x1 q ´ ω 2 u ` pcl ´ x1 qpx2 ´ cl q ď 0 px ´ x1 q.px ´ x1 q ď r̄2 p4q px1 ´ x2 q.px1 ´ x2 q ď ω 2 řK x1 “ l“1 λl cl p6q ř K x2 “ l“1 θl cl p7q řK l p8q l“1 λ “ 1 řK l p9q l“1 θ “ 1 p5q λl , θ l ě 0 p10q @ l “ 1, . . . , K @ l “ 1, . . . , K @ l “ 1, . . . K p2q p3q The construction of the given NLP follows directly from the proof of Proposition 1 and the observation that the problem of finding a uniform bound as x1 ranges in the set BX px, r̄q adds another layer of nesting to the optimization problem in that proposition, making the current problem representable as Min δpx2 , c, x1 , ωq Max Max 1 2 . 1 x P BX px, r̄q x P BX px , ωq c P C 1  Proof of Theorem 1 Because F ˚ is full-dimensional and v P F ˚ zBF , there exists v 1 such that it is in intpF ˚ q and v 1 ăă v. First, we define two constants ∆ and N that we need to define the equilibrium strategy.28 We choose ∆ ą 0 such that ? Bpv 1 , 4 n ´ 1∆q Ă intpF ˚ q. (9.3) Further, if v is not a payoff vector associated with a pure strategy profile, and can be expressed řK as l“1 λl cl where each λl ą 0, ∆ should be small enough so that BX pv, ∆q Ă relintpXq (9.4) where X “ cotc1 , . . . , cK u. Note that from (9.3), it follows that vi1 ą ∆. Now define N P N by S N“ W M max 1 , i vi ´ ∆ 28 (9.5) 2∆ serves as the ‘reward’ for the punishers; while ∆ serves as the radius of all self-accessible balls we will be dealing with in this proof. N is the number of minmaxing periods. 30 implying that N ` 1 ą M {pvi1 ´ ∆q for all i. Let δ 1 be such that for δ ě δ 1 , δN ě N . N `1 (9.6) The last two inequalities guarantee the following inequality which will be critical later: 1 ` δ ` . . . ` δN ě M vi1 ´ ∆ @i . (9.7) Next, given N , there is a δ 2 , such that for δ ě δ 2 , δN ě M M `∆ (9.8) @i. Note that this implies, for δ ě δ 2 , δN ě vi1 vi1 ´ ∆ ě vi1 ` ∆ vi1 ` ∆ @i. (9.9) If v is a payoff vector for a pure action profile, let δ 3 “ 0. Otherwise, BX pv, ∆q referred to in (9.4) is self-accessible for all δ larger than some bound; let δ 3 be that bound computable via Proposition 1. Lastly define 1 1 v 1 piq :“ pv11 ` 2∆, . . . , vi´1 ` 2∆, vi1 , vi`1 ` 2∆, . . . , vn1 ` 2∆q ? Consider the set of all (full-dimensional) balls the centers of which are at most n ´ 1 ∆ away from v 1 piq, each with radius ∆. It may be checked because of (9.3), each of these small balls are fully contained in the interior of F ˚ . Using Proposition 2, a uniform bound can be computed such that each of these balls is self-accessible when the common discount factor is as large as the bound. Call this bound δ4i . Now define δ “ maxpδ 1 , δ 2 , δ 3 , max δ 4i q. i (9.10) For any discount factor δ exceeding this bound, v may be supported by a three-phase strategy which we now describe. Phase I: If v is a pure action profile, play that pure action profile forever. Otherwise, play the action sequence taptq pv, BX pv, ∆q, δqu8 t“0 . If there is a unilateral deviation by player i in Phase I, move to Phase II(i). Phase II(i): For each of N periods play mi , the (possibly mixed) action profile that minmaxes i. If player j unilaterally deviates from this phase (i.e. he is observed to play an action that is not in the support of mij ), start Phase II(j). Otherwise, at the completion of this phase, go to Phase III(i). Phase III(i): Let ãptq , t “ 1, . . . , N be the realized actions during Phase II(i). In Phase III(i), 1 1 i play the sequence of actions given by taptq pv piq ´ z i ´ ∆ei , Bpv piq ´ z i , ∆q, δqu8 t“0 , where z is an adjustment vector defined by the following two equations $ & p1´δN q ri if j ‰ i j δN i zj “ (9.11) %0 otherwise. 31 rji “ N p1 ´ δq ÿ t´1 δ gi pãptq q, p1 ´ δ N q t“1 (9.12) If there is any unilateral deviation from Phase III(i) by player j, start Phase II(j). N M ď ∆ and since, |rji | ď M , |zji | ď ∆ for j ‰ i. This implies Inequality (9.8) implies 1´δ δN ? 1 i that v piq ´ z is at most n ´ 1 ∆ away from v 1 piq. Hence, given the construction of δ 4i earlier, 1 Bpv piq´z i , ∆q is indeed self-accessible for discount factors above that bound. Let us now examine conditions for player i’s strategy to be unimprovable. • For unimprovability from Phase I, it suffices to have p1 ´ δqM ` δ N `1 pvi1 ´ ∆q ď vi ´ ∆, (9.13) • For unimprovability from Phase II(i) with τ periods left in the phase, it suffices to have 0 ` δ N `1 pvi1 ´ ∆q ď 0 ` δ τ pvi1 ´ ∆q for τ “ 1, . . . , N. (9.14) • For unimprovability from Phase III(i), it suffices to have p1 ´ δqM ` δ N `1 pvi1 ´ ∆q ď vi1 ´ ∆. (9.15) • To analyze unimprovability from Phase II(j) we note that because of the adjustment term z in Phase IIIj’s target point, player i is indifferent in Phase IIj between playing any action that is in the support of mj . The question is whether he wishes to play an action which is not in the support of mj . Letting tãptq uN t“1 denote the sequence of actions that would be realized in Phase II(j) on equilibrium path, with τ periods left in that phase, if the following inequality holds (no matter what the last τ entries of that sequenc tãptq u are), it would deter deviation: p1´δqM `δ N `1 pvi1 ´∆q ď p1´δqrgi pãpN ´τ `1q q`. . .`δ τ ´1 gi pãpN q qs`δ τ pvi1 `2∆´zij q. (9.16) Using (9.11) and (9.12), the right hand side of (9.16) becomes: ¯ 1´δ ´ p1q N ´τ ´1 pN ´τ q g pã q ` . . . ` δ g pã q , (9.17) i i δ N ´τ ´ ¯ N M . Hence by (9.8), inequality (9.16) which is bounded from below by δiτ vi1 ` 2∆ ´ 1´δ N δ is satisfied for any sequence of a’s if δ τ pvi1 ` 2∆q ´ ` ˘ p1 ´ δqM ` δiN `1 pvi1 ´ ∆q ď δ N vi1 ` ∆ . (9.18) • Lastly, for unimprovability from Phase III(j) it suffices to have: p1 ´ δqM ` δ N `1 pvi1 ´ ∆q ď vi1 ` 2∆ ´ zij ´ ∆ (9.19) for all possible values of zij . Because |zij | ď ∆, this is satisfied if the following holds: p1 ´ δqM ` δ N `1 vi1 ď vi1 . 32 (9.20) Examination of these conditions shows that while (9.14) is trivially true, (9.15) directly implies (9.13) and (9.20). Because of (9.9), it also implies (9.18). Thus to ensure all incentive compatibility conditions one only needs to satisfy equation (9.15), which is (9.7). Thus the given strategy profile is indeed an SPNE.  Proof of Proposition 3 Without loss of generality, we can and henceforth do discard points in C that are not extreme 1 points of X, and relabel it as C 1 “ tc1 , ¨ ¨ ¨ , cL u. For x P Bpo, rq, and c P C 1 define a vector ypx, c, o, r, k, θq where yi px, c, o, r, k, θq :“ θki pxi ´ ci q ` xi for i “ 1, . . . , n. (9.21) i In terms of discount factors, the above is just δ1i xi ´ 1´δ δi ci , i.e. it is the i’th coordinate of the‘continuation point’ given the target x, the current action c and the discount factor vector δ. Let f px, c, o, r, k, θq :“ ||ypx, c, o, r, k, θq ´ o||2 ´ r2 n ÿ pθ ki pxi ´ ci q ` pxi ´ oi qq2 ´ r2 . “ i“1 “ θ2 n ÿ ki2 pxi ´ ci q2 ` 2θ i“1 n ÿ ki pxi ´ ci qpxi ´ oi q ` p i“1 n ÿ pxi ´ oi q2 ´ r2 q (9.22) i“1 Because Bpo, rq is full-dimensional, f ď 0 ùñ ypx, c, o, r, k, θq P Bpo, rq. To prove the proposition, we will show that there exists θ̄po, r, kq ą 0 such that if 0 ă θ ď θ̄po, r, kq, then for every x P Bpo, rq, there exists a c such that f ď 0. The expression in (9.22) is a strictly convex quadratic in θ with f px, c, o, r, k, 0q ď 0 (and so has at least one non-negative real root). Let θpx, c, o, r, kq denote its larger root, which is continuous in px, o, r, kq. For x “ o, for every c, f px, c, o, r, k, 0q “ ´r2 ă 0 and hence, the larger root is strictly positive and hence, for every c, f ď 0 for θ P p0, θpx, c, o, r, kqs. For x ‰ o, if we can show that there exists a c such that Bf Bθ ă 0 at θ “ 0 then we can assert that for that x there exists a c, such that θp x, c, o, r, kq ą 0 and for θ P p0, θpx, c, o, r, kqs, f is nonřn positive. It suffices to show that that for every x, there exists a c such that i“1 ki pxi ´ci qpxi ´oi q ă 0, or n n ÿ ÿ ki pxi ´ oi qxi ă ki pxi ´ oi qci (9.23) i“1 i“1 řn Consider the hyperplane H “ ty : py “ αu, where pi “ ki pxi ´ oi q and α “ i“1 ki pxi ´ oi qxi (since x ‰ o, p is a non-zero vector). If inequality (9.23) is false for every vertex c, that would mean that every vertex lies on one side of the hyperplane, while clearly x is situated on that hyperplane. This can not be true since x is in a ball which lies in the interior of copC 1 q. The foregoing analysis implies θ˚ px, o, r, kq :“ maxcPC θpx, c, o, r, kq is a strictly positive number, and is continuous in k, o, r and x (being the maximum of continuous functions), and furthermore, for every x P Bpo, rq, if θ P p0, θ˚ px, o, r, kqs, f ď 0. Finally, define the required bound as θ̄po, r, kq :“ min θ˚ px, o, r, kq. (9.24) x P Bpo,rq 33 Since Bpo, rq is compact, this minimum is achieved at some x, is strictly positive-valued, and because of the Maximum Theorem is continuous in o, r and k. Clearly it satisfies the desired requirements of the bound.  Proof of Proposition 4 Define ri :“ r for each i. With these being the lengths of the semi-axes of the desired 2 řn iq ď 1u. It is easy to see that ellipsoid, the latter can be written as: Epo, r, δ, δq “ tx : i“1 pxi ´o ri2 Epo, r, δ, δq is contained in Bpo, rq and can be written as f pBpo, rqq where f is a 1-1 correspondence from Bpo, rq to Epo, r, δ, δq given by 1´δi 1´δ fi pxq “ oi ` pxi ´ oi q 1 ´ δi 1´δ @i. (9.25) Now let x P Epo, r, δ, δq; to prove the proposition, we need to show that there exists c P C such that y P Epo, r, δ, δq where 1 1 ´ δi yi “ xi ´ ci @i. (9.26) δi δi To see this, let x “ f px1 q where x1 P Bpo, rq. By equation (9.25), p1 ´ δqxi “ p1 ´ δi qx1i ` pδi ´ δqoi @i. (9.27) and because of the self-accessibility of Bpo, rq for δι, there exists c such that ˙2 ˆ n ÿ ‰ 1 1“ 1 x ´ p1 ´ δqci ´ oi ď1 r2 δ i i“1 (9.28) Using this particular c in the defintion of y in (9.26), " * y i ´ oi 1 1´δ 1 “ rxi ´ p1 ´ δi qci s ´ oi ri r 1 ´ δi δi " „  * 1 1 1´δ 1´δ “ xi ´ p1 ´ δqci ´ oi r δi 1 ´ δi 1 ´ δi " „  * δi ´ δ 1´δ 1 1 x1i ` “ oi ´ p1 ´ δqci ´ oi r δi 1 ´ δi 1 ´ δi " * “ ‰ δ 1 1 1 x ´ p1 ´ δqci ´ oi “ r δi i δi " ˆ ˙* ‰ 1 δ 1“ 1 “ xi ´ p1 ´ δqci ´ oi r δi δ (9.29) (9.30) (9.31) (9.32) (9.33) where we have used (9.27) to go from (9.30) to (9.31). Now, equation (9.28) and the fact that ¯2 řn ´ i δi ě δ for each i, allow us to conclude that i“1 yir´o ď 1 and we are done.  i Proof of Theorem 2 The reader is requested to refer once again to the proof of Theorem 1 as we point out the parallels 1 and dissmilarities between that proof and the current one. We choose v 1 , ∆, N , v i , δ 1 , δ 2 , δ 3 , δ 4i and hence, δ exactly as before. This guarantees that equation (9.7) is valid with δ being replaced 34 by δi (since δi is at least as large as δ and hence δ 1 ), Thus, we have 1 ` δi ` . . . ` δi N ě M vi1 ´ ∆ @i . (9.34) Similarly, we may argue, since δi ě δ ě δ 2 , δiN ě M M `∆ (9.35) @i. i Define ∆i :“ ∆ 1´δ 1´δ . From the previous inequality it also follows that δiN ě vi1 ´ ∆i vi1 ě vi1 ` ∆ vi1 ` ∆ @i.. (9.36) Next, we describe the strategies which follow the standard three-phase pattern used previously. Since δ ě δι, and Bpv, ∆q is self-accessible for δι, via Proposition 4, we know that the ellipsoid Epv, ∆, δ, δq Ă Bpv, ∆q is self-accessible for δ. In Phase I, it is prescribed that the players play the sequence taptq pv, Epv, ∆, δ, δqqu8 t“0 . Note that at anytime during this phase, the worst continuation payoff for player i is vi ´ ∆i . Phase II(i)’s play does not change at all. To describe Phase III(i), define the quantities zji and rji ’s as before except to use δj rather that δ in their expressions given by equations (9.11) and (9.12). With these new definitions in place, now in Phase III(i), let the players play the action sequence taptq pv 1 piq ´ z i ´ ∆i ei , Epv 1 piq ´ z i , ∆, δ, δqqu8 t“0 . The transitions between the phases follow the same pattern as before. It now remains to verify the incentive-compatibility conditions which are exactly the same as before except that each occurrence of δ is now subscripted with an i and some occurrences of ∆ are subscripted with an i. • For unimprovability from Phase I, it suffices to have p1 ´ δi qM ` δi N `1 pvi1 ´ ∆i q ď vi ´ ∆i , (9.37) • For unimprovability from Phase II(i) with τ periods left in the phase, it suffices to have 0 ` δi N `1 pvi1 ´ ∆i q ď 0 ` δi τ pvi1 ´ ∆i q for τ “ 1, . . . , N. (9.38) • For unimprovability from Phase III(i), it suffices to have p1 ´ δi qM ` δi N `1 pvi1 ´ ∆i q ď vi1 ´ ∆i . (9.39) • Unimprovability from Phase II(j), after identical analysis undertaken before, is assured by: ` ˘ p1 ´ δi qM ` δiN `1 pvi1 ´ ∆i q ď δiN vi1 ` ∆ . (9.40) • Lastly, for unimprovability from Phase III(j) it suffices to have: p1 ´ δi qM ` δiN `1 vi1 ď vi1 . (9.41) As in the previous proof, the nontrivial inequalities (9.37), (9.41) are directly guaranteed by (9.39) while (9.40) is guaranteed by (9.39) because of (9.36). (9.39) is itself guaranteed by (9.34) and 35 hence....  Proof of Fact 1 First, we prove an analogous ‘uniform’ version of Theorem 1: Let F ˚ be full-dimensional. Suppose u and r ą 0 be such that Bpu, rq Ă intpF ˚ q. Then, there exists a uniform discount factor bound δ such that when δ P rδ, 1q, every point v P Bpu, rq is an SPNE payoff for δ “ δι. To see this, consider the set V pεq “ tv 1 : v 1 “ u1 ´ ει, u1 P BBpu, rqu where BBpu, rq is the lower boundary of Bpu, rq. Clearly, there exists a ε small enough, say ε̄ such that V pε̄q is inside intpF ˚ q. For every point v in Bpu, rq, we can then find a v 1 P V such that v 1 ăă v (here and in the rest of this proof, we use the same notation we used in the proof of Theorem 1). In addition, there is also a uniform ∆ ą 0 such that for every such pair of pair v and v 1 the conditions p9.3q and p9.4q Q U hold. Now N , a uniform number of punishment periods can be chosen as maxv1 PV pε̄q maxi v1M ´∆ . i Having defined N , δ 1 and δ 2 can be defined as before. A uniform bound can can be chosen for δ 3 as v varies over the compact set Bpu, rq since the proof of Proposition 1 plus an application of Maximum Theorem shows that the discount factor bound found in that proposition is continuous in the center of the relevant ball. Similarly, for each i, using the proof of Proposition 2 and the compactness of V pε̄q over which v 1 varies, a uniform bound for δ 4i can be found. Choosing δ to be maximum of δ 1 , δ 2 , and the last two uniform bounds, works as a common discount factor bound for supporting all points in Bpu, rq. Now Fact 1 follows from this the same way Theorem 2 follows from Theorem 1.  Proof of Theorem 3 1 Step 1. Let k ąą 0 and player i’s discount factor be given by δi “ 1`k where for now, θ, a iθ positive number, is unspecified. For a given payoff vector v, consider the problem of designing a path such that v is realized through an m ` 1 phase path described as follows. For given nonnegative numbers b1 , . . . , bm , in phase 1, lasting for T1 “ rpb1 {θqs periods, a certain vertex cp1q will be played, then in phase 2, lasting for the next T2 “ rpb2 {θqs periods some vertex cp2q will be played, etc., and for phase m, vertex cpmq will be played for Tm “ rpbm {θqs periods. In the m ` 1’th phase, an action sequnce that generates a continuation payoff will be played so that the whole path indeed realizes v. Call this continuation payoff ṽpθq. Because of Proposition 3, our strategy will succeed if at least for small values of θ, at the end of the first m phases, the continuation payoff enters intpF q. This suggests that we need to know what ṽ :“ limθÑ0 ṽpθq is. If xt denotes the continuation payoff during the t’th period of any path, and in the t’th period 1 , vertex c is played, then for each i the following holds: xti “ p1 ´ δi qci ` δi xit`1 . Since δi “ 1`k iθ we can rewrite this as xt`1 ´ ci “ p1 ` ki θqpxti ´ ci q. (9.42) i Hence, reasoning recursively, if c is played for T periods in periods t, t ` 1, . . . t ` T ´ 1, then for each i, xt`T ´ ci “ p1 ` ki θqT pxti ´ ci q. (9.43) i If T “ r θb s, where b is some non-negative number, then as θ tends to 0, the i’th coordinate of the limiting continuation payoff vector will satisfy lim xt`T ´ ci “ eki b pxti ´ ci q. i θÑ0 36 (9.44) Hence, in the context of the m ` 1 phase path discussed above if m “ 1, p1q ṽi ´ ci (9.45) p1q “ eki b1 pvi ´ ci q and therefore using the same idea twice, if m “ 2, p2q ṽi ´ ci p1q ` eki b1 pvi ´ ci q ´ ci q p1q ´ ci q ` eki pb2 `b1 q pvi ´ ci q “ eki b2 pci “ eki b2 pci p1q p2q p2q (9.46) p1q Proceeding inductively, we conclude that for arbitrary integer m, for each i we will have pmq ṽi ´ci pm´1q “ eki bm pci pmq ´ci pm´2q q`eki pbm `bm´1 q pci pm´1q ´ci q`¨ ¨ ¨`eki pbm `¨¨¨`b1 q pvi ´ci q (9.47) p1q Step 2. Let v̂, v be any two points in intprepF qq such that for all i, v̂i ‰ vi . We claim that for any ε ą 0, there exist positive numbers k1 , . . . , kn , b1 , . . . , bn , and vertices cp1q , . . . , cpnq , such that the system pnq “ ek1 bn pc1 pnq “ ek2 bn pc2 v̂1 ´ c1 v̂2 ´ c2 pn´1q ´ c1 q ` ek1 pbn `bn´1 q pc1 pn´1q ´ c2 q ` ek1 pbn `bn´1 q pc2 pnq pn´2q ´ c1 pnq pn´2q ´ c2 pn´1q q ` ¨ ¨ ¨ ` ek1 pbn `¨¨¨`b1 q pv1 ´ c1 q pn´1q q ` ¨ ¨ ¨ ` ek1 pbn `¨¨¨`b1 q pv2 ´ c2 q p1q p1q .. . kn bn pn´1q k1 pbn `bn´1 q pn´2q v̂n ´ cpnq pcn ´ cpnq pcn ´ cpn´1q q ` ¨ ¨ ¨ ` ekn pbn `¨¨¨`b1 q pvn ´ cp1q n “e n q`e n n q (9.48) has an ε-solution, in the sense that the two sides of each equation differ by at most ε. We give an induction-type argument to justify our claim. First, we will show that if we consider just two players, in fact an exact solution is possible. Wlog, let these be players 1 and 2; we will specifically show that there exist k1 , k2 , b1 , b2 (all positive), and vertices cp1q , cp2q P C, such that the following two equations hold: p2q p1q p2q p1q (9.49) p1q c2 q (9.50) v̂1 ´ c1 “ ek1 b2 pc1 ´ c1 q ` ek1 pb2 `b1 q pv1 ´ c1 q v̂2 ´ p2q c2 “e k2 b2 p1q pc2 ´ p2q c2 q `e k2 pb2 `b1 q pv2 ´ Now choose vertices cp1q , cp2q satisfying the conditions below. sgnpv̂1 ´ v1 q “ sgnpv1 ´ c1 q p1q (9.51) p2q c2 q (9.52) sgnpv̂2 ´ v2 q “ sgnpv2 ´ Note that since v̂i ‰ vi for all i, and both v̂ and v are in intprepCqq, it is possible to find two such vertices (and they could be the same vertex), where none of the signum functions above return 0. Let us set k2 “ 1 and make the following substitutions: eb2 “ 1 ` p and eb1 `b2 “ 1 ` p ` q in equations (9.49) and (9.50). After some cancellations, the second equation can be rewritten as p2q p1q v̂2 ´ v2 “ ppv2 ´ c2 q ` qpv2 ´ c2 q 37 (9.53) while the first equation becomes p2q p1q p2q p1q v̂1 ´ c1 “ p1 ` pqk1 pc1 ´ c1 q ` p1 ` p ` qqk1 pv1 ´ c1 q. (9.54) We are interested in positive k1 , p, q that will solve this pair of equations. In (9.53), we can choose p1q q to be very small and strictly positive such that sgnppv̂2 ´ v2 q ´ qpv2 ´ c2 qq “ sgnpv̂2 ´ v2 q, and then because of (9.52), we can find a positive p that solves (9.53). From p and q, b1 and b2 may be extracted. Turning to equation (9.54), we note that if k1 Ñ 0, sgnpRHS ´ LHSq is the same as sgnpv1 ´ v̂1 q. On the other hand, as k1 Ñ 8, because of the positivity of p and q, sgnpRHS ´LHSq p1q is the same as sgnpv1 ´c1 q. Hence, by the Intermediate Value Theorem, there exists k1 ą 0 which p1q p1q solves the equation if sgnpv1 ´ v̂1 q “ ´sgnpv1 ´ c1 q or sgnpv̂1 ´ v1 q “ sgnpv1 ´ c1 q. But this is just (9.51).29 Now, we show that for any m ă n, and for any ε ą 0 if an ε-solution exists for m ´ 1 equation piq version of (9.48), where the vertices are chosen according to the rule sgnpv̂i ´vi q “ sgnpvi ´ci q for each player i then a solution exists for the m equation version as well where the additional vertex is chosen using the same rule (used for the additional player). To see this, consider (9.48) with n replaced by m; suppose we set b1 “ 0 in all those m equations. If we consider the second through the m-th equation of the system, they become exactly the system for an m ´ 1 player scenario (where the players are indexed 2 through m). This is because in the equation pertaining to player p1q p2q p1q i (i “ 2, . . . , m) the sum of the last two terms eki pbm `¨¨¨`b2 q pci ´ ci q ` eki pbm `¨¨¨`b1 q pvi ´ ci q p2q collapses to the single term ekm pbm `¨¨¨`b2 q pvi ´ ci q on setting b1 to zero (note that cp1q disappears from the system as a result as well). We will call this particular system the ‘revised system’. Choose k2 , . . . , km , cp2q , . . . cpmq and b2 , . . . , bm , so that the left hand side and the right hand side of each equation in this revised system differ by at most 2ε . Next, choose b1 small enough so that the right hand sides of the original equations for players 2 through m and right hand sides of the corresponding revised equations differ by at most 2ε , no matter what cp1q is, which can indeed be ensured since the right hand sides of the original equations are continuous in b1 . Thus, pmq we have chosen now k2 , . . . , km and b1 , . . . , bm and vertices cp2q , . . . , c2 such that equations 2 through m satisfy the desired property. It remains to tackle the first equation and determine k1 . Indeed k1 can now be chosen to satisfy the equation exactly. Once again, as can be easily checked, this is an application of the Intermediate Value Theorem, as long as cp1q satisfies the condition p1q sgnpv̂1 ´ v1 q “ sgnpv1 ´ c1 q. This proves the claim. Step 3. Now, choose any u in intpF q such that there exists a ν-ball around u which lies fully inside intpF q (guaranteed as a consequence of the full-dimensionality assumption). Let v̂ be such that the distance between v̂ and u is at most ν{3, and for each i, v̂i ‰ vi . For this v̂ and the given v, choose the ki ’s and the bi ’s and the ci ’s using Step 2 such that for these parameters, ṽ, the limit point after the first n phases of the path described in Step 1 is at most ν{3 away from v̂. Let θ̄1 be such that for θ ă θ̄1 , the actual required continuation payoff ṽpθq is at most ν{3 away from its 1 limit point ṽ. This will ensure that when θ ă θ̄1 , for the ki ’s chosen, and for δi “ 1`k , at the iθ end of the first n phases, the required continuation payoff ṽpθq will be within a distance of ν from u. For the chosen ki ’s let θ̄2 be the cutoff on θ that is required to make Bpu, νq self-accessible as demonstrated in Proposition 3. Then, when θ ă θ̄ “ minpθ̄1 , θ̄2 q, we can simultaneously ensure Writing equation (9.54) as a “ bxk1 ` cy k1 where y ą x ą 1, it is easily seen that for k1 ě sgn(RHS - LHS) =sgn(c). Now the method of bisection can be used to identify the solution to any arbitrary desired degree of precision. 29 lnp |a|`|b| q{lnp xy q, |c| 38 that ṽpθq is inside Bpu, νq and that there is a sequence of actions that generate ṽpθq. Combining this last phase with the n phases described in Step 1, it follows that for discount factors given by 1 δi “ 1`k with θ ă θ̄, the n ` 1 phase path described in that step will indeed realize v.  iθ Proof of Theorem 4 Ť Ť We first demonstrate the inclusion: tFpδq | δ P p0, 1q2 u Ă intprepF qq F . Let x P F pδq for some δ. Obviously, x R prepF qqc , for otherwise there exists a player i such that xi is either strictly greater or strictly less than what player i can achieve in the stage game – an impossibility. Next we show that if x is on the boundary of repF q, then x P F . In this case, there exists i such that xi is an extremal (either maximum or minimum) payoff for player i (in the stage game). Let taptq | t P Z` u be the sequence of actions played to realize x, and define Cie :“ tpgpaptq q | t P Z` u to denote the set of all payoff profiles earned in any period. Since xi is an extremal payoff of i, we ř must have gi paptq q “ xi for all t; therefore not only is it true that xi “ p1 ´ δi q δit gi paptq q, but ř t it is also true that xi “ p1 ´ δj q δj gi paptq q for any δj . For player j “ 3 ´ i, of course we have ř xj “ p1 ´ δj q δjt gj paptq q. Therefore, we can write the vector equality using j’s discount factor: ř x “ p1 ´ δj q δjt gpaptq q, where each gpaptq q P Cie . This implies x P copCie q Ă F .30 Ť Ť To demonstrate the other inclusion, tF pδq | δ P p0, 1q2 u Ą intprepF qq F , we appeal to Theorem 3 (making use of the full-dimensionality assumption) and further note that for any x P F , Proposition 1 guarantees that x P Fpδιq for sufficiently large δ.  Proof of Theorem 5 Let us wlog assume that wj “ 0 for all j. We begin by asserting that on any path for any player, if he is using discount factor δ, then provided all his continuation payoffs are nonnegative, increasing the discount factor to δ̃ ą δ would keep all his continuation payoffs still nonnegative. To see this let st be the continuation payoff from t onwards when δ is used, i.e. (9.55) st “ p1 ´ δqrv t ` δv t`1 ` δ 2 v t`2 ` ¨ ¨ ¨ s where v t is the player’s actual payoff in period t. Equation (9.55) implies hence, st`1 st ´δ . vt “ 1´δ 1´δ st 1´δ t`1 ´ v t “ δ s1´δ and (9.56) Similarly let s̃t be the continuation payoff from t onwards with the discount factor δ̃. Using equations (9.55) and (9.56), we can write that as „ˆ s̃t “ p1 ´ δ̃q ˆ “ ě 1 ´ δ̃ 1´δ δst`1 st ´ 1´δ 1´δ ˙ ˆ ` δ̃ st`1 δst`2 ´ 1´δ 1´δ ˙ ˆ ` δ̃ 2 st`2 δst`3 ´ 1´δ 1´δ ˙  ` ¨¨¨ ˙ “ st ` pδ̃ ´ δqst`1 ` δ̃pδ̃ ´ δqst`2 ` ¨ ¨ ¨ 0 ‰ (9.57) Now assume for the moment that v was achieved as an equilibrium payoff vector with a discount factor vector where δ1 ď δ2 ď . . . ď δn . Consider what payoff vector would realize if we stayed with 30 When there are more than 2 players a little thought should convince the reader that this logic will not extend unless all players other than i have the same discount factor. 39 the same played path but increased each of player 1, 2, . . . , n ´ 1’s discount factors to δn . Since, v is an equilibrium payoff it is weakly individual rational, and all continuation payoffs for all players for all periods must be nonnegative as well. Hence, after this adjustment of discount factors, the payoff vector we obtain has the first n ´ 1 components non-negative, the last component is the same as vn and moreover, since with equal discounting any play must result in a payoff vector that is in F , this particular payoff vector satisfies all the requirements of un in the WD condition (under the natural order). Next consider the effect of changing all the discount factors to δn´1 ; this involves increasing the first n ´ 2 discount factors, keeping the pn ´ 1q’th discount factor same and decreasing the last discount factor. We cannot predict what happens to player n’s payoff as a result, but we can surely claim that the first n ´ 2 players’ payoffs continue to remain non-negative, player n ´ 1’s payoff remains at vn´1 and the whole payoff vector, taken together is in F . But then this new payoff vector satisfies the requirements of un´1 in the WD condition. Proceeding similarly, each of the conditions imposed in WD can be seen to be satisfied. Finally, If the ordering of the discount factors is not ‘natural’, but it is the case that δπ1 ď δπ2 ď . . . ď δπn , for some permutation π, the same argument can be easily adapted to show that v P W pπq.  Proof of Proposition 5 Part a): In this proof we borrow notation used and results derived in the proof of Proposition 3. For a given ball Bpo, rq, let ypx, c, o, k, θq refer to the continuation point when we decompose the current payoff vector x using the current action c while k, θ parametrize the discount factor vector. We let dpx, c, o, k, θq :“ ||y ´ o|| and f px, c, o, k, θq “ d2 ´ r2 .31 The arguments used in Proposition 3 shows that for the fixed ball Bpo, rq there exists a strictly positive-valued function θ̄po, kq, continuous in its arguments such that if θ P p0, θ̄po, kqq, for each x P Bpo, rq there exists a řn vertex c˚ px, o, kq with the property i“1 ki pxi ´ c˚ i qpxi ´ oi q ă 0 and for that vertex, f ă 0 and hence, d ă r.32 Define θ: pkq “ min θ̄po, kq (9.58) o P ry,zs which is well-defined and strictly positive because θ̄ is strictly positive and continuous in its arguments and because ry, zs is compact. Hence, if θ P p0, θ: pkqq, for any o P ry, zs and x P Bpo, rq, ¯ θq by there exists c, such that f ă 0 or d ă r. Now define dpk, ¯ θq :“ max dpk, max min dpx, c, o, k, θq o P ry,zs x P Bpo,rq cPC (9.59) which is well-defined and ă r because of continuity of d in x and o, the Maximum Theo¯ θq, we now have created a uniform rem and compactness of the relevant feasible sets. In dpk, bound on the distance of the continuation payoff from the center of any ball that makes up the capsule and any target point in the ball by choosing the current action to be ĉpx, o, k, θq :“ argmincPC dpx, c, o, k, θq (ties being broken using any arbitrary preference ordering among vertices).33 Now, for θ ă θ: pkq, we recursively construct the sequences tcptq u and txt u via a third sequence tot u. Define o0 “ y and x0 “ u. Of course, if u is already in Bpz, rq, we can stop 31 y, d and f also depend on r, but we ignore this for brevity’s sake as r stays fixed once we fix our capsule. This shortcut is used for other functions as well. 32 Recall that c˚ was chosen with a view to maximize the range of θ over which f stays non-positive. 33 We note in passing that ĉ depends on θ and need not be the same as c˚ . 40 immediately with T “ 0, so we assume that this is not the case. Let cp0q “ ĉpx0 , o0 , k, θq. Let x1 “ ypx0 , cp0q , o0 , k, θq. Again, we stop with T “ 1 if x1 P Bpz, rq. Otherwise, we define o1 “ argmin xPry,zs ||x ´ z||, and cp1q “ ĉpx1 , o1 , k, θq. ||x´x1 ||“r In general, given xt , ot , cptq we define (9.60) xt`1 “ ypxt , cptq , ot , k, θq t`1 o “ argmin xPry,zs ||x´xt`1 ||“r (9.61) ||x ´ z|| (9.62) cpt`1q “ ĉpxt`1 , ot`1 , k, θq and we stop the recurrence with T “ t as soon as xt P Bpz, rq. Indeed, we are assured of stopping ¯ θq, ||xt`1 ´ ot`1 || “ r which on applying in a finite number of steps because, ||ot ´ xt`1 || ď dpk, U Q ¯ θq. This implies T ď ||y´z|| Triangle Inequality ensures that ||ot ´ ot`1 || is at least r ´ dpk, ¯ r´dpk,θq and completes the proof of Part a). ¯ θq by some suitable function of θ. We start by Part b): To prove this part, we need to bound dpk, observing that the square of the d function d2 px, c, o, k, θq “ θ2 n ÿ ki2 pxi ´ ci q2 ` 2θ i“1 n ÿ ki pxi ´ ci qpxi ´ oi q ` i“1 n ÿ pxi ´ oi q2 (9.63) i“1 is convex in x.34 Now for any x ‰ o in Bpo, rq, let x̄ be the point on the surface of the ball that is r px ´ oq. Then, intersected by the ray emanating from o and going towards x, i.e. x̄ “ o ` ||x´o|| since, x is a convex combination of x̄ and o, we have: d2 px, c, o, k, θq ď maxtd2 px̄, c, o, k, θq, d2 po, c, o, k, θqu (9.64) This in turn implies that d2 px, ĉpx, o, k, θq, o, k, θq ď d2 px, ĉpx̄, o, k, θq, o, k, θq ď maxtd2 px̄, ĉpx̄, o, k, θq, o, k, θq, d2 po, ĉpx̄, o, k, θq, o, k, θqu (9.65) We will now bound each component in the max function in equation (9.65). For the first component, we note that d2 px̄, ĉpk, x̄, o, θq, o, k, θq ď d2 px̄, čpk, x̄, oq, o, k, θq (9.66) řn where čpk, x̄, oq minimizes i“1 2ki pxi ´ ci qpxi ´ oi q where the minimand, as has been shown in the the proof of Proposition 3, is strictly negative. Now by referring to equation (9.63) we see that d2 pk, x̄, ĉpk, x̄, o, θq, o, θq is less than or equal to m1 pkqθ2 ` m2 pkqθ ` r2 where m1 pkq :“ n ÿ max xPCpy,z,rq,cPC and m2 pkq :“ max min oPry,zs xPBpo,rq cPC n ÿ ki2 pxi ´ ci q2 ą 0 (9.67) i“1 2ki pxi ´ ci qpxi ´ oi q ă 0. (9.68) i“1 On the other hand, for the second of the two components in the right hand side of equation 34 This can be easily verified by checking the positive definiteness of the Hessian. 41 (9.65), we notice that both the θ term and the constant term in (9.63) drop out and hence, that component is less than or equal to m1 pkqθ2 . There exists a θ; pkq ď θ: pkq when m2 pkqθ ` r2 ě 0, and hence, for θ P p0, θ; pkqq, for all o P ry, zs, all x P Bpo, rq (including the centers of the balls), ¯ θqq2 ď m1 pkqθ2 ` m2 pkqθ ` r2 . mincPC d2 pk, x, c, o, θq ď m1 pkqθ2 ` m2 pkqθ ` r2 and hence, dpk, a ¯ θq ě r ´ m1 pkqθ2 ` m2 pkqθ ` r2 and the claim follows using the bound This shows r ´ dpk, derived on T in the proof of part a).  Proof of Theorem 6 Wlog we assume that w “ 0 and v is strictly diagonalizable for the natural order, letting u1 , . . . , un be as in the definition of the property. We will show that v is an SPNE payoff. We will first specify the equilibrium path since the equilibrium strategy is based off it. The equilibrium path will entail a ‘pre-entry path’ based on a sequence of actions lasting for T pθq periods that will transition the (required) continuation payoff from v to a point inside a ball in intpF ˚ q, with v t pθq denoting the continuation payoff at period t. The center of this ball will be un which we know, resides in intpF ˚ q. Thereafter, the equilibrium path will coincide with the path created by playing the SPNE strategy to support v T pθq pθq. Of course, to specify this strategy exactly, and hence the ‘post-entry path’ it leads to, we need to specify the radius of the ball of entry, the k vector and ensure that θ will be below a certain bound - we will do all that in due course. The pre-entry path will be broken down into n´1 stages, each stage witnessing an application of the Capsule Lemma. In the l’th stage (l “ 1, . . . , n ´ 1) we will be operating with a capsule that is situated inside the payoff space of the first l players for T l pθq periods and throughout this stage, these players’ payoff (sub)vector will stay inside that capsule. We now describe these capsules. In what follows, if x is an n-dimensional vector, the subvector consisting of its first m coordinates will be denoted as xrms. By strict diagonalizability, for every l “ 1, . . . , n ´ 1, ul rls and ul`1 rls both belong to intpF p1, . . . , lqqXRl`` . Hence, there exists r̄l such that if rl ă r̄l , the entire capsule Cpul rls, ul`1 rls, rl q also lies in intpF p1, . . . , lqq X Rl`` . This is the capsule we will work with in the l’th stage with rl to be further specified later. The purpose of operating the l’th stage is to change the continuation payoffs of players 1 through l (from what they were at the end of l ´ 1’th stage). But it is not that during stages 1 through l, the continuation payoffs of player i, where l ` 1 ď i ď n, will stay put. However, we can make these players relatively patient so that their payoffs will not change by much and thus we can maintain strict individual rationality for those players (since vi was strictly positive for all i). In particular, let ε be any number strictly below mini vi . We will show that kl ’s can be chosen so that during each of the stages 1, . . . l ´ 1, player l’s continuation payoff changes by at most ε{n (from the previous stage). This will ensure that at the beginning of stage l, his continuation payoff stays strictly positive. From stages l onwards we do not have to worry about the strict individual rationality of his continuation payoffs because for these stages they are in capsules within which every vector is strictly positive. What works here is that we choose a player’s k before his payoff becomes part of any capsule, and once done, his payoffs can be transitioned through any capsule since capsules can handle any arbitrary k vector. Given the vectors ul , l “ 1, . . . , n, we define the following anchor vectors: z 1 “ v and for 42 l “ 2, . . . , n, $ &ul i z li “ %vi for i ď l ´ 1 for i ą l ´ 1 Notice that the the first z is the target payoff vector and the last z is un , which is in intpF ˚ q. The point behind the terminology ‘anchor’ should be clear now: until the continuation payoff enters intpF ˚ q, the entire on equilibrium continuation payoff path will stay close to the following ‘piecewise-linear’ path: z 1 ÝÑ z 2 ÝÑ ¨ ¨ ¨ ÝÑ z n . In the l’th stage, all continuation payoffs v t pθq, will be zig-zagging around the line segment joining z l and z l`1 . We need to make sure that the ‘starting ball’ of the l ` 1’th stage will accommodate the continuation payoffs of players 1, . . . l arriving ‘transformed’ via the ‘ending ball’ of the previous capsule as well as the continuation payoff of player l ` 1. This is ensured by the following relation 2 between the radii of one capsule and the next: rl`1 “ rl2 ` ε2 where ε is an upper bound on by how much player l ` 1’s payoff can change up until period T 1 pθq ` ¨ ¨ ¨ ` T l pθq. As our equilibrium strategy will show, we need ‘room’ around the final ball of entry inside F ˚ to take care of offequilibrium behavior. Letting the maximum of the absolute value of the adjustment term needed to be ∆, 35 and the amount of reward for each punishing player to be 2∆, we need to have a ball ? of center un and radius rn ` 3 n ´ 1∆ fit inside intpF ˚ q. To summarize then, we impose the following restrictions on the sequence of capsule radii: Bpul rls, rl q Ă intpF p1, . . . , lqq X Rl`` l`1 Bpu rls, rl q Ă intpF p1, . . . , lqq X ? Bpun , rn ` 3 n ´ 1∆q Ă intpF ˚ q 2 rl`1 “ rl2 2 `ε Rl`` for l “ 1, . . . , n ´ 1 (9.69) for l “ 1, . . . , n ´ 1 (9.70) for some ∆ ą 0 (9.71) for l “ 1, . . . , n ´ 1, (9.72) where ε ă mini vi . Note that the first two constraints ensure that the capsule Cpul rls, ul`1 rls, rl q lies in intpF p1, . . . , lqq X Rl`` . Let m1 be the minimum any player receives in any point in any of the capsules, and let m “ minpm1 , mini vi ´ εq ą 0. Hence, m is a lower bound on any player’s continuation payoff at any point on the pre-entry path. Now define N , which we will use as the number of punishment periods, such that R V M N“ . (9.73) m Next we turn our attention to permissible patterns of discount factor vectors. We start by specifying the ki ’s. This is done recursively using part b) of the Capsule Lemma. Set k1 “ 1. Next, for any l, assuming that we already know k1 , . . . , kl we will determine kl`1 . Apply the Capsule Lemma to the j’th capsule Cpuj rjs, uj`1 rjs, rj qwhere j ď l. Using the notation from that result 1 let θ̄1j be θ; pk1 , . . . , kj q. With T j pθq being the number of periods needed to execute the procedure j described there, let tcp1q pj, θq, ¨ ¨ ¨ , cpT pθqq pj, θqu be the vertices in the original game to be played 35 As in the proofs of Theorems 1 and 2, the purpose of this adjustment is to make punishers indifferent on the various pure actions in the support of any mixed strategy that may be needed to minmax a deviating player. 43 1 to carry out the procedure.36,37 Now, we assert that there exists a θ̄1jl ď θ̄1j and a k̄l`1 , such that if kl`1 ă k̄l`1 and θ ă θ̄1jl , the maximum absolute difference between player l’s continuation payoff at the beginning of the procedure compared to that at the end of the procedure is ε{n. To ptq ptq t`1 t see this recall that for any fixed kl`1 , vl`1 pθq ´ cl`1 “ p1 ` kl`1 θqpvl`1 pθq ´ cl`1 q where cptq is the vertex played and v t pθq is player l’s continuation payoff for the t’th period during the operation. We can rewrite this as ptq t`1 t t vl`1 pθq ´ vl`1 pθq “ pkl`1 θqpvl`1 pθq ´ cl`1 q (9.74) Hence, ptq t`1 t t |vl`1 pθq ´ vl`1 pθq| “ pkl`1 θq|pvl`1 pθq ´ cl`1 q| (9.75) ď pkl`1 θq2M from which it follows that the absolute difference between beginning and end payoffs during stage j for player l is at most 2kl`1 M θT j pθq the θ-dependent part of which is bounded by the expression ˜ θ ¸ αj a `1 , rj ´ m1j θ2 ` m2j θ ` rj with αj being dpuj rjs, uj`1 rjsq and the m’s are constants depending on the capsule specification, k1 , . . . , kl but not on k . The limit of the above expression as θ tends to 0, using L’Hospital’s rule ? l`1 2αj rj ´m ε is the constant ´m and hence choosing k̄l`1 ă 4αj nM2j?rj suffices for the assertion. From the 2j above it is clear if kl`1 ă k̄l`1 and θ ă θ̄1l :“ minjďl θ̄1jl after l stages, i.e. after T 1 pθq ` ¨ ¨ ¨ ` T l pθq periods, player l ` 1’s continuation payoff could not change by more than ε from its original target value vl . If θ̄1 :“ min1ďlďn´1 θ̄1l , then given the k vector we have chosen, for θ ă θ̄1 , the above statement is true for each player. For the chosen k vector, from Fact 1 we know that there is another positive bound θ̄2 such ? that when θ ă θ̄2 , for any x P Bpun , rn ` 3 n ´ 1∆q there is a SPNE strategy σ ˚ pxq that supports and hence, realizes x. Hence, for θ ă minpθ̄1 , θ̄2 q we have designed a path that realizes v. This path involves playing the following sequence of vertices along its pre-entry segment: cp1q p1, θq, ¨ ¨ ¨ , cpT 1 pθqq p1, θq, cp1q p2, θq, ¨ ¨ ¨ , cpT 2 pθqq p2, θq, ¨ ¨ ¨ , cp1q pn ´ 1, θq, ¨ ¨ ¨ , cpT n´1 pθqq pn ´ 1, θq followed by the path yielded by σ ˚ pv T pθq q with T pθq being T 1 pθq`¨ ¨ ¨`T n´1 pθq. For notational ease we will henceforth refer to the sequence of vertices on the pre-entry path simply as c̃p1q , . . . , c̃pT pθqq . Now, we can formally describe the equilibrium strategy in the language of automata (Rubinstein 1986) as shown below. There are three types of (common) states, each identifed by a set of state variables: • A[τ, i, z] • B[τ, τ 1 , i, r] • C[x] where 1 ď τ ď T pθq, 0 ď i ď n, z P Rn where 1 ď τ ď T pθq, 1 ď τ 1 ď N , 1 ď i ď n, r P Rn where x P Rn 36 It is important to note that these are n-dimensional vertices. Though the capsule is in the projected space of players’ payoffs on the first j coordinates, playing a vertex in the projected space requires the participation of all players. 37 Note that the starting payoff for the first capsule is u1 r1s. Given a θ, the vertices to be played in each stage are now recursively defined. 44 The interpretation of an A-type state is that going forward, we have τ periods left of going through the pre-entry path, i was the last deviator (if i “ 0, no deviation ever took place), and ? z is the adjustment vector in the ball Bpun , rn ` 3 n ´ 1∆q that we will need to subtract from the equilibrium point of entry (besides giving a ‘reward’ to player(s) j ‰ i) once we are done with the pre-entry path. The interpretation of a B-type state is that we are on a punishment path where player i, the last deviator is being minmaxed and τ 1 periods of minmaxing still needs to be done while τ denotes from what type of A state we have (eventually) arrived here, and the j’th component of r denotes the normalized payoff for j ‰ i based on the past realizations of the N ´ τ 1 periods of minmaxing i (ri “ 0).38 The interpretation of a Type C state is that it is an ‘absorbing’ state where σ ˚ pxq is played from that point onwards. The game starts at the state A[T pθq, 0, 0]. For any state A[τ, i, z], c̃pT pθq´τ `1q is to be played next. If in the observed action profile, there is a unilateral deviation by player j, play switches to the state B[τ, N, j, 0]. Otherwise, play switches to A[τ ´ 1, i, z] if τ ą 1 and to Crv T pθq s if τ “ 1 and i “ 0 and to Crv T pθq ´ z ` 2∆pι ´ ei q] if τ “ 1 and i ‰ 0. For any state B[τ, τ 1 , i, r], mi is to be played next. If j is the only player whose action is not observed to be in support of mij , play switches to B[τ, N, j, 0]. Otherwise, if τ 1 ą 1, play next moves to B[τ, τ 1 ´ 1, i, r̃] where r̃j “ $ 1 N ´τ 1 ´1 qrj `δjN ´τ gj paq ’ & p1`δj `¨¨¨`δj 1 if j ‰ i ’ %0 if j “ i 1`δj `¨¨¨`δjN ´τ (9.76) with a being the last action profile observed. If on the other hand, τ 1 “ 1, play switches to A[τ, i, z] where zj “ 1´δjN δjN `τ r̃j , where r̃j is defined above. The behavior of the automata at a C type stage has already been described. We need to ensure that |zj | is suitably bounded otherwise the adjustment term could take us out of the last ball. Note that |zj | ď 1 T pθq δj 1´δjN δjN M . The limit of δj T pθq (as θ goes to 0) can be written as limθÑ0 δj T1 pθq ˆ ¨ ¨ ¨ ˆ limθÑ0 δj Tn´1 pθq . It may be easily checked that that if limθÑ0 θT l pθq is some constant, say bl (as we have shown previously), then limθÑ0 δj Tl pθq “ e´kj bl , and hence, there exists a bound θ̄3 , such that if θ ă θ̄3 , |zji | ă ∆. Given that each ‘punisher’ is rewarded by the ? amount 2∆, and ||v T pθq ´un || ď rn , this shows that ||v T pθq ´z `2∆pι´ei q´un || ď rn `3 n ´ 1∆. Next, we examine the requirements for incentive compatibility. As σ ˚ is an SPNE by construction, we only need to check for incentive compatibility at A and B type states. If the current state is A[τ, 0, 0] or A[τ, i, z] for some z, and player i did not deviate, the game will follow a certain path and he will receive a certain stage game payoff sequence. Let his normalized payoff from this be yi . If he unilaterally deviates, he receives 0 for the next N periods and thereafter, he will receive exactly the same sequence of payoffs had he not deviated at all (note that he receives neither a reward nor an adjustment post entry). Unimprovability from the prescription at a Type A state in this case is then ensured by p1 ´ δi qM ` δi N `1 yi ď yi (9.77) M {m ď 1 ` δi ` ¨ ¨ ¨ ` δiN (9.78) or, since yi ě m by which equation (9.73) assures us will hold for high enough δi and hence θ below a certain bound. 38 Note: r ‰ z. The latter will depend on τ . 45 Our next bound θ̄4 is precisely this bound. The argument for i’s unimprovability from states of the form A[τ, j, z] , pj ‰ iq is even stronger than the argument given in favor of unimprovability in the just argued case, because by sticking to the equilibrium prescription, player i would have received yi in normalized payoff plus at least an extra amount of ∆ forever after τ periods. Next consider i’s incentive to deviate from a state of the form B[τ, τ 1 , i, r]. This can’t be profitable because it will simply postpone playing the same path that has a strictly positive (normalized) payoff. Lastly, consider the prospect of i deviating from a state of the form B[τ, τ 1 , j, r], j ‰ i. The design of the adjustment term makes him indifferent between playing any of the vertices on the support of mi as can be easily verified in the usual manner. Hence, the only thing that remains to consider is his deviation to an action not in the support of mi . If equilibrium prescription is followed, i will receive at worst, 1 1 p1 ´ δiτ q. ´ M ` δiτ pyi ` δiτ ∆q (9.79) where yi is his continuation (equilibrium path) payoff at A[τ, 0, 0s. if he deviates he will receive at best p1 ´ δi qM ` δiN `1 yi (9.80) Hence the difference in i’s payoff between conforming and deviating is at least 1 1 p1 ´ δiτ q. ´ M ´ p1 ´ δi qM ` pδiτ ´ δiN `1 qyi ` δiτ ě p1 ´ δiN q. ´ M ´ p1 ´ δi qM ` pδiN ´ δiN `1 qm 1 `τ ` ∆ N `T pθq δi ∆ (9.81) řn´1 The last term in the above expression converges to the positive number e´ki b ∆ (where b “ l“1 bl ) while other terms go to 0 as δi goes to 1. Hence, there exists a positive bound θ̄5 , such that if θ ă θ̄5 , there is no incentive for i to deviate at any B[τ, τ 1 , j, r j ] type state. We can now conclude that for the chosen k vector if θ ă minpθ̄1 , θ̄2 , θ̄3 , θ̄4 , θ̄5 q, the prescribed strategy is an SPNE.  10 Appendix 2: LP 1999, Intertemporal Tradeoffs and the Realizability Problem In this appendix we contrast our findings with those of LP 1999 regarding realizability, paying special attention to realizable payoff vectors that are also Pareto-optimal. As noted before, that paper considers only two-player games and assumes that PRDs exist. LP assume that Player i values $1 received at the end of one time unit as $δ̄ now, and fixes these δ̄’s. Next, assuming that the interactions take place ∆ time units apart, they first characterize the realizable set and then examine that set as ∆ becomes small. This is equivalent to fixing the time interval between ∆ interactions to one, and letting the discount factor for i to be δi “ δ¯i , which in turn amounts to fixing the log-discount ratios in our set-up. Our Theorems 3 and 4 impose no such restrictions on discount factors. LP’s technique of characterizing the realizable set for a given ∆ (and also the limiting set) consists of characterizing its extreme points: they assert that these are normalized repeated game payoff pairs pu1 , u2 q which maximize λ1 u1 `λ2 u2 for a given direction vector λ within the realizable set. This immediately allows them to show how a certain payoff vector on the boundary of the 46 realizable set is to be realized. As an illustration, re-consider the two-player game in Figure 5. To realize γ, which gives high payoffs to both players, assuming δ¯1 ă δ¯2 (i.e. Player 2 is more patient than Player 1), LP’s method would suggest playing c4 (Player 1’s most preferred vertex) for a certain number of periods (say T1 ), followed by a possibly mixed action once (with weights on c4 and c5 only), then c5 for another few periods (say T2 ), followed by another possibly mixed action once (with weights on c5 and c6 only) and finally c6 (Player 2’s most preferred vertex) forever. These paths signal some kind of intertemporal tradeoff; as if the more patient player is ‘loaning’ to the less patient player at the start and then getting paid back later. It is instructive to see the mathematical foundation behind LP’s prescriptions. Allowing for mixing in every period, let a path be defined by the sequence αt p.q, t “ 0, 1, . . . where αt : A ÞÑ R` ř with aPA αt paq “ 1. LP make the point that when we choose a path to maximize λ1 u1 ` λ2 u2 “ ř ř8 tř t t aPA α paqgi paq, all we need to do is to pick that α in period t which i“1,2 λi t“0 p1 ´ δi q δi ř tř maximizes i“1,2 λi p1 ´ δi q δi aPA αt paqgi paq. Next, suppose we are given positive λi ’s and δ¯2 ą δ¯1 . Hence, for any ∆, as t increases, the direction vector pλ1 p1 ´ δ1 qδ1 t , λ2 p1 ´ δ2 qδ2 t q starts moving anti-clockwise, with the second term of the vector eventually dominating the first, which immediately provides a justification of the proposed path(s). Note that nothing in this argument requires players to be absolutely patient (i.e. ∆ to be small ); the argument is supposed to hold for any set of unequal discount factors. Also note that if one or more of the λi ’s are negative, a similar argument is applicable. For example, to maximize λ1 u1 ` λ2 u2 with λ1 ą 0, λ2 ă 0, LP’s suggested path will shift weight progressively over time from c4 to c3 to c2 , eventually settling on the last vertex forever. For the rest of this appendix, we will generalize LP’s notion to any number of players and different randomization set-ups. For n players, by “LP-type paths” we will mean paths that řn ř8 ř maximize i“1 λi t“0 p1 ´ δi q δi t aPA αt paqgi paq, for some non-zero vector λ P Rn . When PRDs are not available, and only independent mixing is allowed, we will impose the additional restriction śn t t that for each t and each a P A, αt paq “ i“1 αi pai q where for each i, αi : Ai ÞÑ R` with ř t ai PA αi pai q “ 1. We now make two observations about LP-type paths. First note that the economic intuition behind using these paths for realizing efficient outcomes does not extend to three or more players. Suppose λ is a strictly positive vector when obviously, all along an LP-type path, only vertices on the stage game Pareto frontier will be played. For two-player games, since on that frontier, one player’s preference ranking over vertices is exactly the reverse of the other player’s ranking, along such paths, one player (the impatient one) does get progressively worse payoffs while the other gets better payoffs. But this makes it clear that the idea of ‘loaning’ hinges on having two players, because the same argument cannot be made for three or more players: a vertex that gives the most impatient player his highest possible amount does not necessarily offer the second-most impatient player more than it does to the third-most impatient player. Moreover, while for two players with unequal discount factors, it is never possible that an LP-type path will result in a play of vertex c in some period t, then a play of a different vertex c1 in period t ` 1 and then again a play of c in period t ` 2, this can happen for three or more players; the weights on various vertices along LP-type paths are not guaranteed to move ‘monotonically’. For example, let F have these four vertices: p0, 0, 0q, p1, 1, .5q, p20, 20, 20q and p4.7, 52.3, 2.9q. Let δ “ p0.7, 0.8, 0.9q. For λ “ p 10 3 , 5, 10q, the reader can verify that in t “ 0 and 2, p20, 20, 20q is to 39 This is not an original point; LP themselves were aware of it (see subsection 5.4 of their paper, where after discussing the problem they conclude: “...Therefore, our method fails in the n-player case.”). 47 be played, while for t “ 1, p4.7, 52.3, 2.9q is to be played.39 A second feature of LP-type paths is that they could be bottom-heavy for some players, in that play will eventually settle on one of the vertices of F and that vertex could potentially result in a very low payoff for those players. From the point of view of the economist attempting to design stable cooperative agreements, this could be undesirable. Next, we offer a detailed contrast between LP’s approach and ours with regards to two different questions that may be raised regarding the realizability problem. The first questions is: Suppose a point v P intprepF q X F c is given. Is it possible to describe a set of discount factor vectors for which v is realizable and if so, via which path? We will call this the Folk Theorem question. Another, somewhat more pragmatic question is: Suppose both the target point v and the discount factor vector δ are given. Is it possible to realize v given δ, and if so, via what sort of path? We will call this the fixed δ question. Even when we assume the existence of PRDs, the LP approach has difficulty answering the Folk Theorem question, particularly for n ě 3, because their approach works by fixing relative patience parameters. Once that is fixed their approach will 1) work out the boundary of the realizable set for a given ∆ (or as ∆ goes to 0) and then 2) figure out two boundary points such that the target point is a convex combination of these two points and then 3) use the same convex combination of the paths needed to realize the boundary point. But for arbitrary relative patience configurations, the target may not belong to the realizable set even as ∆ goes to 0. Further, for more than two players, the relative patience configurations that are needed to realize a certain target as ∆ goes to 0 can be quite complex to derive, a question that the LP approach does not shed much light on. If we do not have PRD’s, the LP approach becomes inapplicable because characterizing a set by pinning down its extreme points works for a convex set, but not for non-convex sets; for such sets this method may miss many efficient payoff vectors, not to mention the fact that for a non-convex set characterizing just the boundary of the set does not characterize the full set. Convexity of the realizable set for any discount factor vector is trivial when PRDs are allowed, but from Counterexample 1 in Section 5 we know that even for large discount factors, convexity fails without PRDs. If additionally we fix relative patience of players either the way LP do (by letting ∆ 1 δi “ δ¯i while varying ∆) or the way Sugaya and we do (by letting δi “ 1`k while varying θ), iθ and let players become more and more absolutely patient, this failure still cannot be remedied. ¯ such Specifically, examining equation 5.5 in Counterexample 1 makes it clear that there is no ∆ ∆ ∆ ¯ Hence, the validity of LP’s method of characterizing the that Fpδ¯1 , δ¯2 q is convex if ∆ ă ∆. limiting set of realizable payoffs by characterizing its boundary does not extend to the PRD-less situation. Our approach, on the other hand, which does not rely on whether PRDs are present or not, is geared exactly to answer the Folk Theorem question. The proof of Theorem 3 shows that we can choose the vertices to be played on the pre-entry path in many different ways, along with the ball inside F where the continuation payoff will eventually settle, and for each such choice, we can provide many relative patience configurations (i.e. k vectors) and an absolute patience parameter bound (i.e. a θ̄ ) that are consistent with the realization of a given v. A suite of three optimization problems for doing this is available from the authors on request. Turning now to the fixed δ question, assuming PRDs, the LP approach works very nicely with n “ 2, but becomes quite complicated for more than two players. Because the monotonicity of vertex weights along the LP-type paths is now lost, it is not easy to characterize the boundary of the realizable set; for every λ and every t an optimization problem is to be solved and the whole 48 boundary can be fully described only when this solution is known for every possible λ. Furthermore, when PRDs are unavailable, and we are dealing with fixed, low discount factors, the non-convexity of the realizable set not only makes the first step of LP’s mathematical argument invalid, (that every efficient point is an argmax of a linear function of the repeated game payoffs), but the conclusion becomes invalid as well (that every such payoff must be realizable via some LPtype path). Alternate vertex switching (AVS) paths where switching among vertices takes place every period can be efficient for many situations where all players are almost equally myopic. To illustrate, the following holds: Proposition A. 1) For the stage game described in Counterexample 1, when PRD’s are disallowed but (independent) mixing is not, there exists an open ball D of discount factor vectors with center pδ, δq for some δ P p0, 1q such that when δ P D, an AVS path where players play the vertices p1, 0q and p0, 1q in alternate periods, starting with either p1, 0q or p0, 1q, is Pareto-efficient and 2) for any δ P D, where δ1 ‰ δ2 , the payoff vector generated by such a path cannot be realized by any LP-type path. The intuition behind the result is as follows. With low discount factors, an AVS path cannot be Pareto-improved by converting a pure-action payoff on its path, such as p1, 0q, to a different pure-action payoff such as p0, 1q because the lumpiness of the current loss may not be remediable even by offering the sacrificing player ‘everything’ later. If PRDs are available, the patient player might be persuaded to release a small amount of payoff to his impatient counterpart in return of getting paid back later (with interest), leading to a Pareto-improvement. However, without PRDs, small changes to a particular period’s utility can be effected by independent mixing only, which is ‘wasteful’ in the sense that it reduces the total utilities players could have in that period. If the discount factors are very close, the prospective gain from intertemporal tradeoff becomes small and is outweighed by this ‘waste’, thus making Pareto-improvements impossible. How does our approach work for the fixed δ question? Unfortunately, not very well either. It is possible to write a Mixed Integer NLP that can search if there exists a sequence of vertices to be used along the pre-entry path and a compatible ball of entry, but admittedly, it is neither simple to solve nor does it settle the fixed δ question completely, since there can be many different ways of entry into intpF q - not just via the paths used in the proof of Theorem 3. If the target point happens to be Pareto optimal (which a priori, without PRDs, there is no simple way of determining40 ), the paths suggested by our approach may never be able to realize it exactly, since, once inside intpF q, the path may feature the play of an inefficient vertex. The fixed δ question, therefore, remains a computationally challenging open problem, worthy of future investigations. Proof of Proposition A 1) The path where players alternate between the two vertices p0, 1q and p1, 0q starting with p1, 0q will be hereafter called AVS(1), and when the starting vertex is p0, 1q, we will call that path AVS(2). When players mix in a period, if one of the players gets the (undiscounted) utility x, the other ? player can get at most f pxq :“ 1 ` x ´ 2 x. 41 Henceforth, without loss of generality, we will focus attention on those paths where in each period the player’s utilities are the pair px, f pxqq for some x P r0, 1s. For future reference, we note the following four properties of f : 40 As was noted in the introduction, even for a two-player game with only two vertices in the stage game, Salonen and Vartiainen (2008) show how ‘irregular’ the Pareto frontier can be. 41 f pxq is the maximum of p1 ´ pqp1 ´ qq subject to pq ě x and p, q P r0, 1s. 49 a) For x P p0, 1q, f 1 ă 0 and f 2 ą 0, b) x ` f pxq is a strictly convex function which evaluates to 1 at 0 and 1 only within the interval [0,1] with f 1 p.25q “ 0, c) f pxq lim “ .25, xÑ1 p1 ´ xq2 d) f ´1 p.q “ f p.q. Step 1: First we construct D. Choose any δ̄ be such that c :“ p1 ´ δ̄p1 ` δ̄qqp1 ´ δ̄ 2 q ą .25. Indeed, this condition may be satisfied by choosing δ̄ small. Note that it implies the following condition: p1 ´ δ̄p1 ` δ̄qq ą .25. Let ε1 “ c ´ .25 and let r1 be such that if δ P Bpδ̄ι, r1 q, the following hold: 1 ´ δi p1 ` δi q ą .25 δi ą δj2 δi2 q2 p1 ´ δi p1 ` δi qqp1 ´ ą c ´ .5ε1 1 ´ δj2 ˜ ¸ δj δi `f ă1 1 ´ δi2 1 ´ δj2 for i “ 1, 2 (10.1) for i “ 1, 2, j ‰ i (10.2) for i “ 1, 2, j ‰ i (10.3) for i “ 1, 2, j ‰ i (10.4) Clearly, a small enough r1 can be chosen to satisfy the above given the choice of δ̄ and property b) of f . Because of property c) of f , there is an η ă .75 such that f pxq ă .25 ` .5ε1 p1 ´ xq2 for x ą 1 ´ η. (10.5) Define ε2 via the following: p1 ´ ηq ` f p1 ´ ηq “ 1 ´ ε2 . (10.6) Let r2 be such that when δ P Bpδ̄ι, r2 q 1 δj δm ` ´ ą 1 ´ ε2 1 ´ δi2 1 ´ δj2 1 ´ δm for i “ 1, 2, j ‰ i (10.7) where δm “ maxpδ1 , δ2 q. Since, the left hand side of the above tends to 1 as both δ1 and δ2 tend to δ̄, it is possible to satisfy (10.7) by choosing r2 small. Let r “ minpr1 , r2 q. Then D “ Bpδ̄ι, rq. Step 2. We show that for any pδ1 , δ2 q pairs satisfying a less stringent condition than (10.1), namely 1 ą δi p1 ` δi q for i “ 1, 2 (10.8) both AVS(1) and AVS(2) are Pareto-optimal within the class of paths that employ pure actions only. To see this for AVS(1), note that playing the prescribed strategy offers Player 1 the amount 1 ` δ12 ` δ14 ` . . . in undiscounted payoff; if p1, 0q is not played at t “ 0, even if it was played for all t ą 0, he would earn at most δ1 ` δ12 ` δ13 ` . . .; which is less than his prescription payoff if 50 δ1 or 1 ą δ1 p1 ` δ1 q. Hence, if any other payoff vector Pareto-dominates the payoff from ą 1´δ 1 the prescribed path, it must also start with the play of p1, 0q. Given this, an analogous argument from Player 2’s perspective shows that p0, 1q must be played in t “ 1 and now this argument can be carried forward ad infinitum. A similar logic establishes the efficiency of AVS(2) within the limited class of pure action paths. 1 1´δ12 Step 3: Next, we consider (independent) mixing. In this step, focusing on AVS(1), we show that for discount factors obeying (10.8), if AVS(1) is not Pareto-optimal, then either AVS(1) or AVS(2) is Pareto-improvable by a path that involves strict mixing only in t “ 0. To see this consider the following optimization problem: Choose a sequence txt u8 t“0 to maximize 8 ÿ δ1t xt ` t“0 8 ÿ δ1t f pxt q t“0 subject to 8 ÿ δ1t xt ě 1 1 ´ δ12 (10.9) δ2t f pxt q ě δ2 1 ´ δ22 (10.10) t“0 8 ÿ t“0 xt P r0, 1s t “ 0, 1, 2... (10.11) A standard compactness-continuity argument (in the product topology) shows that the problem has a solution. If AVS(1) is not Pareto-optimal, the existence of a solution to the above problem provides us with an alternate path that Pareto improves on it and is itself Pareto-optimal. Call it the challenger path. Because of its Pareto optimality, we now claim that along the challenger path, a mixed action can be played in at most one period. Suppose, by contradiction, in period t, players receive the utility pair px˚t , f px˚t qq and in period s ą t, they receive another utility pair px˚s , f px˚s qq where both x˚t , x˚s P p0, 1q. In the xt ´ xs space, Player 1 has linear indifference curves with direction of increasing utility north and east, (his utility function, having fixed his payoffs in all other periods is δ1t xt ` δ1s xs ). Player 2 on the other hand has indifference curves that are convex to the origin, with the direction of increasing utility being south and west (his utility function is δ2t f pxt q ` δ2s f pxs q, which is quasi-convex, a claim that can be verified using property a) of the function f stated earlier). Clearly a strictly mutually beneficial readjustment of the two actions can be organized if the two players’ indifference curves are not tangent at px˚t , x˚s q, but even in the case of tangency, it is easy to verify pictorially that there will be room for Pareto-improvement by moving away from the point of tangency in either direction along Player 1’s indifference curve. This proves the claim. Suppose the challenger path involves mixed action only in period T . We could then, using exactly the same argument used in Step 1 conclude that as long as the condition (10.8) holds, the challenger path coincides with AVS(1) for all periods up to and including T ´ 1. This in turn shows that there is a challenger path that involves playing a strictly mixed action on t “ 0 and pure actions thereafter that Pareto-improves either on AVS(1) or on AVS(2) (which it is depends on whether T is even or odd). Step 4. We now will show that for δ P D, AVS(1) could not be Pareto- improved by a challenger 51 path that mixes only in t “ 0 (the argument for AVS(2) being symmetric will be omitted). For this challenger path, let πiτ denote what Player i receives in unnormalized payoff on a path the t’th period action of which concides t ` τ ’th period action of the challenger path. Then, there exists x P p0, 1q such that the following equations hold: 1 1 ´ δ12 δ2 f pxq ` δ2 π21 ě 1 ´ δ22 (10.12) x ` δ1 π11 ě (10.13) with at least one of the inequalities being strict. If we add the two above inequalities we obtain: δ2 1 ` ´ pδ1 π11 ` δ2 π21 q 1 ´ δ12 1 ´ δ22 1 δ2 ě ` ´ δm pπ11 ` π21 q 1 ´ δ12 1 ´ δ22 1 δ2 δm ě ` ´ 1 ´ δ12 1 ´ δ22 1 ´ δm (10.15) ą 1 ´ ε2 , (10.17) (10.14) x ` f pxq ą (10.16) the last inequality following from (10.7). Now x`f pxq can be above a certain value if either x is low 1 , (<.25, the argmin) or high (above .25). We rule out the first possibility by noting that π11 ď 1´δ 1 1 p1`δ1 q which paired with (10.12) gives us a lower bound on x: 1´δ1´δ ą p1 ´ δ1 p1 ` δ1 q ą .25, because 2 1 of (10.1). Now, because of the definition of η in (10.6) allows us to conclude that 1 ´ x ă η. The challenger path clearly must differ from AVS(1) not just in t “ 0, but in some subsequent period as well. Let T be the first time after t “ 0 when this change occurs. Taking advantage of the fact that the challenger path from T onward uses only pure actions, we can see that T can’t 1 be even because then we will have x ` δ1T π1T ě 1 ` δ1T 1´δ 2 , or equivalently 1 ˆ ˙ 1 1 ´ x ď δ1T π1T ´ 1 ´ δ12 ˆ ˙ 1 δ1 ´ ď δ1T 1 ´ δ1 1 ´ δ12 δ1 p1 ` δ1 q ´ 1 ď δ1T 1 ´ δ12 (10.18) (10.19) (10.20) ă 0, (10.21) an impossibility. If on the other hand, T is odd, a similar argument provides a positive upper bound on 1 ´ x: ˆ ˙ δ1 1 ´ x ď δ1T π1T ´ (10.22) 1 ´ δ12 ˆ ˙ 1 δ1 ď δ1T ´ (10.23) 1 ´ δ1 1 ´ δ12 1 ď δ1T . (10.24) 1 ´ δ12 1 Also, if T is odd, for the second player, we will have f pxq ` δ2T π2T ě 0 ` δ2T 1´δ 2 , which can be used 2 52 to find a lower bound on f pxq: ˙ 1 T ´ π2 f pxq ě 1 ´ δ22 ˆ ˙ 1 δ2 T ě δ2 ´ 1 ´ δ22 1 ´ δ2 1 ´ δ p1 ` δ 2 2q . ě δ2T 2 1 ´ δ2 ˆ (10.25) δ2T (10.26) (10.27) Now combining (10.24) and (10.27), we observe that f pxq ě p1 ´ xq2 ˆ Because of (10.2), no matter what T is ´ δ2 δ12 δ2 δ12 ˙T ¯T p1 ´ δ2 p1 ` δ2 qqp1 ´ δ12 q2 1 ´ δ22 (10.28) will exceed 1, and because of (10.3), will exceed c ´ .5ε1 . On the other hand, because 1 ´ x ă η, and (10.5), the definition of ε1 , this creates a contradiction. f pxq p1´xq2 p1´δ2 p1`δ2 qqp1´δ12 q2 1´δ22 ă .25 ` .5ε1 . Given 2) For fixed λ, we will call a path that is a solution to the LP problem when δ1 ą δ2 an LP(1) path; similarly an LP(2) path is one that solves LP’s problem when δ2 ą δ1 . We show that neither an LP(1) path nor an LP(2) path can attain the payoffs realized by the AVS(1) path. The case of AVS(2) is similar and will be omitted. Clearly, if an LP-type path was to realize the payoffs attained by either an AVS(1) or an AVS(2) path λ must be a strictly positive vector. Since in that case, the path must eventually settle on either p1, 0q or p0, 1q and since any path involving only pure actions cannot realize the payoffs obtained by AVS(1) without coinciding with AVS(1), for an LP path to attain AVS(1) payoffs there must be mixing involved; further given δ1 ‰ δ2 , such mixing can take place in at most one period. Suppose an LP(2) path uses independent mixing for the first and only time on t “ T ; thereafter p0, 1q is played. T can’t be 0 because the maximum Player 1 can then receive on the LP(2) path 1 (which is 1) is strictly less than what he was receiving in the AVS(1) path (which is 1´δ 2 ). Also, T δ2 1 2 can’t be 2 because then the maximum Player 2 would receive in the PVS(1) path ( 1´δ ) is strictly 2 δ2 less than what he receives in AVS(1) path ( 1´δ2 ), because of (10.8). Hence, T “ 1, and there is 2 some x P p0, 1q such that the following equations hold: 1 1 ´ δ12 δ22 δ2 0 ` δ2 f pxq ` “ 1 ´ δ2 1 ´ δ22 1 ` δ1 x “ Equation (10.29) gives x “ 1´ δ2 . 1´δ22 δ1 , 1´δ12 (10.29) (10.30) while equation (10.30) can be solved for f pxq to show f pxq “ Together they imply ˆ f δ1 1 ´ δ12 ˙ “1´ δ2 . 1 ´ δ22 (10.31) But this contradicts (10.4). Next, suppose LP(1) path attains the payoffs realized by the AVS(1) path. Suppose the mixing period is T ; for t ą T , p1, 0q is played. Then T has to be period 0, because we have already 53 established that even if Player 1 gets 1 for all periods from t “ 1 onward, his target still cannot be met. Hence, there exists x P p0, 1q such that x` δ1 1 “ 1 ´ δ1 1 ´ δ12 δ2 f pxq “ 1 ´ δ22 (10.32) (10.33) δ1 Equation (10.32) shows x “ 1 ´ 1´δ 2 , while equation (10.33) upon using property d) of the f 1 ´ ¯ δ2 function shows that x “ f 1´δ . Hence, 2 2 ˆ f δ2 1 ´ δ22 ˙ “1´ which again violates (10.4). This completes the proof. 54 δ1 . 1 ´ δ12 (10.34)