Repeated Games Without Public Randomization - A Constructive Approach

Repeated Games Without Public Randomization: A Constructive Approach Abstract We study infinitely r epeated g ames w ith p erfect m onitoring a nd w ithout public randomization devices. 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. In the case of symmetric discounting, our approach delivers a constructive version of the folk theorem of Fudenberg and Maskin (1991). If discounting is asymmetric, we show that any payoff that is in the interior of the smallest rectangular region that contains the stage game feasible set is realizable in the repeated game for identifiable sets of discount factor v ectors. Next, we provide necessary and sufficient conditions for payoff vectors to be subgame-perfect equilibrium payoffs for some discount factor vector. Sets that are defined by these conditions are easily described; moreover, discount factor vectors and strategies that support a specific payoff vector can be explicitly constructed. In the words of Kronecker, the positive integers were created by God. ...When a man proves a positive integer to exist, he should show how to find it. If God has mathematics of his own that needs to be done, let him do it himself. - Errett Bishop1 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 is supportable as the discounted average of payoffs arising from an SPNE (subgame perfect Nash equilibrium) of the corresponding repeated game. This result is often construed as the foundation of the argument behind the assertion that rational, self-interested agents can be induced to cooperate with one another as long as the future is reasonably important to them. To accord legitimacy to this argument, however, it is vital to ensure that it does not depend on fragile assumptions. Two such 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 second is the assumption that all players have exactly the same discount factor. While the arguments in the original FM 1986 paper were ‘constructive’, existing papers that have attempted to weaken one or both of these assumptions either are unable to provide explicit equilibrium strategies, or can not compute numerical bounds on discount factors for folk-theorem type results, or (in the case of asymmetric discounting) require very specific patterns of discount factor vectors, or are unable to describe in simple terms, the possible equilibrium payoff sets. Using a new geometric concept called self-accessibility, we are able to unify the study of ‘PRD-less’ games with both symmetric and asymmetric discounting. We strengthen results in the former case and offer new results in the latter case, while maintaining a constructive approach throughout. 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?2 Lehrer and Pauzner (1999), hereafter LP 1999, have argued that even when payoffs are monetary and players can borrow in an outside market to smooth their consumption streams, different agents, because of their 1 From “A Constructivist Manifesto”, quoted in Errett Bishop and Douglas Bridges, “Constructive Analysis”, Springer, 1985, Chapter 1, Page 4. 2 See for example Harrington (1989), Obara and Zincenko (2017) and Haag and Lagunoff (2007) who provide interesting economic models with differential discounting, the first two in the context of pricesetting oligopolies, and the last in the context of collective effort-expending games. 1 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,3 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 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; the sequence of pure actions given by Sorin’s lemma may not be an equilbrium path. 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).4 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 3 A set is totally disconnected if the only connected subsets it has are either empty or singleton. 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 2 constructive argument of the FM 1991 folk theorem.5 Why might knowing a 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. In fact, if the bound works out to be .2, one has described what can be achieved for fairly myopic players as well. 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.6 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 proof crucially relies on existence of PRDs. They conjecture that it might be possible to remove this last restriction using techniques similar to 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. Under unequal discounting, Chen and Takahashi (2012) show that a sequence of action profiles that delivers a given payoff can be supported in equilibrium if all its continuation payoffs are uniformly bounded away from the minmax values. However, without a PRD only an ‘approximate’ folk theorem is proved. The question of realizability is not tackled either.7 Repeated games with imperfect public monitoring are 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). Using this approach, Sugaya (2015) extends LP 1999 to prove a very 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, like Lehrer and Pauzner works with restrictive discount factor vector sequences, specifically assuming that pairwise ratios of discount rates 9 are either constants or are converging to constants. His main result shows that the limiting sets of payoff vectors that are individually rational each period and that of equilibrium payoffs are identical. Although results based on self-generation apply to perfect monitoring, the following points about that approach are worth noting and will be contrasted with our approach. 5 Although the strategies we use are very similar to the ones used in FM 1991, one of our innovation is to design a punishment phase that does not increase without bound as players become arbitrarily patient. 6 A recent paper, Hörner and Takahashi (2016) addresses this question systematically for the first time. 7 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. 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 δ1i
1. 3 • Self-generation proofs do not offer a clear-cut way of calculating a bound that discount factors must obey for supporting a target payoff vector. • The actual computation of actions to be played requires solving an infinite sequence of nonlinear programs for the asymmetric discounting case, a computationally onerous task. • Self-generation considers realizability and supportability together. The issue of realizability which is interesting in its own right is not addressed separately. • When the number of players is three and higher, this approach does not yield a simple condition for verifying if a given point is an equilibrium point for some discount factor vector. As it turns out, we can use the notion of self-accessibility to fill many of these voids. To support points inside the interior of the FSIR set, we can find a common bound for each player’s discount factor - the same one we can compute with symmetric discounting! We show that for games with full-dimensional feasible sets, if one is allowed to choose discount rates, for large enough (computable) discount factors, one can make any payoff vector realizable as long as its i-th coordinate is strictly between the maximum and the minimum of player i’s stage game payoffs. Next, we offer necessary and sufficient conditions for payoffs to belong to the limiting equilibrium payoff set10 . These conditions, respectively referred to as the weak and strict diagonal conditions, characterize sets that are quite easy to compute and visualize. We show that with a symmetric stage game, if we wish to give a player (close to) the maximum possible payoff (of the stage game), we have to make him the least patient among all players. We offer specific strategies and sets of discount factors that realize or support a given payoff vector satisfying the sufficiency conditions of realizability and supportability respectively. As such, we go well beyond proving folk theorems: our constructive approach empower game theorists with prescriptive powers above and beyond explicative ones.11 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 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 the weak and strict diagonal conditions and shows how they relate to supportability of payoff vectors outside the FSIR set. Section 8 concludes. All proofs are collected in an appendix. 10 By this we mean the set of payoffs which are SPNE payoffs for some discount factor vector. In fairness, we readily admit that for the n-player case we do not solve the problem of characterizing the set of supportable payoffs for a specific discount factor vector (or even the corresponding limiting set for fixed discount rate ratios). However, we do throw some light on it since, our necessary condition tells us what cannot be part of that set. 11 4 2 Preliminaries 2.1 Notation and The Model We consider a standard infinitely repeated game of perfect monitoring with possibly un- P t0, 1, 2, . . .u the (finite) stage-game G  hI; pAiqi; pgiqii is played, where I is the set of players t1, . . . , nu, Ai is player i’s finite set of actions, ‘ A : j Ai is the set of all pure action profiles, and gi : A Ñ R is player i’s 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 equal discounting. At each t at time t.12 When player i discounts future payoffs using the discount factor δi , player i’s average discounted utility defined over infinite sequences of pure actions in A is ui p ! 8̧
)8 p tq q : p1
δi q δi t gi aptq . a t0 t0  pap0q, . . . , aptqq P 1 . A pure strategy of i is a (sequence of) maps s pt 1q : H t Ñ A pfor t 
1, 0, 1, . . .) i i Under perfect monitoring the public history at the end of period t is ht At 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. This describes the repeated game G8 pδ q, where the vector δ  pδ1, . . . , δnq is referred to as the discount factor vector. In the special case where each player discounts the future at the same rate δ, we denote the game (by a slight abuse of notation) as G8 pδ q. We let F pδ q denote the set of feasible payoff vectors and V pδ q to denote the set of subgame perfect equilibrium payoff vectors in the repeated game. ‘gpAq. Player i’s minmax value is wi : minα
P‘  p∆A q maxa PA gipai, α
iq, P nj1p∆Aj q be the profile that minmaxes i, with player i playing a best re- Let C Let mi i j i j i i sponse. 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 : copC q, the feasible and weakly indi- vidually rational (FWIR) set is F : tx P F | xi ¥ wiu and the feasible strictly indiP F | xi ¡ wiu. The lower boundary of F is xu. We let M  maxi t|gi paq| : a P Au; when F  vidually rational (FSIR) set is F  : tx BF : tx P F : Ey P F such that y is full-dimensional, this is strictly positive. For any set S € Rn, and M € t1, . . . , nu, P rojM pS q denotes the projection of S along 12 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  t1, 2, . . . , n
1u, we use the shorthand P roj
n pS q to denote the projection on the first n
1 coordinates. For a finite set C of pure the coordinates in M . In particular when M action payoffs in an n-player game, we define the corresponding ‘feasible set’ for Players 1, . . . , l (l ¤ n) as F p1, . . . , lq : copP rojt1,...,lu pC qq  P rojt1,...,lu F . ι is a vector of 1’s while ei is the i’th unit vector. For later use, we recall the definitions of a few geometric terms. The affine hull of a set X aff pX q : # ķ  l 1    λl xl  xl  P X, € Rn is ķ  λl  1, k P N + . l 1 ¥ 0 above, we obtain the convex hull of X, denoted as copX q. For x P X, the affine (closed) ball with center x and radius r is BX px, rq : ty P aff pX q : d py, xq ¤ ru, while B px, rq denotes the usual (closed) ball in Rn . The relative interior of X is If λl relintpX q : tx : D r ¡ 0 such that BX px, rq € X u.  copC q, where C  tc1, . . . , cLu, and every point in C is an extreme point of X, then each point in relintpX q can be expressed as of those) points !°a convex combination °L  l L l l l with strictly positive weights, i.e. relintpX q  l1 λ c  λ ¡ 0, l1 λ  1 . The usual interior of a set S is denoted by intpS q. Finally, we introduce a new terminology: the rectangular hull of a bounded set in Rn , denoted as repS q is the smallest closed rectangle When X that contains S. Formally, repS q : £ P R R R 2.2 where R  # n ¹  n ¹ rai, bis : ai ¤ bi, rai, bis  S i 1 +  . i 1 Self-accessibility We now define self-accessibility, for possibly unequal discounting and explain its usefulness. Although self-accessibility is an independent geometric notion, in the definition below the set C may be usefully thought of as the set of payoff vectors from pure action profiles of the stage game and δj may be thought of as the discount factor of player j. € Rn be a finite set. A set S € copC q 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.13 The definition is particularly intuitive for equal discounting. For some x P S € copC q, suppose that we can find c P C, y P S and δ P r0, 1q such that x  p1
δ q c δy; this is Definition. Let C 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 13 When there is no scope for confusion about C, we omit it. Note that if S is self-accessible relative to C for δ, then it is self-acessible relative to any superset of C for the same δ. 6 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 δ  δι. Why is self-accessibility useful for dispensing with PRDs? Suppose C is the set of € copC q is self-accessible for δ, and x P S. It  p1
δj qcjp0q δj yj1 for each j where y1 is p1q δ y2 for each j for some also in S. Because of the latter, we can write yj1  p1
δj qcj j j 1 2 p c P C and y P S. By induction there is a sequence of vertices tc tq ut¥0 such that pure-action payoffs in the stage game, S follows that there exists cp0q P C such that xj xj τ̧  p1
δj q  ptq δjt cj δjτ 1 τ 1 yj @j, @τ. t 0 Since δj 1 and S is bounded, we have k δjτ 1 τ 1 yj in a self-accessible set S has a representation xj kÑ 0 as τ  p1
δ j q ° Ñ 8. Hence any point x p q . Restating this in t t t 0 δj cj ¥ the context of repeated games, 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.14 3 A Numerical Example Next, we presents a numerical example to underscore the computational advantages of using self-accessibility in supporting specific payoff vectors in the symmetric discounting case. Although the results presented later are more general, and are valid for any number of players, in order to abstract away from ancillary issues, we choose a simple, asymmetric version of the Prisoner’s dilemma game. 3.1 Achieving 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 and c4 respectively. The unique dominant strategy equilibrium pA, Aq 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 14 To make this sequence well-defined, whenever a point in S can be decomposed in more than two ways with more than one choice of current action, we can use some pre-assigned arbitrary ordering among the vertices to decide which current action to choose. 7 like to obtain this payoff vector in a SPNE. 7 c4 6 c3 l 5 4 n 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 l  Let us first examine the realizability of n. Choose a one-dimensional closed ball S copt uq containing n, with extreme points l and r (l being closer to λp5, 5q p1
λqp9, 0q  p9
4λ, 5λq and r  µp5, 5q p1
µqp9, 0q  p9
4µ, 5µq with the c2 , c3 c3 ). 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 δp 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, c3q  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 x, c3 of the vertices c2 or c3 with the continuation payoff lying in S.15 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, i.e. p1
θq{p1
µq  θ{λ. Eliminating θ and then substituting in either expression gives 15 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 a needed bound for S to be self-accessible: δ : max δ  pxq  max mintδ px, c2 q, δ px, c3 qu  P P x S x S 1 1
µ λ . (3.2) ¥ δ and (3.1) holds, n can be realized by playing a sequence of actions from the set tpA, N q, pN, N qu. In particular, when δ Next, to support n in equilibrium, we wish to deter deviation from the prescribed path via a grim trigger mecahnism `a la Friedman (1971): pA, Aq is played forever as soon as any deviation is detected. This is achieved by two incentive compatibility constraints that ensure receiving the worst payoff in S for one period is at least as good as receiving the best payoff in the game once and being minmaxed forever afterwards: 9
4λ ¥ 9p1
δ q 5µ ¥ 7p1
δ q 4δ, (3.3) 2δ. (3.4) The minimum δ satisfying (3.1), (3.2), (3.3) and (3.4) is .761, and the corresponding ball S is given by λ  .952, µ  .639. This suggests that above a reasonable discount factor the Nash bargaining payoff n can be implemented in an SPNE where one player never plays his dominant action and the the other some times plays hers. 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? We preview some of the results to follow by explaining how they apply in the context of the current example. 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 9 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 the figure; 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. 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 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 t0 in C °8 t ptq 16 such that x  p1
δ q t0 δ c . Armed with this result, FM then tackle the problem of realizability. The lemma states the following: Suppose x 16 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. 10 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 self-accessible 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 that set are self-accessible (relative to its extreme points and for large enough discount factors). When a target payoff is in F  , by placing it at the center of a ‘small’ ball, we can thus achieve both realizability and (period-wise) 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 1q need not be full-dimensional. Let S  BX po, rq € relintpX q 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 a closed ball S  BX po, rq in the relint 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 that is on the same side of x where c is and one on the other side (they could be same). Call this latter point y (y could be x itself). We can think of x as a p1
δ q : δ convex combination of c and y. It is this δ that is δ px, cq. It is not hard to find a formula for this function, and as expected, it is continuous in x. Now we assert that δ px, cq 1 for some vertex c. If x is in relintpS q, any vertex c P C 1 works but if x is on its (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, c3u 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, δ px, c1 q  1, δ px, c2 q 

kx c2 k ky 2 c2 k and δ px, c3 q 

kx c3 k . ky 3 c3 k Let δ  pxq : mincPC δ px, cq. For our figure, it turns out that δ  pxq  δpx, c3q. 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 δ. Lastly, one can show that the two-stage nested optimization problem we just described can be written as one large optimization problem which is the NLP referred to in Proposition 1. 11 c1 y3 x y1 y2 c2 c3 Figure 3: How δ  pxq is constructed. 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 taptqpx, BX po, rq, δqu8t0 denote this sequence. One of the biggest advantage of the self-accessibility approach over the FM 1991 approach is that we are very easily able to provide a computable uniform bound on discount factors that guarantee 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 such as every open cover of a compact set has some finite subcover are not required. As is well-known, these uniform bounds may become relevant if unbeservable mixed strategies are needed to minmax a player, because post-punishment plays are not known beforehand; they are calculated based on the realizations of mixed actions during the punishment period. Extending ideas that are used to prove Proposition 1, our next result shows that we can easily 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.  °Kl1 λl cl with λl ¡ 0 for each l. Let C 1  tc1, . . . , cK u and X  copC 1 q. Let r̄ ¡ 0 and ω ¡ 0 be such that BX px, r̄ ω q € F  X relintpX q. Then, we can find δ 1 such that for any δ P pδ, 1q, any B px1 , ω q where x1 P BX px, r̄q is selfaccessible relative to C 1 for δ  δι. Furthermore, δ is computable by solving a nonlinear Proposition 2. Let x maximization problem. 12