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

2020
Views:

384

Pages:

19
Author:

xgclover183xz422

ω ω 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 extence 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 critical discount factor bound needed to support a given payoff vector in F zB F . 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 pln δq1, in our proof, we fix it once and for all. We believe that this is a desirable feature of our strategies, practically relevant when there is a possibility of players being susceptible to involuntary mistakes or trembles with minute probabilities. Theorem 1. Let F be full-dimensional and let v such that for all δ P F zBF . Then, there exists δ P p0, 1q 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 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 completeness’s sake and also because, the proof applies with little change to a similar theorem in the asymmetric discounting 13 setting. It relies on the standard architecture of equilibrium strategies introduced in FM 1986 characterized in terms of 3 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.17 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, in the very next period, 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 period become unboundedly large as the discount factor approaches one. In our proof, the target Phase III(i) payoff is u εei , the lowest point (from i’s perspective) in a self-accessible ball (since there is no requirement that a target payoff must be in its center). Thus the perverse situation described above where a patient player wants to restart his own punishment never arises in our case and δ-independent punishment periods can indeed be devised to wipe out the gains from deviation. Asymmetric Discounting: Supporting Points in intpF q 5 In this section, we show that any point in the inerior of F is both realizable and supportable provided the discount factors are large enough. 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 invalid. Next we show that if the discount rate ratios are not fixed, not even small balls are self-accessible for large enough discount factors. However, if they are, closed balls can be shown to be self-accessible for computable sets of discount factors. Lastly, we show that for any ball, there is a discount factor bound, such that for a discount factor vector where each component exceeds this bound, one can always find a self-accessible ellipsoid within the ball that is self-accessible relative to that specific discount factor vector. This last result leads to an asymmetric counterpart of Theorem 1. 5.1 Two Negative Results One might hope that the following ‘global’ extension of Sorin’s lemma to unequal dis- Rn is a finite set there exists δ P r0, 1q such that if δj ¥ δ for and x P copC q, there exists a sequence of points tcptq u8 t0 in C for which counting holds: If C 1 ¤ j ¤ n, 17 It is during this phase that players j i are rewarded for participating in i’s punishment phase. 14 p1 δj q °8t0 δj t cpjtq. It is easy to see that as stated, the conjecture cannot be true: for example, when n L 2 (whereupon copC q is a one-dimensional set with just two vertices) we need the two discount factors to be equal in order to realize points in copC q. Is this then an artifact of copC q not being full-dimensional or x lying on the boundary rather than in the interior of copC q? Are points that defy the desired representation non-generic? xj Unfortunately, the problem runs deeper. 2, with C tp1, 0q, p0, 0q, p0, 1qu. Let any δ P p0, 1q be given. We will show the existence of an open set in copC q and a δ1 , δ2 pair both at least as Counterexample 1. Let n large as δ 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) δ2 T ε2 , (5.3) p1 δ 1 q δ 1 T 1 ¡ ε1 . (5.4) We assert that the point p1 ε1 , ε2 q, which is in intpcopC qq 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 δ1q 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 δ1q pδ1q2 ¥ 1 ε1; from this it follows that ε1 ¥ p1 δ1q δ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 . 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 . For integer t, notice that the function δt 1 t 1 1 t 1 t Ñ0 (5.5) as t goes to infinity, and hence there exists an integer T for which a) the expression above denominator in (5.5) , open set of ε1 , ε2 pairs ¡ T 1 δ. Now, if T 1 1 T 1 is 1 δ1 T 1 T such that 0 δ2T ε2 is strictly below 1, and b) p we define δ1 T 1 T , then, for t T the qδ1 . Hence, if δ2 δ, we can choose an ε1 p1 δ1 qδ1 T 1 and we have fulfilled T 1 all our requirements. This shows that, no matter how high the discount factors are forced 15 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. It then seems natural to invoke self-accessibility. In analogy with the equal-discounting Rn is a finite set with an n-dimensional convex hull, for any x in the interior of copC q there exists a quantity r ¡ 0 and a cutoff δ such that the ball B px, 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. Let n 2, with C tp1, 1q, p1, 1q, p1, 1q, p1, 1qu. Take any ball B pp0, 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 y pδ q case, one might conjecture the following ‘local’ property. If C via the equation p1 δiq ci δi yipδq for i 1, 2, (5.6) then, y pδ q P B pp0, 0q, rq. Write δ 1{p1 θq and choose δ1 δ, and δ2 1{p1 k2 θq for k2 P p0, 1q; this ensures that δ2 ¥ δ. Now specifically let us consider the point x p0, rq and ask which c P C will make the y pδ q given via (5.6) lie in the ball. It is easy to see that the vertices p1, 1q and p1, 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 pθ, r k2θpr 1qq. Hence, y pδ q Ñ pθ, rq as k2 Ñ 0; for any given θ, this is strictly outside the ball. Hence there exists a θ, k combination for which y pδ q is outside the ball. xi 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.18 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. Rn be finite, and let X copC q be full-dimensional and contain in its interior the ball B po, 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 B po, 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 Proposition 3. Let C 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 18 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. 16 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. Also note that it is possible to provide a NLP that would enable us to compute θ̄ in the proposition. 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 new, ellipsoidal self-accessible ¥ δ, proposes a set.19 Rn be finite, and let X copC q be full-dimensional and contain in its interior the ball B po, rq with r ¡ 0. Assume that B po, 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 E po, r, δ, δ q B po, rq given by center o and semi-axes lengths 11δδ r such that E po, r, δ, δ q is self-accessible relative to C for δ. The proposition implies that for any v P E po, r, δ, δ q, there is a sequence of pure actions that realizes v when the discount factor vector δ is used; we let taptq pv, E po, r, δ, δ qqu8 t0 Proposition 4. Let C i denote that sequence. 5.3 Supporting Points in intpF q We now present a constructive folk theorem with asymmetric discounting and without PRDs for points in intpF q. 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 (as long as we are interested in 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 δ discount factor vector δ ¥ δι is used. ¥ δ. Then, v is also an SPNE payoff when the 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 self-accessibiliy. Fact 1. Let F be full-dimensional and let u and r Then there exists a uniform δ ¡ 0 such that if δ 19 ¡ 0 be such that B pu, rq P intpF q. is such that δi ¥ δ for each i, every We owe a special debt to Costas Cavounidis for pointing us in the direction of this result and suggesting how it can improve a previous version of Theorem 2. 17 P B pu, rq is a 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 B pu, rq is an SPNE payoff. v 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, i.e. outcomes that respect incentivecompatibility restrictions. However, if contracts are actually enforceable, identifying the set of realizable payoffs becomes important, especially if it is a bigger set than the set of equilibrium payoffs. But typically, that is indeed the case when discounting is asymmetric, even in the limit as all discount factors tend to one, without being necessarily equal. We now present a result that shows that if we are allowed to choose the players’ discount rate ratios, then, provided these players are patient enough, in the repeated game they can simultaneously get in a realizable payoff virtually anything they can individually get in the stage game feasible set. Theorem 3. Let F be full-dimensional. Then ¤ δ Pp0,1qn F pδ q intprepF qq P intprepF qq we can compute positive numbers k1 , . . . , kn (not necessarily unique) and a θ̄ such that if δi 1 1k θ with θ θ̄, then, v P F pδ q. Furthermore, for any given payoff vector u P intpF q, and any ν ¡ 0, one can More precisely, given any payoff vector v i ensure that along the path that realizes v, after a finite sequence of actions, all continuation payoff vectors lie in a ν-neighborhood of u. To obtain some intuition behind this result, suppose, n 2 and we are examining the realizability of v P intprepF qq. If for some k, and low enough θ, after playing a certain sequence of vertices initially, the next continuation payoff (needed to realize v) enters a small fixed ball B pu, rq inside intpF q, then we are done thanks to Proposition 3, because that proposition shows that any payoff in that ball is realizable for any k and low enough θ. What kind of vertices should the players play? Of course, vertices that nudge the 2, there is a vertex cp1q that nudges Player 1’s p 1q payoff in the right direction (c1 being on the opposite side of v1 from u1 ) and there is another vertex cp2q which does the same for Player 2. A potential pitfall is that while we continuation payoff from v to u. For n are nudging one player’s payoff in the ‘right’ direction, the other player’s payoff could be moving in the ‘wrong’ direction. One can show that by playing cp1q for T1 periods and cp2q for T2 periods where T1 and T2 are suitably chosen functions of θ and by choosing k, we can indeed achieve our goal (for θ small). This involves solving a nonlinear simultaneous equation system involving the limiting trajectory (as θ tends to 0). Once this is done, the n-player version of the problem can be recursively tackled. 18 For n 2 (but not for n ¥ 3 !), Theorem 3 can be sharpened as follows. Theorem 4. For two-player games, if F is full-dimensional, ¤ δ 7 Pp0,1q F pδ q intprepF qq ¤ F. 2 Going Beyond the FSIR Set: Supportability The n 1 phase path described in the proof of Theorem 3 unfortunately does not guarantee that the continuation payoff for each player at each period 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 4, that means player 4’s discount factor is the second-lowest. The inverse function maps names to the ranks; thus if π 1 pj q ¤ π 1 piq, we understand that a 5-player game, if π2 player i is at least as patient as player j. This interpretetion will be useful to keep in mind for the two definitions to follow; the proofs of Theorem 5 and 6 will later validate this interpretetion. 7.1 The Diagonal Conditions In the definitions below C is any set of points in Rn , F copC q and w is some point in repC q. Of course, these objects have their standard interpretations in the context of a game: pure action payoffs, feasible set and minmax point. P repC q 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 Definition A payoff vector v uiπi vπ i and ¥ wj if π1pj q ¤ π1piq. Definition A payoff vector v P intprepC qq 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 uij property uiπi and uij ¡ wj vπ i if π 1 pj q ¤ π 1 piq. 19 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π qpS pπ qq. Note that full dimensionality of F is needed for S pπ 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 π, clpS pπ qq W pπ q and assuming full-dimensionality of F , intpW pπ qq S pπ 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. 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 Specifically, for example, the point v 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 vipπq, v̄ipπqs @i 1, . . . , n, where for any given permutation π, v pπ q and v̄ pπ q are defined as follows: v i pπ q : mintvi : v P F such that v̄i pπ q : maxtvi : v P F such that ¥ wj @j vj ¥ wj @j vj such that π 1 pj q ¤ π 1 piqu. such that π 1 pj q ¤ π 1 piqu. Example (The “stand-out” game): We present a three-player game that illustrates Fact 2’s usefulness. In this “stand-out game”, each of three players can play 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 η where η is some positive number. Thus, C 1 2η is to uniquely ‘stand out’ (by doing the right thing) whereupon the other players 2η, η q, pη, η, 1 tp0, 0, 0q, p1 2η, η, η q, pη, 1 2η qu. In this game the only way to obtain the superior payoff of 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. 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 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 20 that we stay in F , we can give him at most 1 v̄ pπ q p1 2η, 1 η, 1q and W pπ q r0, 1 2η. Hence, for the natural permutation π, 2η s r0, 1 η s r0, 1s. We end our discussion of the diagonalizability conditions by noting that a vector’s diagonalizability (weak or strict) is ‘inherited’ by its subvectors in a sense made precise by the Fact below, stated without proof. It will be used in the proof of Theorem 6. Fact 3. If v satisfies weak or strict diagonalizability under the natural order with respect to C (given the n-dimensional null vector as w), then v n satisfies the same with respect to P rojn pC q (using the n 1 dimensional null vector as w). 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, ¤ P W pπ q π P ¤ δ Pp0,1qn V pδ q 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 payoff? It turns out that the u’s needed for the WD property fall right out of these freshly evaluated payoff vectors. Going back to the Stand-out game, Theorem 5 tells us that 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 Thus, for example, if η η and 1 2η, can never be an equilibrium payoff. .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. However, this payoff vector is realizable by virtue of Theorem 3. The proof of Theorem 5 also rules out arbitrary associations of equilibrium payoffs with relative ordering of patience among the players; for example, 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 given by the natural order. 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. This is easy to see - just consider the two player game with the given payoff matrix: 21 L R U ( 1, 0) (0, 0) D (0, 0) ( 0, 1) The payoff vector p1, 1q belongs to W pπ q for each π, but it is not even realizable let alone be supportable for any discount factor vector. Strict diagonalizability, however, ‘works’. 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, ¤ P π P S pπ q ¤ δ Pp0,1q V pδ q n P S pπq for some π, it is possible to determine k ¡¡ 0 (not necessarily uniquely), and θ̄ ¡ 0 such that if θ P p0, θ̄q and δi 1 1k θ for each i, it is possible More specifically, if v i to specify a SPNE strategy profile that supports v for those discount factors. The proof of Theorem 6 uses several complex ideas; hence, for the reader’s benefit, we now provide the intuition behind our methods in some detail. We will borrow a technique from the proof of Theorem 3: Devise discount factor parameters and an action sequence so as to create a path for the continuation payoffs that will start with the target payoff and will end inside a suitable set (hereafter we will call this the pre-entry path). In the case of Theorem 3 the set we wished to enter was intpF q, while in this case it would be intpF q. Once we are able to enter intpF q, Fact 1 takes over. 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 play. Where strict diagonalizability helps is with the first task. To see this for the two-player case, suppose our target payoff v is in S pπ q where π is the natural order. Then, strict diagonalizability of v guarantees us the existence of a vector u2 in intpF q where u22 Also, there must exist a vertex c such that sgnp vertex is played the continuation payoff of Player T times where T is q p v 1 q. v1 c1 sgn u21 1 shifts towards u21 . v2 . Each time this If we play this vertex q, by choosing a suitable b ¡ 0 and θ small, limiting arguments used b r s θ in the proof of Theorem 3, show us that it is possible to take the first coordinate of the continuation payoff arbitraily 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 intpF q. For three or more players, unfortunately, extending this idea runs into difficulties. Suppose n 3 and v P S pπ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: while keeping Player 3 extremely patient throughout, first we ‘fix’ Player 1’s 22 payoff by moving it to u31 (via the play of some suitable vertex). We keep Player 2 patient relative to Player 1, so that his payoff does not fall below his minmax during this first phase. Next, we fix Player 2’s payoff to u32 by playing another suitable vertex and try and enter intpF q. The problem with this strategy is that when we are trying to fix Player 2’s payoff, Player 1 can find his payoff getting ‘unfixed’! We could try and fix both players’ 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 for these players even though v1 ¡ 0, v2 ¡ 0, u31 ¡ 0 and u32 ¡ 0. We, therefore, need a new tool: how to move one strictly individually rational payoff vector to another’s neighborhood without violating (strict) individual rationality along the path. This can indeed be done as long as the two payoff vectors are both inside intpF q. Our next proposition, called The Capsule Lemma shows exactly how it can be done and also provides an upper bound on the number of periods needed to do it. Its proof offers the remarkable insight that the notion of self-accessibility 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! In m-dimensional Euclidean space, let ry, z s represent the line segment joining the points y and z and let C py, z, rq denote the set of points that are at most distance r from ry, zs, i.e. ¤ C py, z, rq o P ry,zs B po, rq 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 of copDq X Rm ¡ 0 be such that the capsule C py, z, rq is in the interior , which is assumed to be m-dimensional. Then, P B py, rq and any vector k ¡¡ 0, there exists θ:pkq ¡ 0 such that for any θ P p0, θ: pkqq we can find a finite sequence of points tct uTt01 in D and a finite sequence of points txt uTt0 in C py, 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 B pz, rq. b) Furthermore, there exists a θ; pkq ¤ θ: pkq, a strictly positive numbers m1 and a strictly negative number m2 (both Qdependent on k) such that when θ P p0, θ; q, the T given in part U ? ||yz|| a) is less than or equal to . r m θ m θ r a) For any u 1 2 2 2 Theorem 6’s proof uses a combination of strict diagonalizability, Capsule Lemma and Fact 3 to design a (continuation payoff) path that starts at the target payoff v and ends inside intpF q. We cannot effect this transition with one application of the Capsule Lemma because for that to work, the entire pre-entry path needs to be inside intpF q which of course we may not assume. However, we can use the Capsule lemma to first 23 change only Player 1’s payoff, then Player 1 and 2’s payoffs, then Player 1, 2 and 3’ s payoffs etc., each time operating inside the interior of F of the relevant subset of players. The strict diagonalizability condition provides us the ‘anchors’ which serve as landmarks for the pre-entry path around which our capsules are fashioned. It is then shown that with appropriate choice of the ki ’s and θ small, we can indeed enter intpF q while keeping each continuation payoff vector strictly individual rational all along the pre-entry path. The equilibrium strategy now can be qualitatively described. Play starts and continues on the pre-entry action 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 action path where the deviation took place. 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 a) an ‘adjustment’ term to make any punishing player indifferent among his minmaxing pure strategies, and b) a ‘reward’ to them for participating in the punishment. During preentry, 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 punisher)” strategy ensure incentive compatibility for patient players? With rising patience, bad outcomes for a finite number of periods still wipes 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 later. Now it is true that as they become more patient, the time taken to to get one’s reward also grows infinitely large, but the Capsule Lemma ensures that these times don’t grow too fast, and in fact, the PDV of the reward tends to a limit. With finite punishment periods, this ensures that patient players do not balk from punishing a deviant player. 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. 24 Appendix: 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 problem20 : 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. (8.1) For any c, given that the left hand side of (8.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 (8.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 l1 λl cl where λl ’s are strictly positive weights summing to 1. Multiplying each inequality in (8.2) by λl 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 have ° K l 1 2 l 2 λ r r2 and since these two are equal, the claim follows. But now, if for each l, c . x r , 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 (8.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.21 Clearly, δ is continuous, being the minimum of continuous functions and lies in p0, 1q. Finally, define δ : maxtδ pxq : x P S u. 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 . l 20 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). 21 To achieve well-definition, in case of ties, use any arbitrary preference ordering among the vertices. 25 Computability of δ: Having described the problem of determining δ po, rq as the nested problem Max Min δ px, c, o, rq x P BX po, rq c P C 1 we note 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 (8.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 pδl q2 tpcl oq.pcl oq r2 u 2δl pcl oq.px cl q kx cl k2 0 @ l 1, . . . , K pδl qtpcl oq.pcl oq r2 u pcl oq.px cl q ¤ 0 @ l 1, . . . , K p3q px oq.px oq ¤ r2 p4q °K x l1 λl cl p5q °K l p6q l1 λ 1 λl ¥ 0 @ l 1, . . . , K p7q. δ p2q 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 minimization is also over x and constraints (4) - (7) ensure that each feasible x belongs to the affine ball BX po, rq.22 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 22 Note that if the ball was full-dimensional, we could have dropped constraints (5) - (7). 26 uniform bound follows. Now we can state the required NLP. Max δ subject to ¤ δl @ i 1, . . . , K p1q pδl q2 tpcl x1 qpcl x1 q ω2 u 2δl pcl x1 qpx2 cl q kx2 cl k2 0 @ l 1, . . . K pδl qtpcl x1 qpcl x1 q ω2 u pcl x1 qpx2 cl q ¤ 0 @ l 1, . . . , K p3q px x1 q.px x1 q ¤ r̄2 p4q px1 x2 q.px1 x2 q ¤ ω2 p5q °K x1 l1 λl cl p6q °K x 2 l 1 θ l c l p7q °K l p8q l1 λ 1 °K l p9q l1 θ 1 λl , θl ¥ 0 @ l 1, . . . , K p10q δ p2q 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 1 Max 2 Max . x P BX px, r̄q x P BX px1 , ω q c P C 1 Proof of Theorem 1 Because F is full-dimensional and v P F zB F , there exists v 1 such that it is in intpF q and v1 v. First, we define two constants ∆ and N that we need to define the equilibrium strategy.23 We choose ∆ ¡ 0 such that ? B pv 1 , 4 n 1∆q intpF q. (8.3) Further, if v is not a payoff vector associated with a pure strategy profile, and can be expressed °K as l1 λl cl where each λl ¡ 0, ∆ should be small enough so that BX pv, ∆q where X relintpX q (8.4) cotc1 , . . . , cK u. Note that from (8.3), it follows that vi1 ¡ ∆. Now define N P N by N S W max i 23 M vi1 ∆ , (8.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. 27 implying that N 1 ¡ M {pvi1 ∆q for all i. Let δ 1 be such that for δ δN ¥ NN 1 ¥ δ1 , . (8.6) The last two inequalities guarantee the following inequality which will be critical later: δ 1 δN ... ¥ v1 M ∆ @i . (8.7) i ¥ δ2 , Next, given N , there is a δ 2 , such that for δ δN Note that this implies, for δ ¥ M M ∆ @i. (8.8) ¥ δ2 , δN 1 1 @i. ¥ v1 vi ∆ ¥ vvi1 ∆ ∆ i (8.9) i If v is a payoff vector for a pure action profile, let δ 3 0. Otherwise, BX pv, ∆q referred to in (8.4) is self-accessible for all δ larger than some bound; let δ 3 be that bound computable via Proposition 2. Lastly define v 1 piq : pv11 2∆, . . . , vi11 2∆, vi1 , vi1 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 (8.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 (8.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 t0 . 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 ã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 , B pv piq z i , ∆q, δ qu8 t0 , where z is an adjustment vector defined by the following two equations zji $ & p1δN q r i % δN j 0 if j i otherwise. 28 (8.11) rji N ¸ pp11δδNqq δt1 gi pãptq q, (8.12) t 1 If there is any unilateral deviation from Phase III(i) by player j, start Phase II(j). δ i i Inequality (8.8) implies 1 ?δN M ¤ ∆ and since,1 |rj | ¤ M , |zj | ¤ ∆ for j i. This implies 1 i that v piq z is at most n 1 ∆ away from v piq. Hence, given the construction of δ 4i earlier, 1 B pv 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. N • For unimprovability from Phase I, it suffices to have p1 δqM δN 1 pvi1 ∆q ¤ vi ∆, (8.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. (8.14) • For unimprovability from Phase III(i), it suffices to have p1 δqM δN 1 pvi1 ∆q ¤ vi1 ∆. (8.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 tãptq uN t1 denote the sequence of actions that are realized in Phase II(j), with τ periods left in that phase, if player i knew the last τ entries of that sequence, the following inequality would deter deviation: p1 δ qM δN 1 pvi1 ∆q ¤ p1δqrgi pãpN τ 1q q . . . δ τ 1 gi pãpN q qs δ τ pvi1 2∆zij q. (8.16) Using (8.11) and (8.12), the right hand side of (8.16) becomes: δ τ pvi1 2∆q 1δ gi pãp1q q δ N τ which is bounded from below by δiτ vi1 is satisfied for any sequence of a’s if p1 δqM δiN 2∆ 1 ... δ N τ 1 gi pãpN τ q q , (8.17) M . Hence by (8.8), inequality (8.16) 1 δN δN pvi1 ∆q ¤ δN vi1 ∆ . (8.18) • Lastly, for unimprovability from Phase IIIj it suffices to have: p1 δqM δN 1 pvi1 ∆q ¤ vi1 2∆ zij ∆ (8.19) for all possible values of zij . Because |zij | ¤ ∆, this is satisfied if the following holds: p1 δqM 29 δN 1 vi1 ¤ vi1 . (8.20) Examination of these conditions shows that while (8.14) is trivially true, (8.15) directly implies (8.13) and (8.20). Because of (8.9), it also implies (8.18). Thus to ensure all incentive compatibility conditions one only needs to satisfy equation (8.15), which is (8.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 B po, rq, and c P C 1 define a vector y px, c, o, r, k, θq where yi px, c, o, r, k, θq : θki pxi ci q xi for i 1, . . . , n. (8.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 : ||y px, 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θ n ¸ ki pxi ci qpxi oi q i 1 i 1 n ¸ p pxi oi q2 r2 q (8.22) i 1 Because of the full-dimensionality assumption, f ¤ 0 ùñ y px, c, o, r, k, θq P B po, 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 B po, rq, there exists a c such that f ¤ 0. The expression in (8.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 BBfθ 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 i1 ki pxi ci qpxi oi q 0, or n ¸ n ¸ ki pxi oi qxi i 1 i 1 ki pxi oi qci (8.23) °n Consider the hyperplane H ty : py αu, where pi ki pxi oi q and α i1 ki pxi oi qxi (since x o, p is a non-zero vector). If inequality (8.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 B po, rq, if θ P p0, θ px, o, r, kqs, f ¤ 0. Finally, define the required bound 30 as θ̄po, r, kq : min P p q x B o,r θ px, o, r, kq. (8.24) Since B po, 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 requirement of the bound. Proof of Proposition 4 Define ri : 11δδi r for each i. With these being the lengths of the semi-axes of the desired °n oi q2 ellipsoid, the latter can be written as: E po, r, δ, δ q tx : i1 pxi ¤ 1u. It is easy to see that ri2 E po, r, δ, δ q is contained in B po, rq and can be written as f pB po, rqq where f is a 1-1 correspondence from B po, rq to E po, r, δ, δ q given by fi pxq oi pxi oi q 11 δδi @i. Now let x P E po, r, δ, δ q; to prove the proposition, we need to show that there exists c that y P E po, r, δ, δ q where 1 1 δi yi xi ci @i. δi δi To see this, let x f px1 q where x1 (8.25) P C such (8.26) P B po, rq. By equation (8.25), p1 δqxi p1 δi qx1i pδi δqoi @i. (8.27) and because of the self-accessibility of B po, rq for δι, there exists c such that n ¸ 1 2 r i 1 1 1 xi p1 δ qci oi δ 2 ¤1 (8.28) Using this particular c in the edfintion of y in (8.26), y i oi ri " * 1 1δ 1 rxi p1 δi qci s oi r 1 δi δi " * 1 1 1δ 1δ xi p1 δ qci oi r δi 1 δi 1 δi " * 1 1 δi δ 1δ 1 x oi p1 δ qci oi r δi i 1 δi 1 δi " * 1 1 1 δ xi p1 δ qci oi r δi δi " * 1 δ 1 1 x p1 δ qci oi r δi δ i (8.29) (8.30) (8.31) (8.32) (8.33) where we have used (8.27) to go from (8.30) to (8.31). Now, equation (8.28) and the fact that δi ¥ δ for each i, allow us to conclude that °ni1 31 yi oi ri 2 ¤ 1 and we are done.