University:
Boston University
Course:
CAS EC 203 | Empirical Economics 1
Academic year:

2024
Views:

199

Pages:

12
Author:

amenablyccue

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 (8.7) is valid with δ being replaced by δi (since δi is at least as large as δ and hence δ 1 ), Thus, we have 1 δi ¥ v1 M ∆ @i . δi N ... (8.34) i Similarly, we may argue, since δi ¥ δ ¥ δ2 , δiN ¥ M M ∆ @i. (8.35) Define ∆i : ∆ 11δδi . From the previous inequality it also follows that δiN 1 1 ¥ v1 vi ∆ ¥ vvi1 ∆∆i @i.. i (8.36) i Next, we describe the strategies which follow the standard three-phase pattern used previously. Since δ ¥ δι, and B pv, ∆q is self-accessible for δι, via Proposition 4, we know that the ellipsoid E pv, ∆, δ, δ q B pv, ∆q is self-accessible for δ. In Phase I, it is prescribed that the players play the sequence taptq pv, E pv, ∆, δ, δ qqu8 t0 . 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 (8.11) and (8.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 , E pv 1 piq z i , ∆, δ, δ qqu8 t0 . 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 p 1 δi q M δi N 1 pvi1 ∆i q ¤ vi ∆i , (8.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. (8.38) • For unimprovability from Phase III(i), it suffices to have p1 δi qM δi N 1 pvi1 ∆i q ¤ vi1 ∆i . (8.39) • Unimprovability from Phase II(j), after identical analysis undertaken before, is assured by: p1 δi qM δiN 1 pvi1 ∆i q ¤ δiN 32 vi1 ∆ . (8.40) • Lastly, for unimprovability from Phase III(j) it suffices to have: p1 δi qM δiN 1 vi1 ¤ vi1 . (8.41) As in the previous proof, the nontrivial inequalities (8.37), (8.41) are directly guaranteed by (8.39) while (8.40) is guaranteed by (8.39) because of (8.36). (8.39) is itself guaranteed by (8.34) and 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 B pu, rq intpF q. Then, there exists a uniform discount factor bound δ such that when δ P rδ, 1q, every point v P B pu, rq is an SPNE payoff for δ δι. To see this, consider the set V pεq tv 1 : v 1 u1 ει, u1 P B B pu, rqu where B B pu, rq is the lower boundary of B pu, rq. Clearly, there exists a ε small enough, say ε̄ such that V pε̄q is inside intpF q. For every point v in B pu, 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 p8.3q and p8.4Uq Q 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 bounds can can be chosen for δ 3 as v varies over the compact set B pu, rq since the proof of Proposition 1 plus an application of Maximum Theorem shows that the discount factor bound found in that proposition is continuos 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 B pu, rq. Now Fact 1 follows from this the same way Theorem 2 follows from Theorem 1. Proof of Theorem 3 Step 1. Let k ¡¡ 0 and player i’s discount factor be given by δi 1 1ki θ where for now, θ, a 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 ṽ 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 ṽ : limθÑ0 ṽ pθq is. If xt denotes the continuation payoff during the t’th period of any path, and in the t’th period vertex c is played, then for each i the following holds: xti p1 δi qci δi xit 1 . Since δi 1 1ki θ , we can rewrite this as xti 1 ci p1 ki θqpxti ci q. (8.42) Hence, reasoning recursively, if c is played for T periods in periods t, t 33 1, . . . t T 1, then for each i, xti T ci p1 ki θqT pxti ci q. (8.43) 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 xti θ T Ñ0 ci ek b pxti ci q. (8.44) i 1 phase path discussed above if m 1, Hence, in the context of the m p1q eki b1 pv ṽi ci i cpi1q q (8.45) and therefore using the same idea twice, if m 2, p2q eki b2 pcp1q ṽi ci e p1q q cp2q q eki b1 pvi ci i ki b2 pcpi1q cpi2q q eki pb2 i b1 q pvi cp1q q (8.46) i Proceeding inductively, we conclude that for arbitrary integer m, for each i we will have pmq eki bm pcpm1q cpmq q eki pbm i i ṽi ci bm1 q pcpm2q cpm1q q i i eki pbm b1 q pvi cp1q q (8.47) i 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 pcpn1q cpnq q ek1 pbn 1 1 p nq k2 bn pn1q v̂2 c2 e pc2 cp2nq q ek1 pbn v̂1 c1 v̂n cpnnq .. . ek b pcpnn1q cpnnq q n n ek1 pbn q pcpn2q cpn1q q 1 1 bn1 q pn2q pc cpn1q q ek1 pbn ek1 pbn q pv1 cp1q q 1 b1 q pv2 cp1q q q pcpn2q cpn1q q ekn pbn bn1 2 bn1 n 2 n b1 2 b1 q pvn cp1q q n (8.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 ek1 b2 pcp1q cp2q q ek1 pb2 1 1 p 2q k2 b2 p1q v̂2 c2 e pc2 cp22q q ek2 pb2 q pv1 cp1q q 1 b1 q pv cp1q q v̂1 c1 b1 2 2 (8.49) (8.50) Now choose vertices cp1q , cp2q satisfying the conditions below. p1q q sgnpv̂1 v1 q sgnpv1 c1 p2q sgnpv̂2 v2 q sgnpv2 c2 q Note that since v̂i (8.51) (8.52) vi for all i, and both v̂ and v are in intprepC qq, it is possible to find two such 34 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 (8.49) and (8.50). After some cancellations, the second equation can be rewritten as v̂2 v2 ppv2 cp22q q p1q q q p v2 c 2 (8.53) while the first equation becomes p2q p1 pqk1 pcp1q cp2q q 1 1 v̂1 c1 p1 p p1q q. q qk1 pv1 c1 (8.54) We are interested in positive k1 , p, q that will solve this pair of equations. In (8.53), we can choose p 1q q to be very small and strictly positive such that sgnppv̂2 v2 q q pv2 c2 qq sgnpv̂2 v2 q, and then because of (8.52), we can find a positive p that solves (8.53). From p and q, b1 and b2 may be extracted. Turning to equation (8.54), we note that if k1 Ñ 0, sgnpRHS LHS q is the same as sgnpv1 v̂1 q. On the other hand, as k1 Ñ 8, because of the positivity of p and q, sgnpRHS LHS q p 1q is the same as sgnpv1 c1 q. Hence, by the Intermediate Value Theorem, there exists k1 ¡ 0 which p 1q p1q solves the equation if sgnpv1 v̂1 q sgnpv1 c1 q or sgnpv̂1 v1 q sgnpv1 c1 q. But this is just (8.51).24 Now, we show that for any m n, and for any ε ¡ 0 if an ε-solution exists for m 1 equation p iq version of (8.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 (8.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 p 1q 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 p 2q 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 p 1q 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, ṽ, the limit 24 Writing equation (8.54) as a bxk cy k where y ¡ x ¡ 1, it is easily seen that for k1 ¥ 1 1 lnp |a||c||b| q{lnp xy q, sgn(RHS - LHS) =sgn(c). Now the method of bisection can be used to identify the so- lution to an arbitrary desired degree of precision. 35 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 ṽ pθq is at most ν {3 away from its limit point ṽ. This will ensure that when θ θ̄1 , for the ki ’s chosen, and for δi 1 1ki θ , at the end of the first n phases, the required continuation payoff ṽ 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 B pu, ν q self-accessible as demonstrated in Proposition 3. Then, when θ θ̄ minpθ̄1 , θ̄2 q, we can simultaneously ensure that ṽ pθq is inside B pv̂, ν q and that there is a sequence of actions that generate ṽ pθq. Combining this last phase with the n phases described in Step 1, it follows that for discount factors given by δi 1 1ki θ with θ θ̄, the n 1 phase path described in that step will indeed realize v. Proof of Theorem 4 We first demonstrate the inclusion: tF pδ 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 ° it is also true that xi p1 δj q δjt gi paptq q for any δj . For player j 3 i, of course we have ° t xj p1 δj q δj gj paptq q. Therefore, we can write the vector equality using j’s discount factor: ° x p1 δj q δjt g paptq q, where each g paptq q P Cie . This implies x P copCie q F .25 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 F pδι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. st p1 δqrvt δv t 1 δ2 vt 2 s where v t is the player’s actual payoff in period t. Equation (8.55) implies hence, st st 1 vt δ . 1δ 1δ 25 (8.55) st 1 δ vt δ s1δ t 1 and (8.56) 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. 36 Similarly let s̃t be the continuation payoff from t onwards with the discount factor δ̃. Using equations (8.55) and (8.56), we can write that as s̃ t p1 δ̃q 11 δ̃δ ¥ 0 st 1δ st δst 1 1δ pδ̃ δqst δ̃ 1 st 1 1δ δ̃ pδ̃ δ qst δst 2 1δ 2 δ̃ 2 st 2 1δ δst 3 1δ (8.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 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 δn1 ; 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 vn1 and the whole payoff vector, taken together is in F . But then this new payoff vector satisfies the requirements of un1 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 B po, rq, let y px, 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 .26 The arguments used in Proposition 3 shows that for the fixed ball B po, 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 B po, rq there exists a °n vertex c px, o, kq with the property i1 ki pxi c i qpxi oi q 0 and for that vertex, f 0 and hence, d r.27 Define θ: pkq min θ̄po, kq (8.58) o P ry,zs which is well-defined and strictly positive because θ̄ is strictly positive and continuous in its arguments and because ry, z s is compact. Hence, if θ P p0, θ: pkqq, for any o P ry, z s and x P B po, rq, 26 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. 27 Recall that c was chosen with a view to maximize the range of θ over which f stays non-positive. 37 there exists c, such that f r. Now define d¯pk, θq by 0 or d d¯pk, θq : max o max min dpx, c, o, k, θq (8.59) P ry,zs x P Bpo,rq cPC which is well-defined and r because of continuity of d in x and o, the Maximum Theorem and compactness of the relevant feasible sets. In d¯pk, θq, we now have created a uniform 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 ĉpx, o, k, θq : argmincPC dpx, c, o, k, θq (ties being broken using any arbitrary preference ordering among vertices).28 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 B pz, rq, we can stop immediately with T 0, so we assume that this is not the case. Let cp0q ĉpx0 , o0 , k, θq. Let x1 y px0 , cp0q , o0 , k, θq. Again, we stop with T 1 if x1 P B pz, rq. Otherwise, we define o1 argmin xPry,zs ||x z ||, and cp1q ĉpx1 , o1 , k, θq. ||xx1 ||r In general, given xt , ot , cptq we define ypxt , cptq , ot , k, θq ot 1 argmin Pr s ||x z || || || p t 1q t 1 t 1 c ĉpx , o , k, θq xt 1 x x y,z xt 1 (8.60) (8.61) r (8.62) and we stop the recurrence with T t as soon as xt P B pz, rq. Indeed, we are assured of stopping in a finite number of steps because, ||ot xt 1 || ¤ d¯pk, θq, ||xt 1 ot 1 || r which onQ applyingU ||yz|| Triangle Inequality ensures that ||ot ot 1 || is at least r d¯pk, θq. This implies T ¤ r d¯pk,θ q and completes the proof of Part a). Part b): To prove this part, we need to bound d¯pk, θq by some suitable function of θ. We start by observing that the square of the d function d2 px, c, o, k, θq θ2 n ¸ i 1 ki2 pxi ci q2 2θ n ¸ ki pxi ci qpxi oi q i 1 n ¸ pxi oi q2 (8.63) i 1 is convex in x.29 Now for any x o in B po, rq, let x̄ be the point on the surface of the ball that is r intersected by the ray emanating from o and going towards x, i.e. x̄ o ||x o|| px oq. Then, 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 (8.64) This in turn implies that d2 px, ĉpx, o, k, θq, o, k, θq ¤ d2 px, ĉpx̄, o, k, θq, o, k, θq ¤ maxtd2 px̄, ĉpx̄, o, k, θq, o, k, θq, d2 po, ĉpx̄, o, k, θq, o, k, θqu (8.65) We will now bound each component in the max function in equation (8.65). For the first component, 28 29 We note in passing that ĉ depends on θ and need not be the same as c . This can be easily verified by checking the positive definiteness of the Hessian. 38 we note that d2 pk, x̄, ĉpk, x̄, o, θq, o, θq ¤ d2 pk, x̄, čpk, x̄, oq, o, θq (8.66) °n where čpk, x̄, oq minimizes i1 2ki pxi ci qpxi oi q where the minimand, as argued before, is strictly negative. Now by referring to equation (8.63) we see that d2 pk, x̄, ĉpk, x̄, o, θq, o, θq is less than or equal to m1 pkqθ2 m2 pkqθ r2 where m1 pkq : and Pp n ¸ max q P x C y,z,r ,c C n ¸ ki2 pxi ci q2 ¡0 (8.67) i 1 m2 pkq : max min 2ki pxi ci qpxi oi q oPry,z s cPC i1 xPB po,r q 0. (8.68) On the other hand, for the second of the two components in the right hand side of equation (8.65), we notice that both the θ term and the constant term in (8.63) drops out and hence, it is less than or equal to m1 pkqθ2 . There exists a θ; pk, θq ¤ θ: pk, θq when m2 pkqθ r2 ¥ 0, and hence, for θ P p0, θ; pk, θqq, for all o P ry, z s, all x P B po, rq (including the centers of the balls), mincPC d2 pk, x, c, o, θq ¤ m1 pkqθ2 m2 pkqθ r2 and hence, d¯pk, θqq2 ¤ m1 pkqθ2 m2 pkqθ r2 . a This shows r d¯pk, θq ¥ r m1 pkqθ2 m2 pkqθ r2 and the claim follows using the bound 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 inside intpF q, with v t pθq denoting what the continuation payoff is 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. As was clarified in Section 7, 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. 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 and Fact 3, for every l 1, . . . , n 1, ul rls and ul 1 rls both belong to intpF p1, . . . , lqq X Rl (recall that F p1, . . . , lq is the convex hull of P rojt1,...,lu C). Hence, there exists r̄l such that if rl r̄l , the entire capsule C pul rls, ul 1 rls, rl q also lies in intpF p1, . . . , lqqX 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 39 we can maintain strict individual rationality for those players (since vi was strictly positive for all i). In particular, let ε be any number below mini vi . We will show, kl for l ¡ 1 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 l 2, . . . , n, $ z li & for i ¤ l 1 l %ui for i ¡ l 1 vi Notice that the the first z is the target payoff v is 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 between the radii of one capsule and the next: rl2 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 rquilibrium strategy will show, we need ‘room’ around the final ball of entry inside F to take care of offequilibrium behavior; if the maximum of the absolute value of the adjustment term is ∆ and the amount of reward for punishing players is 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: B pul rls, rl q intpF p1, . . . , lqq X Rl B pun , rn B pu ? 3 rls, rl q intpF p1, . . . , lqq X R n 1∆q intpF q rl2 1 rl2 ε2 l 1 l for l 1, . . . , n 1 for l 1, . . . , n 1 for some ∆ ¡ 0 for l 1, . . . , n 1, (8.69) (8.70) (8.71) (8.72) where ε ¤ mini vi . Note that the first two constraints ensure that the capsule C pul rls, ul 1 rls, rl q lies in intpF p1, . . . , lqq X Rl . Let m be the minimum any player receives in any point in any of the capsules. Hence, m is also 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 N R V M . m 40 (8.73) 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 C puj rj s, uj 1 rj s, rj qwhere j ¤ l. Using the notation from that 1 be θ; pk1 , . . . , kj q. With T j pθq being the number of periods needed to execute the result let θ̄1,j j procedure described there, let tcp1q pj, θq, , cpT pθqq pj, θqu be the vertices in the original game 1 and a to be played to carry out the procedure.30 Now, we assert that there exists a θ̄1jl ¤ θ̄1j 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 p tq p tq is ε{n. To see this recall that for any fixed kl 1 , vlt 11 pθq cl 1 p1 kl 1 θqpvlt 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 vlt 1 1 pθq vlt 1 pθq pkl qpvlt 1 pθq cpl tq1 q (8.74) q|pvlt 1 pθq cpl tq1 q| 1 θ q2M (8.75) 1θ Hence, |vlt 11 pθq vlt 1 pθq| pkl ¤ pkl 1θ 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 θ rj αj m1j θ2 m2j θ a rj 1 , with αj being dpuj rj s, uj 1 rj sq and the m’s are constants depending on the cylinder, k1 , . . . , kl but not on k? l 1 . The limit of the above expression as θ tends to 0, using L’Hospital’s rule is the 2αj rj m2j?ε constant m2j and hence choosing k̄l 1 4αj nM rj suffices for the assertion. From the 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¤n1 θ̄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 B pun , rn 3 n 1∆q there is a SPNE strategy σ pxq that 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 n1 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 n1 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 30 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. 41 1986) as shown below. There are three types of (common) states, each identifed by a set of state variables: ¤ T pθq, 0 ¤ i ¤ n, z P Rn B[τ, τ 1 , i, r i ] where 1 ¤ τ ¤ T pθq, 1 ¤ τ 1 ¤ N , 1 ¤ i ¤ n, r i P Rn C[x] where x P Rn • A[τ, i, z] • • where 1 ¤ τ 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, a deviation never took place), and ? z is the adjustment vector in the ball B pun , 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 i denotes the normalized payoff for j i based on the past realizations of the N τ 1 periods of minmaxing i (rii 0).31 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 z 2∆pι ei q] if τ 1. For any state B[τ, τ 1 , i, r i ], 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̃ i ] where $ ' & gj paq 1 δjN τ rji i if j i (8.76) with a being the last action profile observed. If on the other hand, τ 1 1, play switches to A[τ, i, z] r̃ji where zji ' δj rji 1 δj %0 δjN τ 1 if j r̃i , where r̃i is defined above. The behavior of the automaton at a C type stage j δN τ j 1 δjN j has already been described. We need to ensure that |zji | is suitably bounded otherwise the adjustment term could take us out of the last ball. Note that |zji | ¤ 1 pq T θ δj M . The limit of δ T pθq (as θ goes to 0) can be written j 1 δjN δjN as limθÑ0 δj T1 pθq limθÑ0 δj Tn1 pθq . It may be easily checked that that if limθÑ0 θT l pθq bl , θ̄3 , |zji | then limθÑ0 δj Tl pθq ekj bl , and hence, there exists a bound θ̄3 , such that if θ ∆. T pθ q n Given that each ‘punisher’ is rewarded by the amount 2∆, and ||v u || ¤ rn , this shows that ? ||vT 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 unileterally deviates, he receives 0 for the next N periods and therafter, 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 31 Note: r z. The latter will depend on τ . 42 the prescription at a Type A state in this case is then ensured by or, since yi ¥ m by p1 δqM δN 1 yi ¤ yi (8.77) M {m ¤ 1 δi δiN (8.78) which equation (8.73) assures us will hold for high enough δi and hence θ below a certain bound. 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 the argument for unimprovability in the just argued case, because by sticking to the equilibrium prescription, he 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 i ]. 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 ], j i. If equilibrium prescription is followed, i will receive at worst, p1 δiτ 1 q. M 1 δiτ pyi δiτ ∆q (8.79) where yi is as before. if he deviates he will receive at best p1 δi qM δiN 1 yi (8.80) Hence the difference in i’s payoff between conforming and deviating is p1 δiτ 1 q. M p1 δi qM pδiτ 1 δiN 1 qyi δiτ 1 τ ∆ ¥ p1 δiN q. M p1 δi qM pδiN δiN 1 qm δiN T pθq ∆ (8.81) The last term in the above expression converges to the positive number eki b ∆ 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 1 j incentive for i to deviate at any B[τ, τ , j, r ] 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. 43