UNIVERSITY OF ILLINOIS LIBRARY AT URBANA-CHAMPAIGN BOOKSTACKS Digitized by the Internet Archive in 2011 with funding from University of Illinois Urbana-Champaign http://www.archive.org/details/goodbaduglycoali91158kahn Faculty Working Paper 91-0158 330 B385 1991:153 COPY 2 The Good, The Bad and The Ugly: Coalition Proof Equilibrium In Infinite Games Charles Kahn Department of Economics University of Illinois Dilip Mookherjee SUU is til nl Institute Seu Delhi Bureau of Economic and Business Research College of Commerce and Business Administration University of Illinois at Urbana-Champai^n BEBR FACULTY WORKING PAPER MO. 91-0158 College of Commerce and Business Administration University of Illinois at Urbana -Champaign August 1991 The Good, The Bad and The Ugly: Coalition Proof Equilibrium In Infinite Games Charles Kahn Department of Economics University of Illinois Dilip Mookherjee Statistical Institute New Delhi Forthcoming: Games and Economic Behavior THE GOOD, THE BAD AND THE UGLY: COALITION PROOF EQUILIBRIUM IN INFINITE GAMES by Charles M. Kahn University of Illinois, Urbana- Champaign and Dilip Mookherjee Indian Statistical Institute Current Version: October 1990 *We thank Carlos Asilis, Joseph Greenberg, Bentley MacLeod, Alvin Roth, William Thomson, and an anonymous referee for useful comments, as well as participants at the summer game theory conferences at Ohio State, 1988 and 1989. This work was funded by NSF grant SES-8821723. Addresses: Kahn: Department of Economics, University of Illinois, 1206 S. Sixth Street, Champaign, IL 61820, USA. Mookherjee: Indian Statistical Institute 7 S.J.S. Sansanwal Marg, New Delhi 110016, INDIA. Running Head: THE GOOD, THE BAD, AND THE UGLY Abstract : This paper provides techniques for using stable sets to characterize equilibria in infinite games. We demonstrate the techniques by extending the definition of Coalition Proof Nash Equilibrium. Our new definition reduces to the recursive definition of Bernhein-Peleg- Whinston in games with a finite number of players and a finite strategy space. Unlike the old characterization, our new one maintains an equivalence between a recursive definition and a non- recursive characterization when strategy spaces are infinite. Examples are used to demonstrate the advantages and relative simplicity of the new definition, even for games with infinite numbers of agents . JEL Classification Number: 026 Mail correspondence to: Charles M. Kahn Department of Economics University of Illinois 1206 S. Sixth St. Champaign, IL 61820 THE GOOD, THE BAD AND THE UGLY: COALITION PROOF EQUILIBRIUM IN INFINITE GAMES I. Introduction Recently Greenberg [6,7,8] has used the von Neumann-Morgenstern [13] notion of stable sets as a framework for examining and comparing game theoretic solution concepts. The idea of a stable set applies to any abstract system of objects with an arbitrary dominance relation defined on the set. It partitions the objects into two subsets -- which can be denoted "good" and "bad" -- with the property of internal stability (no element of the good set is dominated by another) and external stability (every element of the bad set is dominated by some element of the good set) . By varying the type of objects that constitute potential candidates for a solution (such as strategy- tuples or coalitional arrangements), and the nature of the dominance relation among them, the analysis can reflect alternative assumptions about the environment in which the game is played. The approach allows systematic extension of known solution concepts to new and difficult contexts. For example, the approach is of use in defining renegotiation proof equilibria in repeated games (Asheim [1], Asilis, Kahn and Mookherjee [2]) and in extending cooperative solutions to games with private information (Boyd-Prescott [4], Myerson [12], Marimon [11], and Kahn-Mookherj ee [9,10]). A difficulty with the approach is that a stable set can only be guaranteed to exist for finite abstract systems. For example, Greenberg [7] demonstrates that the Coalition Proof Nash Equilibrium proposed by Bernheim- Peleg- Whinston [3] can be characterized by the stable set of an abstract system of coalitional agreements with a suitable dominance relation -- so long as a stable set exists. We provide examples with infinite action spaces where the stable does not exist and the equivalence breaks down. Thus the approach might seem of limited usefulness in economic contexts, where players typically have an infinite number of actions available. The aim of this paper is to suggest procedures for extending the stable set approach to games with infinite action spaces and/or infinite numbers of players. We employ two procedures. The first follows Roth's [14] generalization of the von Neumann and Morgenstern solution concept, using a tripartite division of the objects in the abstract system. This "semi-stable partition" exists for any abstract system, finite or infinite. The second procedure involves modifying the objects examined in the abstract system, by developing a notion of "near- rationality" of coalitional actions. We illustrate the two procedures by applying them to the case of Coalition Proof Nash Equilibrium (CPNE) . We show that there is a unique semi-stable partition of Greenberg's abstract system for any finite player game. From this partition, we generate a non- recursive definition of coalition-proof equilibrium (S-CPNE). For finite player games we show that this non-recursive equilibrium concept is a subset of the set of equilibria according to B-P-W's recursive definition. With infinite action spaces, the recursive definition can generate intuitively unreasonable outcomes; in these cases our non recursive concept provides a useful refinement. However, we also provide examples where recursive CPNE are unreasonable and the S-CPNE fails to exist, despite the existence of "intuitively reasonable" outcomes of the game. This problem arises when the set of self -enforcing agreements is open. We show that the set may be open even in a game with compact strategy spaces and continuous payoffs. Our second procedure handles this difficulty, by modeling "near- rationality " for coalitions. We model coalitions as choosing not single action- tuples , but convergent sequences of actions, with payoffs defined by the limit points of these sequences. The interpretation is that they choose actions "sufficiently far along" these sequences, thus gaining little by going to the limit. With this modified formulation of the set of coalitional agreements, the stable partition exists in any finite player game. From this stable partition, we derive an "extended" notion of coalition proof equilibrium (ES-CPNE), which provides the desired refinement of the B-P-W definition. We also provide an alternative, recursive definition of ES-CPNE. Since the stable sets approach does not depend on finite recursions on the set of players, it is the natural candidate for extension to the infinite player case. Although the stable set need not be unique when the number of players is infinite, the minimal stable set can be easily characterized. We therefore propose as the natural extension a "strong" coalition proof equilibrium, corresponding to Roth's "supercore" and characterized as belonging to every stable set. A natural economic application for a game with an infinite number of players is any situation with free entry. The procedures we develop here have proved particularly useful in applications to market games with imperfect information (see Kahn-Mookherj ee [10]). II. Simple Agreements Let N be the (possibly infinite) set of players, with i£N denoting a typical player. Let A , U respectively denote the strategy space and payoff i i functions of i and let A = Y „ A , and U : A -» R. A iGN i i Define an agreement to be a pair (a,S) where a 6 A and S is a non-empty subset of N. Let A denote the set of all agreements. Note that an agreement specifies actions for all players, not just those in S. The reader may find it helpful to interpret an agreement as specifying the actions for the parties to the agreement, given the actions of other players . Agreement (b,S) dominates agreement (a,T) (denoted (b,S) > (a,T) ) if (i) S C T (ii) a = b for all j £ N\S j j (iii) U (b) > U (a) for all i e S. i 1 In other words, a dominating agreement is one in which a subset of the original parties break away and find actions which are strictly better for all of the subset, the rest of the players leaving their actions unchanged. The pair (G,B) is a stable partition of the set of agreements A -- where G denotes the stable set of "good" agreements, and B denotes its complement, the set of "bad" agreements -- if (a,T) e B « There exists (b,S) 6 G such that (b,S) > (a,T) (a,T) e G <=• There does not exist (b,S) E G such that (b,S) > (a,T) In other words, every agreement in G is dominated only by agreements in B, and 2 every agreement in B is dominated by some agreement in G. It is not clear that a stable partition always exists, or if it does, whether it is unique. However, if a stable partition (G,B) does exist, it generates a solution concept in the following way: the set of solutions to the game is the set of strategy vectors a such that (a,N) is in the set G. In the case of a finite number of players and strategies, it can be shown that there always exists a unique partition; this is established below. But in finite -player , infinite - strategy games, a stable partition may not exist. Example 1 Consider a one player game N = (i), A = (0,1) and U (a ) = a . i iii If G is non-empty, it must contain a single agreement -- otherwise one agreement in G will dominate another. Let G = ((a ,(i))). Then (a +c,{i))eB, i i and therefore must be dominated by some agreement in G , a contradiction. G cannot be empty, because then every agreement would be in B , and by definition every agreement in B must be dominated by some agreement in G.B Example 1 would no longer hold if the player had a compact strategy space. But with more players, this problem may arise even with compact strategy spaces and continuous utility functions. Example 2 Suppose N = (1,2,3), A = [0,1] for all i and i U (a , a , a ) = a - I a -a I 112 3 2 ' 1 2 U (a ,a ,a ) = 2a - a - la -a I 2 12 3 1 3 ' 2 3 ' U(a,a,a)=2a -a - I a -a I ( 1-a +a ) . 3 12 3 1 2 1 3 ' 12 The best response correspondences are: a (a , a ) = a 12 3 2 a (a ,a ) = a and 2 13 3 a (a ,a ) - [0,1] if a = 1 and a = 3 12 1 2 a otherwise . l Suppose there exists a stable partition {G,B}. First note that ((a , a , a ) , ( i ) ) G G if a G a (a ), where a denotes the strategy- tuple of 123 ii-i - i players other than i -- this is because such agreements cannot be dominated, as i is playing a best response. Next, note that (a,N) G G implies a must be a Nash equilibrium -- otherwise it can be dominated by a singleton-agreement involving a best- response strategy. Hence (a,N) G G implies a - a - a . We claim that there is no (a,N) G G. Suppose ((a,a,a),N) G G and ((b,b,b),N) G G with b > a; then the latter would dominate the former, a contradiction. Suppose there is a unique a G [0,1] such that ((a,a,a),N) G G. If a < 1, then it follows that ((a+e, a+e, a+e),N) G B, which requires ( (a+e , a+e , a+e ) , N) to be dominated by some agreement in G. Clearly it cannot be dominated by any singleton coalition agreement, nor by ((a,a,a),N). So ( (a+e , a+e , a+e ) , N) must be dominated by some pair-coalition agreement. Suppose it is dominated by ( (a ,0 , a+e ) , { 1 , 2 ) ) G G. For this it is necessary that a and P both exceed a+e . But if @ > a+e , ( (a ,/3 , a+e ) , { 1 , 2 ) ) ls dominated by ( (a,a+e ,a+e ) , { 2 ) ) e G, contradicting the hypothesis that ( ( There exists (b,S) G G such that (b,S) > (a,T) (a,T) G G o (b,S) f> (a,T) only if (b,S) G B U = A \ (G u B) In other words B consists of all agreements dominated by agreements in G, and G consists of all agreements which are not dominated, except possibly by 3 agreements in B. A semi-stable partition is weaker than a stable partition in that the good and the bad sets do not exhaust the set of all agreements: there may be agreements that are neither good, nor bad. The following lemma establishes some properties of this ugly set. Lemma 1 : (a). Any (a,S) in U is dominated by some (b,T) in U. Hence U is either empty or infinite. (b) . In finite player, finite-strategy games, U is empty. Hence a semi-stable partition is a stable partition in such games. (c) . (a,S) G U cannot be dominated by any (b,T) G G. Hence with compact strategy sets and continuous utility functions, (a,N) G U implies a is a Nash equilibrium. Proof (a) (a,S) G U must be dominated by some agreement (b,T), otherwise it would be in G. If (b,T) G G then (a,S) would be in B instead. If (a.S) is not dominated by another agreement in U, then (b,T) e B. But then (a,S) e G, a contradiction. (b) Follows from (a), since A is finite in finite games. (c) is obvious. ■ Ugly sets are therefore "open" in the sense of containing infinite sequences of agreements dominating one another, but none of which are dominated by a good agreement. With compact strategy spaces and continuous utility functions, they involve members of the coalition playing best responses -- i.e., they are self -enforcing in the strict non-cooperative sense . Theorem 1 ; A semi-stable partition always exists. 4 Proof: Define: G = ((a,S) e A | there is no (b,T) in A dominating (a,S)) B = l(c,V) 6 A | (c,V) is dominated by some (a,S) e G } For any (finite or transfinite) ordinal a > 0, define B and G inductively a a given the definitions of G and B. for all < a: P P G = {(a,S) G A I there is no (b,T) in A - U B. dominating (a,S) a p 0. Then there must be a first such ordinal. Call it a and let (a,S) e B n G . Thus (a,S) is dominated by some Q Q (c,V) E G ; moreover (c,V) G B_, for some 8 < a . This means there is (b,T) G G„ a P 8 which dominates (c,V); this (b,T) must be in B for some 7 < a. Thus G„ n B 7 B 7 * 0. Let 6 be the larger of 8,-y. Then G n B * 0, contradicting the 6 assumption that a was the first such ordinal. IAI There are at most 2 distinct sets G so for some ordinal 7, G = G a 7 7+1 Let U = A - (G u B ). We establish that {G ,U ,B } is a semi-stable 7 7 7 7 7 7 partition. By the above, the sets are disjoint. An agreement is in G if and only if it is dominated only by agreements in LL .. B„ - B . An J j j b £<7+l 3 7 agreement is in B if and only if it is dominated by an agreement in G ■ The previous theorem gives an inductive procedure for generating a semi-stable partition. The next theorem establishes that in a game with a finite number of players there is no other serai-stable partition. Theorem 2 : For finite player games, the semi-stable partition is unique. Proof : See appendix. Theorems 1 and 2 give rise to the following definition: In a finite player game, a strategy vector a is a Semi - Stable Coalition Proof Equilibrium (S-CPNE) if (a.N) G G in the semi-stable partition of agreements . Corollary 1: Every strong equilibrium is an S-CPNE. Proof : In the proof of theorem 1, the strategy vectors a such that (a,N) is in G are precisely the strong equilibria. ■ It should be kept in mind that the existence of a CPNE is a separate issue from the existence of a stable or semi-stable partition. A semi-stable partition always exists, but it may be that no CPNE -- of either variety -- exists. In example 2, this is precisely the case: there is no (a,N) in the good set of the semi-stable partition. All Nash equilibria of the form ((a, a, a), N) for a < 1 are in the ugly set, but ((1,1,1), N) is in the set B. Obviously, when a stable partition exists, the equilibria it generates are identical to the S-CPNE. We now explore the connection of S-CPNE with the recursive definition of a CPNE due to B-P-W in the case of finite player games . Recursive Definition of CPNE : For any singleton coalition { i } , define a to be optimal for (i) if i is playing a best response in a. Having defined optimality for all coalitions of size (k-1) or less, define optimality for a coalition S of size k (>2), as follows: Say that a is self -enforcing for S if it is optimal for every TcS . Say that a is optimal for S if it is self -enforcing for S, and there does not exist any b self -enforcing for S such that (b,S) dominates (a,S). Finally, if N is finite, say that a is an R (recursive) -CPNE if a is optimal for N. The following example illustrates that the semi-stable partition is an improvement on the stable partition. It shows that there are cases in which the S-CPNE coincides with the R-CPNE, but there is no stable partition. Since the S-CPNE is a strong equilibrium in this example, it also shows that corollary 1 would fail to hold if we used stability rather than semi- stability as the basis of the definition. 10 Example 3: N= (1,2), A = [-2,1], A = [-1,1), U (a , a ) = U (a , a ) =aa. 112 2 12 12 In this example, strategy vector (-2,-1) strictly Pareto dominates all other strategy vectors. Since it is self enforcing, it is the unique R-CPNE. It is also the unique S-CPNE, since ((-2,-l),N) belongs to G n and dominates any other agreement involving N. However there is no stable partition; for example, agreements of the form ((1, a ),(2)) are neither good nor bad, by an argument identical to that of example 1 In this example, the equilibrium is intuitively plausible, and the two definitions coincide. In general the S-CPNE are a subset of the R-CPNE. Theorem 3 : In a finite player game, if a is a S-CPNE, it is a R-CPNE. Proof Let (a,S) € G in a semi-stable partition. We use an inductive method to establish that a is optimal for S. This is obviously true for any singleton S. So suppose it is true for all coalitions of size not exceeding k-1 , and let #S = k. First, we establish that a is self -enforcing for S. If not, there exists T C S for which a is not optimal. By the inductive hypothesis, (a,T) € G. Therefore it is dominated by (b.V) g B. But then (b,V) dominates (a,S). This contradicts (a,S) G G. Next, we show there cannot be any d which is self -enforcing for S such that (d,S) dominates (a,S). Suppose there is. Since (a,S) € G, (d,S) is in B. We claim that there exists (e,S) € G which dominates (a,S), which would lead to a contradiction. Since (d,S) e B, there exists (f,T) e G which 11 dominates (d,S). If T C S, Che induction hypothesis implies f is optimal for T. Then d cannot be optimal for T, contradicting the hypothesis that d is self -enforcing for S. So we must have (f,S) e G which dominates (d,S) and therefore also (a,S). Putting e = f, we are done. ■ The following theorems establish circumstances in which the S-CPNE and the R-CPNE coincide: Theorem 4 For finite player games, if a stable partition exists the S-CPNE and R-CPNE coincide. Proof : Given the result of Theorem 3, we only have to show that every R-CPNE is an S-CPNE, i.e., if a is optimal for N, then (a,N) e G in the semi-stable partition. By theorem 2, if a stable partition exists, the serai-stable partition is stable. Any agreement in B is dominated by an agreement in G and by Theorem 3 all agreements in G are optimal, so all agreements in B are non optimal. Since these two sets exhaust the set of agreements, the set G equals the set of optimal agreements. ■ In order to demonstrate the equivalence of the various versions of CPNE we require that the stable partition exists. In one important case existence is easily established: Theorem 5: In any finite player, finite strategy game, a stable partition exists. Proof : By Theorem 1, a semi-stable partition exists, and by Lemma 1 (a) the set U is empty. ■ 12 Next we provide an example where S-CPNE do not coincide with R-CPNE; moreover, the latter is "unreasonable." Example 4: N = (1,2), A - (0,1), A = [0,1), — - 1 2 U (a , a ) = U (a , a ) =aa. 112 2 12 12 In this game, there is a unique Nash equilibrium (0,0). Since this is the only self -enforcing strategy vector for (1,2), it is optimal for (1,2), and therefore a R-CPNE. We claim that (0,N) £ G. Suppose otherwise. Now (0,N) is dominated by (a,N) where a a > 0. So it must be that (a,N) £ B, and there 12 exists (c,S) £ G dominating (a,N). If S = N, then (c,N) would also dominate (0,N) , a contradiction. Clearly S must be (2) and c = 1, c > a . So — J 12 2 ((l,c),(2)) £G . This is dominated by ( ( 1 , c +e ) , { 2 ) ) , which must therefore be 2 2 * * in B. Any agreement that dominates this must be ((l,a ),{2)) with a > c +e . 2 2 2 * * Therefore, there is ((l,a ),{2)) 6 G, with a > c +e > c - - so it dominates 2 2 2 2 ((l,c ),{2)) £ G, a contradiction. ■ 2 The R-CPNE in this example appears unreasonable, since it has player 1 choosing a dominated strategy. If 2 conjectures that 1 will not play a dominated strategy, 2 should play some a close to 1. The importance of self enforcing agreements is that they protect a player from being "double-crossed" but in this example, they prevent players from enjoying mutually beneficial actions, solely because there is no "best" action of this sort. Were we to allow in some fashion "near- rational" behavior for the coalition (1,2), we would be able to describe actions a with a = 1 and a close to 1 as "almost" - 1 2 self -enforcing, and therefore superior to 0. In the following section, we extend our approach to allow for such forms of "almost" self -enforcing agreements . 13 With a slightly more complicated example, we can show that R-CPNE need not be S-CPNE, even in a game with compact strategies and continuous utility functions : Example 5: N = (1,2,3,4) , A - [0,l]x{0,l) i tya) - p x p 2 p 3 p,[x 2 - iv x 2 |] U 2 (a) = p iP2 P 3P J2x i - x 3 - |x 2 -x 3 |] U(a)-pppp[2x -x - I x -x I (1-x +x ) ] 3 _ r l r 2 r 3 r 4 1 2 ' 1 3 ' 12 U (a) = pppplx] H 1 2 3 H M where x denotes the real number in [0,1] chosen by i, and p e(0,l) the second i i component of i's decision. (Think, of this game as an extension of the game in k 1c k k example 2: Call any agreement with p=p =p = p=la "participative" 12 3 i> agreement; if all four players agree, players 1-3 play the game in example 2; otherwise, all players receive 0.) k k k k It is obvious that any strategy with p=p= P = p=0is self -enforcing for N. We shall establish that any such agreement is an R-CPNE but not a S-CPNE. To show that any such strategy a is an R-CPNE, note that any dominating agreement must be participative. However, no participative b is self -enforcing for N. Suppose otherwise; then it must constitute a Nash equilibrium, and x - x - x = x, say, while x =1. If x < 1, then any 1 2 3 J 4 participative strategy c with real-valued components (x+e , x+e , x+e , 1) is self -enforcing for (1,2,3). This is established by arguments analogous to those in example 2: neither of the first three players can unilaterally deviate profitably, and neither can any pair-subcoalition of (1,2,3) engineer 14 a coordinated deviation that is self -enforcing . So b cannot be self -enforcing for N, as (b,N) is dominated by (c, (1,2,3)), implying that b cannot be optimal for (1,2,3). If x = 1, then (b,N) is dominated by (d,{2,3)), where d is a k k participative strategy with x - x - 0, which is optimal for (2,3). We next show that (a,N) J G in any semi-stable partition. Now (a,N) is k k k dominated by (e,N) where e is a participative strategy vector and x - x = x — rr oj 12 3 =» x < 1 and x =1. If (e, N) € B then (a,N) € G, and we are done. 4 Therefore, suppose that (e,N) e B. If so, there is something in G which dominates it. It cannot involve singletons, or paired coalitions, neither can it include player 4. So it must involve the coalition (1,2,3). Further, to be k k k * in G , it must involve x - x = x = x where x < x* < 1 . But any such 12 3 J agreement must be in U , by reasoning which is identical to that of example 2. Therefore (e,N) G U. Contradiction. ■ The two examples above establish that the recursive and non- recursive formulations are not identical in all cases. Since the equilibria generated by a stable partition are S-CPNE, example 5 demonstrates a fortiori that the characterization in terms of stable partitions is not equivalent to the recursive formulation. Since our results seem to be different from those claimed in Greenberg [1989] it is important to indicate the source of the discrepancy. Greenberg finds that R-CPNE can be characterized by using stable partitions. The problem is that he implicitly assumes that a stable partition exists. As we have seen, this cannot be demonstrated in general, except for finite-player, finite -action games. 15 III. Extended Agreements The recursive and non- recursive definitions are equivalent for games with finite strategy spaces and finite numbers of players. The equivalence breaks down in other cases. In example 4 equivalence would be restored if we modified the game by adding strategies which corresponded to the limit points of the strategy space. But example 5 demonstrates that this proposed resolution will not work in general. In this section we will examine a more satisfactory resolution for the case of infinite strategy spaces. In this section we assume that the set of players is finite and that each player's utility function U. is continuous on the compact strategy space ^ A.. An extended agreement (a,S) consists of a coalition S C N and a sequence 1 2 of strategies a = (a , a , ...) which satisfies the following conditions: 1: The sequence converges. k k' 2: For all t € S, a = a for all k, k' . t t In other words, an extended agreement is a sequence of coordinated actions by the members of coalition S, holding the actions of non-members fixed. Extended agreements include simple agreements as a special case: identify a simple agreement with an extended agreement in which the sequence of strategy vectors is constant. Let A denote the set of extended agreements. An extended agreement (b,T) dominates (a,S) if (a) TCS (b) There exists k such that b = a for all j € N\T j j (c) lim U (b k ) > lim U (a*) for all ieT. 16 It is useful to note that (b,T) dominates (a,S) implies that it also dominates (a,V) for any VDT if (a,V) is in A . Dominating agreements are coordinated deviations from initial agreements: At any step in the process that forms the initial extended agreement, say k, a subcoalition can agree to break away and follow their own coordinated deviation. The definition of a serai-stable partition carries over without modification, as do the proofs of theorems 1 and 2 establishing the existence and uniqueness of the semi-stable partition. A strategy vector a* is an Extended Stable Coalition Proof Nash Equilibrium (ES-CPNE) if it is the limit of a sequence of strategy vectors a, where (a,N) is in G for the serai - stable partition of extended agreements. For finite-player games, there is a recursive definition in extended agreements analogous to the recursive definition of the previous section: Recursive Definition of Extended CPNE : For any singleton coalition (i), say that (a,(i)) e A is optimal if there does not exist any (b, {i)) in A which dominates (a, ( i ) ) . Having defined optimality for all coalitions of size (k-1) or less, define optimality for a coalition S of size k (>2), as follows. Say that (a,S) e A is self -enforc ing if there does not exist an optimal (b,T) that dominates (a,S), with T C S. Say that (a,S) is optimal if it is self -enforcing and there does not exist any self -enforcing (b,S) that dominates (a,S). Finally, if N is finite, say that the strategy vector a* is an Extended Recurs ive -CPNE (ER-CPNE) if it is the limit of a sequence of strategy vectors a such that extended agreement (a,N) is optimal. 1 7 The next result is the major result of the paper. It says that if we define Coalition Proof equilibria in terms of extended agreements, then for all finite player games -- those with infinite strategy spaces as well as finite strategy spaces -- the recursive and the non-recursive definitions are equivalent. Theorem 6: Using extended agreements, there is a unique serai-stable partition, which is also a stable partition. In this stable partition, (a,S) 6 G if and only if (a,S) is optimal; hence the limit of a is an ER-CPNE if and only if it is an ES-CPNE. Proof: See appendix. A consequence of the proof of this theorem is that there is an equivalent, somewhat simpler recursive definition. Corollary : The following definition is equivalent to the other definitions of Extended CPNE. Alternative Recursive Definition of Extended CPNE : For any singleton coalition (i), say that all (a,(i)) e A are self -enforcing . Having defined self -enforcing for all coalitions of size (k-1) or less, define it for a coalition S of size k (k>2) as follows. Say that (a,S) G A is self -enforcing if there does not exist a self- enforcing (b,T) that dominates (a,S), with T C S. Finally, if N is finite, say that the strategy vector a* is an Extended-CPNE if it is the limit of a sequence a of strategy vectors such that the extended agreement (a,N) is self -enforcing and not dominated by any self enforcing agreement. Proof: See appendix. It is instructive to use examples 2 and 5 to contrast the extended equilibrium definition with the initial definitions. In example 2, the unique extended equilibrium is the point (1,1,1). Although it is not self enforcing, it is the limit of a sequence of self enforcing agreements (x,x,x) and is the optimal member of this class. There was no R-CPNE and no S-CPNE. Example 5 shows the power of our new definition. The fact that the set of optimal three player agreements is empty allows unreasonable R-CPNE in the four player game. Our definition of an S-CPNE eliminates these equilibria, but does not suggest an alternative. The extended equilibrium for this example is the point (1,1,1,1): it is "almost" self enforcing, and is maximal among such points. IV. Games with a Countably Infinite Number of Players Theorem 1, demonstrating the existence of a semi-stable partition, does not depend on the number of players in the game being finite. But if there is an infinite number of players, the semi -stable partition need not be unique. This fact gives rise to the following definitions: The strategy vector aeA is a Weakly Stable CPNE if (a,N)eG for some serai-stable partition of A. It is a Strongly Stable CPNE if (a,N)eG for every semi-stable partition. 19 The following example illustrates the distinction: Example 6: N = {1,2,3...}; A. = (0,1) for i e N. Thus a strategy vector is an infinite string of zeros and ones. In this game any strategy vector gives a payoff of zero to all players, except for strategy vectors listed in the table below. For a strategy vector x = (x.. ,x_ ,x_ , . . . ) in the table, the corresponding payoff vector u = (u. ,u.,u.,...) is indicated to the right: x 1 - (1 1 1 1 1 1 ...) u 1 - (2,2,2,2,2,2, x 2 =(100000...) u 2 -(1,3, 3, 3, 3, 3, x 3 = (1 1 1 1 1 ...) u 3 - (1,1,4,4,4,4, x 4 =(101000...) u 4 - (1,1,1,5,5,5, x =(101010 ...) u = (1,1,1,1,1,1,... In this game there are two complete stable partitions; in one all the even numbered strings are Weakly Consistent CPNE, in the other all the odd numbered strings are Weakly Consistent CPNE. There is no Strongly Consistent CPNE. 00 Note that x is not an equilibrium in either partition. ■ It might seem a difficult matter to check whether an agreement is in every semi-stable partition; in fact the procedure for doing so is relatively simple. This is due to the following theorem: * * * Theorem 7 : There exists a minimal semi-stable partition {G , U , B ) -- that * * * is (G , U , B } is a semi-stable partition such that for every other semi-stable partition (G, U, B} G c G, and B C B. 20 Proof: In the derivation in theorem 1, let 7* be the first ordinal such that •*• ■*■ G ,_ = G . , , and let G = G _ B = B . . Note that the set G n will belone to 7* 7*+l 7* 7* the set G in any serai-stable partition, B_ will belong to the B set in any semi-stable partition, and if for all a < 8 , G and B belong, respectively to a a ° J G and B in all semi-stable partitions, then G and B must as well.B P P Thus the minimal semi-stable partition is precisely the semi-stable partition generated in the procedure of theorem 1. As an immediate consequence, we have the following characterization: Corollary : a is a strongly stable CPNE if and only if agreement (a,N) belongs to some set G where the sets G are defined as follows: a a G- is the set of agreements not dominated by any agreement in A. For a > G is the set of agreements which are dominated by no agreement in A, except for agreements which are in turn dominated by some agreement in V " y mean x. > y. for i = 1, . . n. We will say set A dominates x if a > x for some a in A. x is an upper bound for A if A does not dominate x. Observation: If A is bounded and A dominates x, then there is a point z in the closure of A such that z > x and z is an upper bound for A. Proof of Observation : There exists a in A such that a > x. Define the set B to be points in the closure of A such that ra. > a. for i = 1, . .n. B is a non-empty, compact set. Pick z in B to maximize 2.Z.. ■ Lemma A , 2 : For any non-empty, bounded set A in IR , either there is a point x in A which is an upper bound for A or there is a sequence of strictly increasing points in A whose limit is an upper bound for A. Proof : Define a sequence recursively as follows: Given a. 1 , if it is an upper bound for A, stop. Otherwise, using the above observation, pick z. > a. , which is an upper bound for A and which is l l - 1 the limit of a sequence of points in A. From that sequence, we can pick a. such that a. is strictly greater than a. , and the distance between a. and z. l J b l-l ii is less than 2 If the process terminates the theorem is proved. If the process does not 26 terminate, take a convergent subsequence of z.'s. The corresponding a.'s form the desired sequence. ■ The key result is the following lemma: it rules out "openness" of the set of self -enforcing agreements. Lemma A. 3 : Suppose (a, T) is not optimal, but is self enforcing (if #T > 2) then there exists (c, T) which is optimal and dominates (a, T) . Proof : The result is obvious for a singleton coalition. For #T > 2 , let £ - {(d,T) self enforcing d. =» a. for i € T} In other words any self -enforcing agreement which dominates (a,T) must be in £ . Consider the set Im £ , the image in IK , the space of payoffs for members of T, from the limit strategy vectors for all extended agreements in t5 . Note that an extended agreement in "Q is optimal if and only if its image is an upper bound in Im £ . Applying lemma A. 2 to Im S, we can conclude that either there is an optimal agreement that dominates (a,T) or there is a sequence of extended agreements with strictly increasing utility for all members of T, whose utility converges to an upper bound. This sequence of extended agreements will have a subsequence (d(l),T), (d(2),T), (d(3),T) ... such that d*(l), d*(2), d*(3), . . . is a convergent sequence (recall the notational convention). Call the limit strategy vector c . Now choose a sequence of strategy vectors, one from each d(i), such that this sequence also converges to c . Call this "diagonalized" sequence c. Agreement (c,T) dominates (a,T) and no element of t? dominates (c,T). If (c,T) is self -enforcing, we are done. Suppose (c,T) is not self enforcing. Then it is dominated by an optimal agreement (f ,V) , with V c T. That means that all members of V strictly prefer * * f to c , and that for some k f k = c k for all i € V i 1 k k' k But for some d(m) and some k' , c = d (m) . And for all i 6 V, f . k' f. . That is to say, for k' f k '= d k ' (m) for all i € V. And since all members of T prefer c to d (m) , all members of V prefer f to d (m) . That is to say, (f,V) dominates (d (m),T), contradicting the assumption that all agreements in £ were self -enforcing. ■ Lemma A.A_j_ An optimal extended agreement is not dominated by any self enforcing extended agreement. Proof : Suppose otherwise that (a,T) is optimal and dominated by a 9R self -enforcing (b,S). Since one optimal extended agreement cannot be dominated by another, (b,S) must not be optimal. But then by the preceding lemma there exists an optimal (c,S) which dominates (b,S). And by Lemma A.l, (c,S) dominates (a,T), a contradiction. ■ Lemma A 5j_ For any serai stable partition, (a,T) e G implies (a,T) is optimal. Proof : Identical to the proof for simple agreements in theorem 2 of the text. Lemma A 6j_ Suppose we have a semi-stable partition with the property that for all coalitions T of size not exceeding k-1 (> 2), (a,T) e U implies that (a,T) is self -enforcing. Then (a,T) is optimal implies (a,T) € G. Proof : If (a,T) is in U it is dominated by (b,V) in U. Since the size of V is no greater than the size of T, (b,V) is self enforcing by the hypothesis of the lemma. Then by lemma A. 4, (a,T) is not optimal. If (a,T) is in B, it is dominated by (b,V) in G. By lemma A. 5 (b,V) is optimal, therefore (a,T) is not optimal. ■ Lemma A 7j_ Given a semi-stable partition and a coalition T (with #T > 2) , (a,T) G U implies that (a,T) is self -enforcing . Proof : Suppose #T =» 2 . Then (a,T) not self -enforcing , means that there is a player i in T such that (a,T) is dominated by an optimal (c,(i)). For a single -player agreement to be optimal, it cannot be dominated by any agreement, and therefore (c,(i)) e G, contradicting (a,T) G U. Now suppose the result is true for any T with #T < k - 1, and consider the case where #T = k. If (a,T) e U is not self -enforcing then there exists an optimal (b,W), wich W c T, such that (b,W) dominates (a,T). Since #W < k - 1, application of the preceding lemma implies that (b,W) is in G, contradicting the assertion that (a,T) G U. ■ Lemma A 8j_ (a,T) is optimal if and only if (a,T) G G in the semi-stable partition. Proof : Combining the two preceding lemmas we conclude that (a,T) optimal implies (a,T) G G. The reverse implication is lemma A. 5. The uniqueness of the semi-stable partition follows from the fact that the set of optimal agreements is constructed without any reference to stable partitions. ■ Lemma A 9j_ U is empty; i.e. the semi stable partition is stable. Proof: Suppose (a,S) G U. By lemma A7 , (a,S) is self -enforcing. By the preceding lemma, (a,S) € G implies (a,S) is not optimal. Thus there is (c,S) which is optimal and which dominates (a,S). By the preceding lemma (c,S) G G dominates (a,S) G U, a contradiction. ■ Proof of Corollary : The equivalence follows from the following fact: (a,T) is self enforcing if and only if it is not dominated by any self enforcing (b,S) with S C T. "If" follows from the fact that optimal agreements are a subset of self enforcing agreements. To prove "Only if" we show that if (a,T) is dominated by a self enforcing (b,S) with S c T, then it is dominated by an optimal (c,S). This follows by applying lemma A. 3 and lemma A.l. 30 References [1] G. B. Asheim, "Renegotiation- Proofness in Finite and Infinite Stage Games Through the Theory of Social Situations," working paper, Norwegian School of Economics and Business Administration, July, 1988. [2] C. Asilis, C. M. Kahn, and D. Mookherjee "A Unified Approach to -Proof Equilibria," working paper, University of Illinois, Urbana-Champaign , July, 1990. [3] D. Bernheim, B. Peleg, and M. Whinston, "Coalition- Proof Nash Equilibrium: Part I, Concepts," Journal of Economic Theory . 42, (1987), 1-12. [4] J. Boyd and E. C. Prescott, "Financial Intermediary Coalitions," Journal of Economic Theory. 38 (1986), 221-232. [5] B. Dutta, D. Ray, K. Sengupta and R. Vohra, "A Consistent Bargaining Set," Journal of Economic Theory . 49 (1989), 113-134. [6] J. Greenberg, "Stable Standards of Behavior: A unifying approach to solution concepts" Stanford University, IMSSS Economics Series, Technical Report 484, March, 1986. [7] , "Deriving Strong and Coalition Proof Nash Equilibrium from an Abstract System," Journal of Economic Theory . 49 (1989), 195-202. [8] , The Theory of Social Situations: An Alternative Game-Theoretic Approach, Cambridge University Press, 1990. [9] C. M. Kahn and D. Mookherjee, "Decentralized Exchange and Efficiency Under Moral Hazard" working paper, University of Illinois, April 1990. [10] and , "A Game Theoretic Approach to Decentralized Markets with Moral Hazard," working paper, University of Illinois, September, 1990. [11] R. Marimon, "The Core of Private Information Economies," Paper presented at the Mid-West Mathematical Economics Conference, Minneapolis, MN 1988. [12] R. Myerson, "Sustainable Matching Plans with Adverse Selection," Northwestern University working paper, 1988. [13] J. von Neumann and 0. Morgenstern, Theory of Games and Economic Behavior, Princeton: Princeton University Press, 1947. [14] A. E. Roth, "Subsolutions and the Supercore of Cooperative Games," Mathematics of Operations Research . .1,(1976), 43-49. 32 Footnotes See also Dutta et al. [5], 2 In other words, the dominion of G is precisely the complement of G. The definition would be unaffected by writing it with one-way rather than two-way implications . 3 In a semi-stable partition it is possible for the good set to be empty (and therefore the bad set as well). This is the case in example 1 above. However the good set will not be empty if the payoff functions are continuous and individual players' strategy sets are closed. In the definition of a semi-stable partition, unlike the definition of a stable partition, the double implications are crucial. 4 This proof is a special case of the existence proof for subsolutions in Roth (1976). If there are a finite number of players, then the proof does not require transfinite induction. Again, having an open set of strategies is not necessary; more complicated examples can be derived with compact strategy spaces and continuous payoffs. A natural extension of this approach will handle games with discontinuous payoffs by modifying (iii) in the definition of dominance as follows: k k lim inf U.(b ) > lim sup U.(a ) . To handle non-compact action spaces as well, it will be necessary to substitute raonotonic sequences for convergent sequences of strategy vectors, and to use the overtaking criterion for comparison of limit payoffs. An alternate proof of uniqueness is provided in theorem 6. HECKMAN BINDERY INC. JUN95 „ 1T „, JN MANCHESTER 1Uj " INDIANA 46962