THE U N I V E R S I T Y OF M I C H I G A N COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Department of Mathematics Technical. Report ON SOLUTIONS TO n-PERSON GAMES IN PARTITION FUNCTION FORM William F. Lucas ORA Project 04637 under contract with: NATIONAL SCIENCE FOUNDATION GRANT NO. G-18914 WASHINGTON, DoCo administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR April 1963

This report was also a dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in The University of Michigan, 1963.

TABLE OF CONTENTS Page LIST OF FIGURES iii ABSTRACT iv CHAPTER 1. n-PERSON GAMES IN PARTITION FUNCTION FORM 1 lo Introduction 1 2. A Game and the Value of a Coalition 3 3. Imputation, Domination, and Solution 4 4. S-Equivalence 7 5. 2-Person Games 9 6. The Partition INJ and Games With Large v(N) 10 7, The Partition [1),ooo,(nn] 12 2. THE 3-PERSON GAMES 14 1o Introduction 14 2, Solutions 16 3. Uniquene s s 24 3, THE 4-PERSON GAMES WITH DISTINCT IMPUTATION SIMPLICES 29 1l Introduction 29 2. Some Lemmas 33 5o Solution 35 4. Cases 40 5. The Exceptional Cases 44 6. Remarks 56 4, n-PERSON GAMES WITH ONLY (n), (n-l,l) AND (1,1,.o,1) TYPE PARTITIONS 58 lo Introduction 58 2o The Constant Sum Case 60 3. The Distinct Simplices Case 71 4, A Separation Theorem 75 5. Intermediate Cases 76 5, UNSOLVED PROBLEMS 80 REFERENCES 85 ii.

LIST OF FIGURES Figure Page 1o Genus 1. 20 2, Genus 2, Species Ao 20 35 Genus 2, Species B. 21 4, Genus 3, Species Ao 21 5. Genus 3, Species Bo 22 6. Genus 3, Species C, Case cl > d. + d2 + d322 7. dom a via (h,k)o 31 8~. dom a. via [hk,pjo 31 9, EhnA"' for P' = [(h},(k,p,q} } 38 10. E nA for P = ( (h,k, {p, q }} 38.1LI, Exceptional Case on A50 45 12. Exceptional Case on A O h6 135 Exceptional Case on A h47 14, Solution for n = 3 and C 0, 62. 15. Solution for n - 3 and Z r o 62 16., Solution for n - 4 and Z ~ o 63 e a. a

ABSTRACT John von Neumann and Oskar Morgenstern (Theory of Games and Economic Behavior, Princeton University Press, 1943) formulated a theory of n-person games in terms of a characteristic function which is defined on the set of all subsets of the set of players. Since then several reformulations of the theory have appeared. Among the more recent developments in this direction is a presentation by R. M. Thrall ("Generalized characteristic functions for n-person games," Proceedings of the Princeton University Conference on game theory, October 4-6, 1961, ppo 157-160) of a theory of n-person cooperative games with side payments in terms of a partition function which is defined on the set of all partitions of the set of players~ This formulation assigns a real numbered outcome to each coalition in each partition of the set of playerso For each such partition, the sum of the outcomes of its coalitions then determines an imputation simplex~ The concepts of dominance and solution are similar to those in the von Neumann-Morgenstern theory, except that an imputation can dominate via a certain coalition only if it is on an imputation simplex realized by a partition containing that coalition. This approach reduces to the von Neumann-Morgenstern approach when all the imputation simplices are the same. The object of this thesis is to present solutions (stable sets) for games in partition function form as defined by Thrall. Chapter 1 summarizes the formulation of the theory of these games, and gives the solutions for the 2-person games and the n-person games in which the largest payoff goes to the partition made up of the single coalition containing all of the players~ All solutions for all 3-person games are discussed in Chapter 2. Chapter 3 gives a polyhedral solution for each 4-person game in which distinct partitions give rise to distinct imputation simplices. Partial results for n-person games in which only partitions of type (n), (n-l,l) and (1...,1) have large outcomes are presented in Chapter 4. The final chapter lists some of the unsolved problems in the theory. In comparison with the von Neumann-Morgenstern games, the Thrall theory gives more cases to consider and usually more imputations in a solution. But there are fewer solutions in the latter theory as the number of impu.tation simplices increases. The discriminatory solutions and the bargaining curves in the von Neumann-Morgenstern theory do not seem to appear in the Thrall games unless some of the imputation simplices coincide. iv

CHAPTER 1 n-PERSON GAMES IN PARTITION FUNCTION FORM 1. INTRODUCTION In 1944, von Neumann and Morgenstern [8] formulated a theory of n-person games in terms of a characteristic function which is defined on the set of all subsets of the set of players. This formulation was followed by much criticism of it, and several reformulations of the theory have appeared. An excellent survey of this work, through 1957, is given in the book by Luce and Raiffa [2],o A complete bibliography of all of game theory up to 1958 is contained in [7L] Among the more recent developments in this direction is a formulation by R. M. Thrall [6] of a theory of n-person cooperative games with side payments in terms of a partition function which is defined on the set of all part.::,is of the set of players. Thrall's formulation assigns a real numbered outcome to each coalition (coset) in each partition of the set of players. For each partition, the sum of the outcomes of its coalitions then determines an imputation simplex. The concepts of dominance and solution are similar to those in the von NeumannMorgenstern theory, except that an imputation can dominate via a certain coalition only if it is on an imputation simplex realized by a partition containing that coalition. This approach reduces to the

von Neunann-Morgenstern approach when all the imputation simplices are the same. R. J. Aumann, Morton Davis, Michael Maschler and Bezalel Peleg (see references in [3]) are also working on a more local theory of bargaining sets for n-person games which makes use of partitions of the set of players. It is safe to say that none of the models for n-person games proposed to date is completely satisfactory and no such single model is likely to appear. But the various models do give somen insight into the problems of bargaining and conflict resolution. Thrr object of this thesis is to present solutions (stable sets) for games in partition function form as defined by Thrall. Chapter 1 si-mrnarizes the formulation of the theory of these games, and gives the solutions for the 2-person games and the n-person games in which the lasrgest payoff goes to the partition made up of the single coalition containing all of the players. Much of this material was presented by Thrall in [6]. All solutions for all 3-person games are discussed in Chapter 2. Chapter 3 gives a polyhedral solution for all 4-person games in which distinct partitions give rise to distinct imputation simplices whenever their payoffs are greater or equal to the payoff to the partition containing the single coalition of all players. Partial results for n-person games in which only partitions of type (n), (n-1,1) and (1,...,1) are significant are presented in Chapter 4. The final chapter lists some of the outstanding problems in the theory.

2. A GAME AND THE VALUE OF A COALITION We prodeed to define an n-person game in partition function form and the value of a coalition in such a game. Let N = i,.,n] be a set of n players who are represented by 1,...,n. Let P= [P,.,Pr] be an arbitrary partition of N into coalitions P1,.. oPr. The set of all partitions of N is denoted by ff = (PF Denote the real numbers by R'. Then for each partition P assume there is an out+come function Fp ~ P+Rwhich assigns the real numbered outcome Fp(P. ) to the coalition P. when the partition P forms. The function F: IT- Fp which assigns to each partition its outcome function is called the payoff function or partition function for the game. Finally the ordered

pair r = (N,F) is called an n-person game in partition function form. For each non-empty subset M of N define the value of M as (1) v(M) = min Fp(M) (PIMqP] and define v(f) = 0. Let v((i]) = vi for each iEN. This minimum is over all partitions P which contain M as a coset and not the partitions in which M is a union of more than one coset. That is, secret coali-e N 1 tions are prohibited. This function v:2 -OR need not satisfy the supe radditivity condition v(M)U M2)>V(M1 )+v(M2) whenever Min M2 = -. In fact, there exist games for any choice of the values v(M). If we were to take the above minimum over all P that have M as a union of cosets of P. we would obtain a superadditive function as in the von Neumann-Morgenstern theory. This was proved by D. B. Gillies on p. 68 in [7]. 3. IMPUTATION, DOMINATION, AND SOLUTION For a given game, the concepts of imputation, domination, and solution can now be introduced in a manner similar to that in the von Neumann-Morgenstern theory.

A vector a = (al,. ooan) is called an imputation if (2) ai > vi i = l...,n and (3) ai = Fp(Pj) for some PCIo icN P.eP Let R = the set of all imputations of a game. Conditions (2) and (3) are called individual rationality and realizability respectively. An imputation a is a possible set of payoffs to the individual players, amount ai to player i, at the end of a game. (2) states that no player need accept a payoff less than what he is assured of if he forms a coalition by himself. And (3) states that the total payoff to all of the players equals the sum of the coalition outcomes for some partition. This definition of an imputation allows for side payments between coalitionso Replacing the equality in (3) by "less than or equals" would allow for a disposal of wealth, and does not appear to change the following theory significantly. If a and b are imputations and M is a non empty subset of N, then a dominates b via M, denoted a dom b, means that (4) ai > bi for all i&M,

(5) Z aji < v(M) iEM and (6) V ai = X Fp(Pj) for some PeIT with McP, i~N PjeP These conditions are called, respectively, M-preferable, M-effective, and M-realizable. Condition (4) says that each player in M prefers his payoff in a to that in b. (5) states that M can be assured of getting at least what they get in a no matter what N - M does, and (6) states that a could arise when M is actually acting as a coalition. This last restriction does not appear in the von Neumann-Morgenstern theory. a is called exactly M-effective if the equality holds in (5), and strictly M-effective if the inequality holdso If (5) fails, then we call a M-ineffective. We say a dominates b, denoted a dom b, if there exists such an M such that a dom b. The relation "dom" is M neither transitive nor antisymmetric. Also, if ACR, let dom A = M (beRla dom b for some acA], and dom A = (bcR a dom b for some aeAlo M Clearly, dom (AU B) = dom AU dom B and dom (AOB) C dom An dom B. A set of imputations K is a solution if (7) Kfdom K =

and (8) KlJdom K = R. These two conditions are equivalent to the one condition R - dom K = K. In words, these two equations say that (7') if a and b are in K, then neither dominates the other, and (8') if c is not in K, then there exists an a in K which dominates c. If B is some subset of R. we will also say that a subset K of B is a solution for B if K dom K = 0 and KU dom K DBo A set that is more stable than a solution set is the core defined by C = R - dom R, that is, the undominated imputations in R. For games in partition function form the core is similar to this concept in the classical theory as discussed by Gillies on po 71 of [7] Since C = ~ for many games, we will proceed to find solutions. 4o S-EQUIVALENCE Let r and r' be two n —person games (in partition function form). r and r' are called S-equivalent if there exists constants

c > 0O al,,.. an and a permutation C of N such that (9) Flc(Pi) = cFp(Pi) +~ a. jePi for all PiEP and all PeIR. Intuitively, C relabels the players, c changes the unit of wealth, and aj is an ante or subsidy that player j makes before the play of the game. F is in normal form if vi = 0 for all i~N. r is in strict normal form if F is in normal form and max j Fp(Pi) = 1 Pef PieP It is easy to prove the following facts about S-equivalence. Sequivalence is an equivalence relation. Each equivalence class contains a game in normal form. If r has some Pel for which Fp(Pi) > O0 then there exists F' in strict normal form such that P. eP r' is S-equivalent to F. Two games in strict normal form are Sequivalent if and only if they are identical up to some permutation a of No Two S-equivalent games F and F' are isomorphic, that is, there is a one to one correspondence between R and R' that preserves the relation "dom" for all MCN, and thus preserves solutions, M In what follows, we assume that all games are in normal form but not necessarily strict normal form~ Thus equation (2) now becomes (2') ai >O,

For a partition P in a game r let IPI = ( Fp(Pij) P. eP 1 Also, for any constant b let A(b) = a a i = b and a > 0). i~N Then for each Pefn conditions (2') and (3) give an imputation simplex A( IPI ) which we will also denote by A(P)o. 2-PERSON GAMES For a 2-person game, N = (1,2) and I = (P,P ) where 0 1 P = (N) and P = ((1), (23). Assume F~0(N) = c and F pl((i) 0 for i = 1,2. Then v(N) = c and vi = i = 192. And R = A(c)U ((0,0)). Clearly, if c > 0 then the unique solution is K = A(c), and if c < 0 then the unique solution is K = R = ((0,0)). That is, the two players must agree on some way to split the amount c > O or else both get nothing~

10 6. THE PARTITION (N) AND GAMES WITH LARGE v(N), Define a > b to mean ai > bi for all iEM. Similarly define > M M and =o M Lemma 1. If a dom b and b > c where MC SCN, then a dom c M S M Proof. Since a dom b, a is M-effective and M-realizable. And M clearly ai > ci for all ieM. Corollary. If bedom A and ACKUdom K, then bedom Ko N The following theorem states that no part of a solution can be below the imputation simplex A(c) realized by the partition (No. That is, no imputation in a solution can be on an imputation simplex A(a) with a < c. And Theorem 2 then shows that this partition (N) causes no trouble in finding solutionso Theorem 1. If K is any solution and a < c = v(N), then KnA(a) = ~o Proof, Let beA(a) and define a by ai = bi+d where nd = c- bi > 0~ i eN Then aEA(c) and a dom bo If aK then bedom K. If ajK, then acdom K N N M for some MCN and so bcdom K by Lemma 1o In either case bJK. M Theorem 2. If K is a solution for T = UA(P) where this union is over all PIF with IPI > c = v(N) and P ~ (N}, then K' = KU (A(c)-dom K) is a solution for all of Ro

11 Proofo If A(c)CT then A(c)C Kl dom K by hypothesis and K' = Ko If A(c)( T = 0 then clearly A(c)CK'U dom KCK'U dom K'. In either case, if beR-A(c)-T then bEA(a) for some a < c and so bedom A(c) N as was shown in the proof of Theorem 1. So bedom A(c)CK' Udom K' N and then the above Corollary gives bedom K'. Thus K'Udom K' = R. If A(c)CQT then K'N dom K' = K dom K =.o If A(c)n T = 0 then K'f dom K' = [K U(A(c)-dom K)] idom[KU (A(c)-dom K)] = [Knldom K] U [(A(c)-dom K)n dom K]U [Kndom (A(c)-dom K) ]U [(A(c)-dom K)n dom (A(c )-dom K) ]_(CU VU [Kn dom A(c) ] U [A(c)n dom A(c) But bedom A(c) implies bi < c, and aeK or aeA(c) implies L ai > c. icN ieN So (KUA(c))ndom A(c) = o Thus K' ndom K' = ~. Therefore, K' is a solution for R. We will now give the solution for n-person games in which the outcome to the partition (N) is greater than the sum of the outcomes for any other partition~ Theorem 3. For an n-person game with F (N) = v(N) = c > (N) 7 Fp(Pj) for all partitions P different from (N], the unique Pj eP solution is K = A(c)o

12 Proof. Note that c > 0 since v(N) > Fp((i]) _> vi = 0 icN iEN where P = {[l,o, v(nj]o Lest K = 5 in Theorem 2 and then K' = A(c). So A(c) is a solution. It is the unique solution by Theorem lo For many games of the type in Theorem 3, the solution A(c) seems *to contain too many imputations, but if all the players in N are actually acting as a coalition, then any imputation in A(c) seems reasonable, at least as reasonable as the discriminatory solutions in the classical theory. in general, a solution for a game in partition function form has at least as many imputations as a similar solution in the classical theory. However, Thrall games usually have fewer solutions than the corresponding von Neumann-Morgenstern games as the number of distinct imputation simplices A(P) (P[(N) nor ((l,, (:r3) increases. It is also clear from Theorem 3 that the intersection of all solutions need not be the core for Thrall games, because A(c) is the unique solution but. an imputato.ion -below A(c) may dominate some imputations on A ( c ) 7,. TIHg PARTrTION (1,.o o,n j We, will now show that the partition ((1,,o, (n]j} causes no trouble in finding solutions~ Lemma 2. Domination via one element subsets (i) is impossible. Proof~ a dom b implies O = vi > ai > bi > 0 which is impossible (i ) Theorem 4. If K is a solution for V = UA(P) where the union is

13 over all PcT except P = P' = (f1,..., (n]J, then K' = KU (A(g) - dom K) is a solution for all of R where g = IP'I = E Fp ((i)o. icN Proof. If A(g)CV then R = V and K' = K and K' is a solution for R. So assume A(g)f V = 9. Then K' Udom K' = [KU(A(g)-dom K) ]U dom[KU (A(g)-dom K)] = [KUdom K] U [KUdom (A(g)-dom K) ]U [(A(g)-dom K)U dom K] L[(A(g)-dom K)U dom (A(g)-dom K) ] (K Udom K)UA(g) = R. And K'0 dom K' = [KU (A(g)-dom K) i] dom [K U (A(g)-dom K) ] C[Kndom K]UJ [(A(g)-dom K) dom K]/J ([KU (A(g)-dom K)] i dom A(g)) = A, because dom A(g) = Q since the only coalitions realizable for aeA(g) are one element coalitions and domination by these is impossible by Lemma 2. Therefore, K' is a solution for Ro As a result of Theorems 2 and 4, only the imputation simplices that are at least as "high" as A(c) where c = v(N) and that are realized by the non trivial partitions will be considered in finding solutions. So the appropriate points on A(c) and A(g) must be appended to the solutions that are described in what follows in order to get a complete solution for all of R.

CHAPTER 2 THE 3-PERSON GAMES 1. INTRODUCTION In this chapter, we will discuss the 3-person games in partition function form. The set of players is N = (1,2,3} and the set f = [PP) of partitions of N consists of PC = (N} pi = ((i},(jk}} i = 1,2,3 p = ((1},(2),(3}} where in this chapter i,j,k always stand for distinct elements of N. We denote the values of the outcome functions by FpO(N) = c Fpi (i}) = di Fpi(ljk}) = ei i =1,2, Fp4((i]) = gi i = 1,2,35 Then the values of the coalitions of N are v(X) = 0 14

Vi = min(di,gi) i = 1,2,3 v((j,kj) = ei i = 1,2, v(N) = ce Further reducing to normal form under S-equivalence gives vi = 0 and so one of di or gi = O and the other is non negative, and also ei < ci where we define Ci = di + ei The set R of all imputations consists of the vectors a = (aj,a2,a3) with ai > 0 which satisfy one of the equations al + a2 + a3 = c al + a2 + a3 = di + ei = ci i = 1,2,3 al + a2 + a3 = g1 + g2 + g3 = go These five imputation simplices are realized by the partitions P0, Pi, P4 and are written as A(c), A(ci), A(g), respectively. If a and b are imputations and N DM / 0, then a dom b means M ai > bi for idMi

16 I ai < v(M), and ieM a is on an imputation simplex realized by a partition that contains M. But domination via M = (i is impossible by Lemma 2. And a dom b means N acA(c) and b is an imputation in the open octant below a. By Theorem 1, such b are never in a solution, so we do not have to worry about domination via N. Finally, a dom b means (j, k aj > bjak > bk aj + ak < v(([jk) = ei (or ai > di), and acA(Ci) o So a dominates all imputations b that are in the open wedge (xlxj < aj, xk < ak]. This wedge meets the imputation simplices A(P) with. IPI - aj + ak in congruent parallelogram shaped regions similar to the regions in the von Neumann-Morgenstern theory, for example, see Figure 72 on po 408 of [8]. On the A(P) with IPI < aj + ak these parallelograms are truncated by xj + xk = PI (or xi = 0)o 2. SOLUTIONS 'The nature of the solutions for the 3-person games depends upon the number of the simplices A(ci) that have ci > c. So for the purpose of

17 discussing solutions, four genera will be considered. Genus O0 c > Cl > C2 > c3 Genus 1l c1 > c > c2 > C3 Genus 2. c1 > C2 > C > C3 Genus 3. cl > C2 > C3 > co We assume that c1 > c2 > c3 since the other possibilities can be obtained from these by symmetry. The solutions in some genera also depend upon the distribution of equalities in the above relations. Genera 2 and 3 are thus subdivided into species. Genus 2. Species A. cl > c2 Species B. cl = c2 Genus 3. Species Ao c1 > c2 > c3 Species B. cl = c2 > c3 Species C. cl > c2 = c3 Speies Do cl = c2 = c3 From Theorem 4, the simplex A(g) need not be considered in determining solutions~ Except for describing genera, the simplex A(c) also need not be considered in determining solutions (Theorem 2), And by Theorem 1, no part of a solution is below A(c)o Therefore, only the parts of the solutions on the simplices A(ci) with q > c will be described in the following. For complete solutions, we must add the appropriate parts on A(g) and A(c)o So we now proceed to discuss the

18 solutions for each of the above cases. The verification that these are solutions is fairly evident from the geometry of Figures 1-6. The technical proofs are long but easy and will be omitted. The verification of the uniqueness of these solutions (except for Genus O) will be discussed in the following section. Our discussion of solutions is followed by corresponding figures in which the solutions K consist of the closed regions bounded by the heavy lines. In these figures, those imputation simplices A(ci) that are at least as high as A(c) appear as if they were viewed from a distance in the (1,1,1) direction, that is, in barycentric coordinates. Points on the same 1200, 600, 0~ lines have the same first, second, third coordinates respectively. The figures show the cases where ci > 0 for there are no imputations in A(ci) to consider if ci < 0. Genus O0 The unique solution is A(c). This was proved in Theorem 3 for the case of arbitrary no Genus 1. The unique solution is A(cl) - (Xlx2 + x3 < el} where recall that el = v( 2, 3) < cl. Genus 2, Species A. The unique soluton is A(cp) - [xjx2 + x3 < e} d - A,x < xl + x3 < e2 p=l where A = c -cq The last term could also be written as pq P q (xA(cp) el + Ap2 < x2 + X3, xl + x3 < e23. p=l

19 Genus 2, Species B. The solution is A(cl) - (x x2 + x3 < eli - Ix xl + x3 < e2]LUK1 where K1 is a continuous curve on A(cl) from the point (dl,d2,cl-dl-d2) to the edge (X3 = O0 whose xl and x2 coordinates are non decreasing as x3 decreases. K1 is the same as the curves in the von Neumann-Morgenstern 3-person games, for example, see Figure 82 on p. 412 of [8]. This solution is unique up to the choice of K.o Genus 3, Species A. The unique solution is U A(c ) - (x x2 + x3 < el (xx dl -x A12,xl + x3 < e2] p=l -(x x1 < dl - A13x2 < d - A23,xl + x2 < e33. Genus 3, Species B. The solution is U A(cp) - (x x2 + x3 < e - (x x + x3 < e2] p=l -(xxlI < dl - A13,x2 < d2 A23,xl + x2 < e3)j UK1 where K1 is the same curve as in Genus 2, Species Bo This solution is also unique up to the choice of Klo Genus 35 Species CO The solution is 3 U A(cp) - (x x2 + x3 < el)- ([xx < dl - A12,xl + x3 < e2J p=l -(xIx < d1 - A13s,x + x2 < e3UK LJK3 K where two cases need to be considered.

(oo,0l) A(Al) x2 - x3 - e1 (or X1 -- dl) K (c1,lO,) (O,,1oO) Figure 1. Genus 1. A(Cl) A (n2) Fir Xl + x3 = ec x"~ + x3 = el Figure 2. Genus 2, Species A.

21 A(c) -- A(2) Figure 3. Genus 2, Species B. A(1.) A(c2) A(o3) Figure 4. Genus 3, Species A.

22 (cl) = A(C2) A( Figure 5. Genus 3, Species B. A A(Cl) A(c2) = A(3) Figure 6. Genus, Specie2 cl d Figure 6. Genus 3, Species C, Case cl > d, + d2 + d3.

23 (i) If cl < dl+d2+d3, then K2 is a curve on A(c2) from the point (c2-d2-d3,d2,d3) to the edge [xl = 0} and is analogous to K1 above, and K3 is a curved bar on A(cl) of width J2A12 whose sides are the same shape as K2 and whose ends are determined by xl > 0, and x2 > d2, X3 > d3o (ii) If c q> dl+d2+d3, then K2 is a similar curve on A(c2) from the point (c2+d2+d3-2el, cl-dl-d3, cl-dl-d2) to the edge (xl = 0), and K3 is a similar bar on A(cl) whose ends are determined by xl > 0 and x2 > cl-dl-d3, X3 > cl-dl-d2o Case (ii) is the one shown in Figure 6. Genus 3, Species D. The solutions (still not counting A(g) and A(c)) in this case are the same as those in the von Neumann-Morgenstern 3 -person games. Again, two cases need to be considered. (if z- K t2+3, themo the saolutiAos are the type pictured in Figure 86 on p. 415 of [8]o (ii) If cl > dl+d2+d3, then the solutions are the type pictured in Figure 82 or Figure 83 on p. 412 of [8 ] In comparison with the von Neumann-Morgenstern 5-person games, the Thrall games give more cases to consider and usually more points in a solution, but fewer solutions in most cases. In the cases where the A(ci) are distinct, a unique solution exists and it is polyhedral with boundaries parallel to the edges of the imputation simplices A(ci)~

When some ci are equal and as large as c, then an infinity of solutions (the Ki parts) exist; and often one of these solutions is the limit of the distinct simplex case. However, this is not true when in Genus 3, Species C is considered as the limiting case of Species A. Note that the union of all solutions for some games of the type in Genus 3, Species C need not meet the A(ci) in a connected set. Also, if c > dl+d2+d3, then the core of the games in Genus 0 is empty, and since A(c) is the unique solution and need not be empty, we have an example where the intersection of all solutions is not the core. 3. UNIQUENESS The following theorems will be used to prove the uniqueness asserted in the above discussion of solutionso Theorem 5o If c, > C2 > c3, c1 > c and K is any solution, then Kn (X x2 + x3 < el ) - Proof. If el = cl-di < O, then x2+x3 < el < 0 implies xRDK and the theorem is true. But always dl > 0 or el < cl, So we can assume 0 < el < cl Let Bn = (xeA(cl) x2 + X3 < dn where dn = minfel, nAl2] and again Apq = cp-Cqo The idea of our proof is to show that there exists a neighborhood B1 of the vertex (c1,9,0) on A(cl) that is contained in KU dom K and is (2,3} [2,53 effectiveo Then the neighborhood [xcA(a) x2+x3 < d'3 of the vertex

(a,O,O) on each A(a) is in dom K and thus does not meet Ko Using these (2.,3) facts, we can continue to enlarge our neighborhood B1 to B2 B3,...until it includes all of (xcA(cl) Ix2+x3 < el = v((2,31)}. Then each region (xcA(a) x2+x3 < el is in dom K and thus does not meet K. (2,3 First, we will show that B1CKUdom K. Since K is a solution, (2,>} BlCKUdom K. But Bln dom K = ( for all M / (2,3). Because domination M via one player coalitions is impossible; and since cl > c, A(cl)ndon R = N And because BOn dom K = (, for if not then there exists aEA(cj) (j f 1 (l,i] nor i) and beB such that a dom b which implies bl < al < al+a2+a3 = cj (l{,i} and b2+b3 = cl-bl > cl-cj = Alj > A12 > min(ej,AL12 = d1, which contradicts beBI Therefore, BlCKUdom K. Next, it is then clear that (2,3) (x jx2+x3 < d'lCdom (xA(cl ) x2+x3 = dl'Qdom B1Qdom (KUd om K) = dom K. (2,3} (2,3} (2,3) (2,3} (2,3) So (xX2+X3 < dl} nK = n If dl = el, then the proof is complete. If d' < el, then d= 12 and (xjx2+xs < A12]f K = So if aEKn A(ci) (i = 2 or 3), then a2+a3 > A12 and al < ci -A12 Now, we can show that B2 CKU dom K. Because B2r dom K =, for if not, then there (2,3} (l,i) exists acA(cj)-(xl x2+x3 < A/12 and bEB2 such that a dom b, which implies (l,i} a2+a3 > A12 and bl < al = cj-a2-a3< c.-A12, and so b2+b3 = cl-bl > cl-c. +A,2 = A:j+A12 > 2A,2, which contradicts boBa Therefore, B2CK U dom Ko (2,3}

26 Next, it is then clear that ([xx2+x3 < d2] }dom (xcA(cl) x2+x3 = d2)C (2,3} dom B2C dom (KU dom K) = dom K. So (x x2+x3 < da23fK = (2,53 (2,3} (2,3} (2,3) If d2 = eL, then the proof is complete. If d2 < el, then we continue as above to get BmrCK U dom K for (2,3} m = 3,4,3o,m0 where finally dm0 = el. Then (x x2+x3 < d = elCdom (xEA(c I) x2+x3 = e1 C dom B C dom (KU dom K) = dom K. So (2,3} (2,3} (2,3} {2,3} (2,3} (x x2+x3 < el nK = 39, and this completes the proof of the theorem. The following two theorems can be proved in a manner similar to Theorem 5 and so their proofs will be omitted. By starting with a neighborhood of the vertex (O,c2,O) on A(ca) and staying where (2,3) is ineffective, we can enlarge this neighborhood to get Theorem 6. And by starting with a neighborhood of the vertex (O,O,c3) on A(C3) and staying where (2,3) and (1,3] are ineffective, we can enlarge this neighborhood to get Theorem 7. Theorem 6. If c2 > C3, C2 > c and K is any solution, then KS() (xxl+x3 < e2, xl < dl - A1} - where Apq = Cp-Cqo Theorem 7. If c3 >c and K is any solution, then KnO XX 1+X2 K e3, X1< dl - A13, x2 K d2 - A23) = g -I

27 Theorem 8 If eC1 > c2 > c3 and K is any solution, then (xlx > dl - A13 or x2 > d2 - A23}n dom K = ~ (1,2) Proof. Let D {(xeA(c3)/xl > dl-A13 or x2 > d2-A23)} We will first show that D([AK = (. For let acD, so ai > di-Ai3 and aj+ak < ei for i = 1 or 2. Then define b by bj = aj+c, bk = ak+C bi = ai+Ai3-2~ where 3e = min (ei-aj-ak, Ai3) > 0. And then b > a and b dom a, because N (j,k} c and Ai3-2e > 0, bj+bk = aj+ak+2~ < ei = v({j,kj), and bl+b2+b3 = al+a2 +a3+Ai3 = Ci so bcA(ci)o But beK Udom K. If beK, then ae dom bCdom K. (j,k} If be dom K, then clearly ac dom K (Lemma 1), In either case aJK. Therefore, DDK -= 0 That is, if a_6A(c3) nK, then al < dl-A13 and a2 < d2-As23 So if be dom K then bl < dl-A13 and b2 < d2-A23o This (1,2} completes the proof. The uniqueness of the solutions in Genera 1, 2A and 3A now follows immediately, because Theorems 5, 6 and 7 show that exactly those points on an A(cp) that are not in the described solutions cannot be in any solution.. But extending a solution from U A(cp) to all of R, that is, p=l adding appropriate parts on A(c) and A(g), does not destroy the uniquenesso Theorem 8 is used. in Genera 2B and 3B to show that although some imputations in (xeA(cl) IX2+X3 < el and xl+x3 < e2J] may have xl+x2 < e3 = v((1,23), there is still only domination via (2,3) and [1,3] to be con

28 sidered in this region. Then the uniqueness of the solutions in Genera 2B, 3B and 3C, up to the Ki parts, also follows from the above theorems and the characterization of the Ki curves in [8]~ It is also shown in [8] that, the solutions discussed in Genus 3D are all possible ones. Consequently, Section 2 lists all possible solutions for all 3-person game s.

CHAPTER 3 THE 4-PERSON GAMES WITH DISTINCT IMPUTATION SIMPLICES 1. INTRODUCTION For the 4-person games, the set of players is N = (1,2,3,4). In this chapter h,k,p,q will represent a permutation of 1,2,3,4. There are 15 partitions P = (Pl,.ooPr ] of NJ: N), ((1, ( (3J, (4]], four of type ( (h,(k,p, qJ three of type ( h, k, (p, qJ and six of type ((h,k], (p), (qj.o The 15 outcome functions Fp are specified when the 37 real numbers Fp(Pi) are given. For MCN equation (1) then gives the value of the coalition M as v(M) = min Fp(M). Assuming the games in normal MCP form gives v((h)) = vh = 0, and hence Fp([(h) > 0 for all P containing (h.o The set R of all imputations then consists of up to 15 imputation simplices in the first orthant of four dimensional space. Domination via one player coalitions (h) is impossible by Lemma 2, and domination via N is discussed in Theorems 1, 2 and 3. If a dom b M and M = (h,kJ, then equations (4), (5), and (6) gives ah > bh and ak > bk aj < v(M), and a is on an imputation simplex realized by j cM *the partition ((h,k), (p,q] )or ((h,k], (p], (q].o For such an M, dom a M meets the imputation simplex containing a in an open region shown in 29

30 broken lines in Figure 7. (The tetrahedra in the figures of this chapter picture the imputation simplices A(P) in barycentric coordinates ) The domination cone dom a meets the other imputation simplices in a simM ilar manner. If a dom b and M = (h,k,pj, then ah > bh, ak > bk, and M ap > bp Z aj < v(M), and a is on the imputation simplex A(((h,k,p], j cM (qJ 3 ). For such an M, Figure 8 shows dom a intersected with the impuM tation simplex containing ao In this chapter, we will consider the 4-person games that have distinct simplices. This hypothesis means that for the different partitions PcF -the numbers r (10) jP = Fp(Pj) j=l are distinct. We will give a solution for each 4-person game that satisfies (10), The nature of this solution depends upon the manner in which the 15 numbers Plare ordered for the given P, the relative magnitudes of these numbers, and values v(M) of the 10 non trivial coalitions M of N. Thus, the general method of this chapter applies to a great number of 4 —person games (over ten billion),. The many solutions so obtaiLned are a valuable source of examples to test additonal conjectures on solution theory~ It will further be clear that our solution is

51 Xh + Xk Fi gure d*ciom -a via C Xk V ah x~~~pxP Ilp ap~~~~~~~~~~ -xh a qh i~~ig~~~do 8. dio 2 a vi

also valid for many games in which some of the numbers given by (10) are not distincta In addition, for those remaining games in which the imputation simplices are not all distinct, it appears that solutions can always be found by combining the methods of this chapter on the distinct imputation simplices with the known solutions for the von Neumann-Morgenstern 4-person games on the simplices realized by more than one partition. But no such general existence theorem has yet been proved for all — person Thrall games. Let pi (pi, o o.,Pri) be. a partition in F and we assume that the numbers | Pil are ordered by rl~ ri+l i l Fpi(P.) > Fpi+l(P) =Pi+l j=1 j=1 for i = 1,2,..,14. Then let A' = A(Pi). Also def ine E = x > v(M) for all M6 U PJ o C- tM -j=l_ Clearly Eil, Aj is a compact convex polyhedron To find a solution K for a 4-person game that satisfies condition

33 (10) we proceed as follows. First, K' = ElnA' is a solution for A1U (R-El) where all domination is via coalitions MEP1. Second, take the elements G in E1 A2 that are maxiaml with respect to dom for all M MeP2. Then K2 = G 2U (K-dom G2) is a solution for A'UA2U (R-E2). We continue this way. Take the elements G in E -1A that are maximal i iKi - i with respect to dom for all MeP Then G UK -dom G is usually a M solution for A1U... UA U (R-E). There is only one case that may cause i trouble in this process. If M = (h,aq)P, and (h,pJ and (h,kJ occurred n s i in earlier partitions P and P where s < n < i, then dom G may domM i -1 i i -1 inate away too much from the previous solution K Then G U K i 1 i i - dom G may leave some imputations in A U.. UA U(R-E ) undominated. But if we repeat the above process of taking successive maximal elements, but now only in a region J(h) that contains the undominated imputations, i i i-i then we obtain a solution Kl(h) for J(h) which can be added to G UK i i 1 i i - dom G to get the solution K for A... UA U(R-E ). After this i 1 digression to obtain KL(h), we continue the above process until RCA Uo.. f f f J A U (R-E ) and then K = K is the desired solution for the given game. We will discuss this solution K in more detail after we give some preliminary lemmas in the next section. 2. SOME LEMMAS In order to start our induction process to find K, we must have the following lemma. Lemma 5. E EA f o

Proof. First, note that R f, since if Pg = (1}, (2], 3, (413, then 17 Fpg( (j) > 0, and thus RDA(Pg) $ ~o Thus P1 > P g > 0 j=l and A'1 0( Next, consider the partition Q made up of the pE.P1 with v(Pl) > 0 and all other cosets containing just one element. Using (10) and FQ(j)) > 0, we get pll = 7 Fpl(P.) > 7 F FQ(Qj) > pJpl QeQ P EQ min F =(P) = v(P) = v(P+). So there exists xcAl, P J - a plCQ P'EQ plEP1 V(P+) >O!cN jeP! thatP is>r That is, E'n A' If a and b are imputations, N2M and a is M-realizable and M-effective, then a dom b is equivalent to a > b. The existence of the M M maxiamal elements G in our induction follows from Zorn's Lemmao The nature of these sets of maximal elements is given in the following lemma. For additional results of this type, see Stearns [5 ] Lemma 4o If E is a compact convex polyhedron and G is the set of elements in E that are maximal with respect to i, then G is a union of closed faces of Eo Proof, Assume csG. If c is a vertex of E, then c is a closed faceo So let c be in a closed face H of E of dimension > 0. We can

assume c is in the relative interior of H or otherwise, it is in a closed face of less dimension. Then we must show that HCG. Assume to the contrary that a is in H-G. Then there exists beG such that b > ao By the M convexity of H, the line segment L(a,c)CH. Since c is interior to H, L(a,c) can be extended slightly beyond c to c' such that ceL(a,c')CHo Then c = Xa+(l-X)c' for 0 < X < 1. Since b > a and c' = c', b' = kb M M +(l-A)c' > c. But b'eE by the convexity of E. Thus b' > c which conM M tradicts ceG. Therefore, HCG. The two previous lemmas hold for n-person games with arbitrary n, whereas the following one holds only for n < 4. Lemma 5. In a 4-person game which satisfies condition (10), any aeR can be strictly effective and realizable for at most one MCNo Proof. Since the imputation simplices are distinct, a can be realized by only one partition PO But no imputation is strictly effective for a one element coalition. And the only partitions P with more than one M with more than one element are of the type Q = ((h,k), (p,q)]o But aA(Q) implies ) aj = FQ((h,k])+FQ((p,q]) > v( (h,k))+v((p,q]). jeN So if ah+ak < v((h,k]), then ap+aq > v((pqj), that is, if a is (h,kjstrictly effective then a is (p,q)-ineffective. 3o SOLUTION In this section, we give a detailed discussion of the solution K

described in the first section of this chapter. First, we will prove that K1 = EliA1 = [xcA'l 7 a. > v(M) for all MeP1) is a solution for L Li j cM Al U(R-El). If pl = (N} then ElnA1 = A' is a solution for all of R by Theorem 3. Thus assume P1 / (NJ, so MP1' implies N-M f o. To show that K'U dom K1 = A1U(R-El), let a [AlU (R-E'i) ]-K Then aj < P jeN and aj < v(M) for some MeP' Let e = v(M)- aj > 0 and P6 jeM jcM Z a. > 0 Also let MI = the number of elements in M. Thern define j-N b by b. = a. + c/IM for jcM bj = aj - 6j for jNN-M whe re.i = -6 and. a > 6. for jcN-M. Such 6j exist, because j N -M aj = p aj-6 = pl -v(M)+v(M)- aj-6 = P' -v(M)+c-6 > c-5 jcN-M j M jcM since |P ' -v(M) > Q-v(M) > F (M)-v(M)>O where Q is the partition composed of M and one element sets. Then beA', bj = v(M) and b > a, ~jeM M 1 1 1 and thus b dom a And bcK = E nA is clear from the proof of Lemma 5o M (The separation property inr Lemma 5 is only valid for n < 4, but with 1 A and thus some extra restrictions on the 6j above we could get bE A and thus

37 K1 would still be a solution for A1' (R-E1) for the case of arbitrary n. ) This proves that K1U dom K1 _ Al j (R-E1). Clearly El ndom (ElA ), and so the inclusion is an equality. Finally, K ndom K= (E'n A) n dom(E1n A1) cEn dom A' = A. This completes the proof that K = E FnA is a solution for A U (R-E). K' for P = ((h),(k,p,qJ] and [(h,k},(p,q]J is shown by heavy lines in Figures 9 and 10 respec — tit-rely. Next, we can descend to A and the part on A that is not dominated by K = E nA is E n A, which is a compact convex polyhedron bounded by x. > 0 and x > v(M) for all McP. j eM i-1 Now, proceed to the induction step. Assume that K where i > 2 is a solution for A U... UA U(R-E ) with K GA U... UA and i-1 Aj i-1 j K nA E nA This condition holds for i = 2 since from above 1 1 1 1 1 K = E OA is a solution for A U(R-E ) and it trivially has KlA1 1 AjCj-1 0 i and K OA iE -lA (where let E = R). We then need to find a K that is a solution on A U.. U A U (R-E ) with KiA_ J UA jA and Ki (i Aj- i-1 Since imputations in E are not strictly effective for any i-i i-1C 1 i- i-i i-i Mc U P and since K -A U. UAi, E dom K and j=l i-1 i is i-i E 1(A U. JA ) is the part in R below A that remains undominated by K On A this part is Ei nAi If E (lAi =, then AiCR-Ei- and so Ki = Ki is a solution for A1U)... UAi U (R-Ei) with i-1 the desired propertieso In fact K is then a solution for all of R. i-1 i i-1 i So assume that E lnA i. Clearly, E nA is a compact convex polyhedron o

Xk # Xp +Zq 'V((k,,poq})) Figure 9. ElnA' for P' 1 h), =kyp" qj Xhi + Xk = V(ihpk)) 1 1 Figure 10. EqDA for p =

39 For each MEPi let Gi(M) be the elements in E i- nAi that are maximal with respect to dom. Then Gi (M) iE nAi f(x | x > v(M)). M jcM But Ei-1'nA n x | xj < v(M)} is a compacet convex polyhedron of jcM dimension < 3 in which dom is equivalent to >. So by Lemma 4, G (M) M M meets this latter set in a union of closed faces that clearly are coni tained in (xcaA' xj = v(S) for some S EU Pj,.. Next, let G j=jcS i i i i n. G (M) eThen G E NA and M* p Gi ndom G = G. And using Lemma 5, Gi U dom G'DEi'-l nAi Also dom G D (A U.ooUA5 )(E Ei)o Because if a is in this set, then ' aj K< j P aj > v(S) for all jeN jeS i -1 SE U9PJ and aj < v(M) for some MePi So pick bcA such that b > a j=l - N jeM and X bj K v(M), and then bj > v(S) for all SeYJPi so beE m-Aio jcM jeS i i i Then b dom a and beG Udom G which implies ae dom Go M M

40 Finally, we define ~ i (11) K (GlU Kl dom G )U K1 i11) K where K = ~ unless we are in one of the four exceptional cases where [h,q)cP, and (h,p] and (h,k) occurred in partitions P and P respectively with i > n > s > 1, and Gi dominates away too much from K (Since GiU (Ki-l-dom Gi) = (G UKi1 )-dom G. no such parenthesis appear in (11)o) These exceptional cases will be discussed in Section 5. When K = i, it is clear that K -A U. UA and K AJCE _A; So in this case when K = (, it only remains to prove that K is a solution for A UO. A U (R-E'). But [A'U..UAiU (R-Ei)] - [A1 U..UAi-'U i-1 i (R-Ei-)]= [Ei-lA] 'U[(A U Oo E UA) (Eand from above G-ij dom Gicontains this set. And domi GK_ K ndom G. So if G1 UK -dom G dominates as much as K did, then K is a solution for A'l U oUAiU (R-Ei). By considering cases in the next section, we will show that this is true, So completion of the next two sections will finish the induction step of the proof. 4. CASES We will now show, except for the exceptional case handled in the next section, that i-1 i i- 1 i (12) dom K Qdom (G U K - dom G ), i-1 i-1 j Let aEK be S-effective and S-realizable where ScE kJ P o Then j =1

41 a < v(S) and acAl U U.UA. Consider an arbitrary beG which is jeS M-effective for MePi Then b. < v(M), P b. < Then_ b v(M), pi;-~ Lj < &aj, and jcM jcN jeN Z bj > v(T) for all Te'c P To prove (12), it is sufficient to show a- j=l jeT that either (i) b cannot dominate a via M, or (ii) if b dom a then M dom b Ddom a, or (iii) if b dom a then there exists a'eK such that M S M no b' eG can dominate a' via M and dom a'Ddom a. We proceed to consider S S all non trivial cases of M and S. (i) M = (h,k,p], S = (k,p,q). Then b > v(S) > a jeS jeS bj < aj and so ah > bho Thus b dom a is impossible. M jeN jeN (ii) M = (h,k,pj, S = (p,q>o Then b. > v(S) > a. and jES jES b < K aj, which implies that j bS < aj Since N-SCaM, jcN jeN jcN-S jcN-S b dom a is impossible. M (iii) M = (h,k), S = (h,k,plo If b dom a then dom bDdom a by M M S Lemma 1o (iv) M = (h,k], S = [kpq>o Then b. > v(S) > ~ aj and jeS jeS

42 bj<, aj, which implies that b < a Thus b dom a is impossible. jeN jEN M (v) M = (h,k), S = (p,q). Then bj > v(S) > aj and L_ jES jES b. < aj, which implies Yb. < Va. since M = N-So Thus /_ J j_ L J L J jEN jeN jEM jeM b dom a is impossible. M (vi) M = (h,k,p3, S = (h,k>o Assume b dom a where beG and M acKi' Let B = (xeG |_ dom a} and let z = lub (xpxceB). Define M aV'.A( \ aj) by a, = ah, ah = ak, a' = z, and a' = a-(z-ap) = jcN xq+(xh-ah)+(xk-ak)-(z-xp)+A > 0 for any xeB where L = Za~ -!x.' jcN jcN Clearly dom a = dom a' and no b'IcG can dominate a' via M. So if S S i-i i i-1 a'eK then a'cK o We then need to show that &L'eK Pick b'cB e-K then a then Pca' > such that z-bK < A and assume TeJlIP o If qcT, a -J 1 jeT y bj > v(T), and thus a' is T-ineffective. If qgT, then;' >a, T jeT and so if c d m a', then c dom a. So if a'i'K i, then Ki- which is a contradiction~ Therefore, a'eK ( a =h S (K), and.assume~i. h -1 (vii a) M = (h,q), S = (h,k}, and assume that [h,p]l~LJP o

Let B = (xeGi x dom a) and let z lub (xq xcB3. Define a'eA( a ) j eN by a = ah, a=ak, a z a =' ap -(a-a ) Clearly dom a' = dom a S S and no b'cG can dominate a' via Mo We need tO show that a' K 1 That i is, we need to show that a'~ dom Ki' for all Te U Po. So we now conT j=l sider all non trivial cases for various T. We assumed that T / (h,p3. If T = [p,qJ, then ap+a' = a +a > |P I-ah-ak > IPS -v(([h,k) > v((p,q]) by Lemma 5 where TePs, and so Ua' is not (p,ql-strictly effective. If T = (k,p), (k,p,q) or (h,k,p), then there exists beBQG such that e > where < = a3- bJ, which implies aJ > j~N-T jcN-T jeN jcT b > v(T), and so a' is T-ineffective. If T = (k,q] or (h,k,qi, jcT then a' > a so a'E dom Ki implies aE dom K, a contradiction. FiT T T nally, if T = (h,p,q), then either TePj for j < s where ScpS and a jeT = a. > v(T) so a' is not strictly effective for T. or TePj for jcT i > j > s and bh+bk > v((h,kj) > ah+ak so bp+bq < ap+aq which says b cannot dominate a via T. This proves that a', dom Ki-1 for all T when T (h,p]i UPj This completes case (vii a) J=1 i -1 (vii b) M = (h,q), S = (h,k3, and assume that (h,p]e U Po. In j =

44 this case, K1 may not be A. So this case is treated separately in the next section. Therefore, except for this exceptional case (vii b) which will be treated in the next section, we have verified equation (12) and thus completed our induction step. 5. THE EXCEPTIONAL CASES In. this section, wF: consider the more difficult case (vii b), that is, we assume M = (h,qj cki S = (h,k] EpS and (h,p) EPn where s < n < i. As shown in (vii a) above, dom Gn cannot contain the xEGS- n-l dom Gs ~hp]) _ -~~j_=s+l (hapj with large values of xp (small values of xq), and the dominion via [h,k3 o Gi of all such x equals dom G o But dom G may contain some such x but not (h,k) (h,qj the corresponding dom x. So some imputations that were previously in (h,k) i-1 i-i -o i dom K or dom K may now be left undominated by G UK i-dom Gi (h;k) [h,p} The result may be that dom Ki'l dom (GiUKi-1 _ dom Gi ) in which case we must find the Ki ' in equation (11). This situation 1 for a given h is shown in Figures 11, 12, and 13, which picture A, An and A' respectively. In these figures, the heavy lines show the region that contains (but is not necessarily equal to) GiUK i —dom Gi' the light broken lines show the region J(h) that contains the undominated imputations, and the heavy broken lines show the additional part K (h) 1

A1 J(h) AAl / \, X k x = v (fhk) Fiur 11. EXk Xh + xq = "({hrq). xh + xk = v((h,k)) Figure 11. Exceptional Case on As.

46 J(h) nn Xh + Xp ((hpt)) K(hn LI Xh +HUW Xq xh + sxl Y((h,q) xh + xk' ((h,k)) n Figure 12. Exceptional Case on A

47 A' *xq x v((hq) 113.r EXceptiona. aeo -i — I C On -

48 of the solution for the given ho J(h) and K (h) will meet the other simplices Aj(j / s,n, nor i) in similar regions. Then the union of all i i such K (h) that occur at the ith step of our induction gives the K in 1 1 equation (11). In order to describe J(h) analytically, we introduce the following notation. On each Ai there is the line segment Lj= IxAj lXk + xh = v([k,h)),xp + xh = v([(p,h] )+ And let x* = ma lx xG and x + x <v((q,h)) q q q h On each Ai consider the point where xq = x meets L These points have coordinates xJ JPJ - x* - v((k,h}) p xj = x q q xJ = Pi: J - x* - v((p,h)) Xj x* + v([(p,h) + v((k hi) - IPj / Note that xq < Pi -v( (p,h ), that is where xp+xh = v( (p,h) meets xk = Con Ai. Assume x* exists, because Ei- An ixIxq+xh< v((cq,h}j is closed and if it is empty, then dom G = 5 and so J(h) = Also assume (q,h} x* > O for if not, then dom G = ( and we are again back in the case q t[,h}

49 (vii a) of the last section. And we can assume that the points xj are on Aj For if x x* does not meet L on A, then either v( (k,h) or q q v( p,hJ) is negative and the corresponding domination does not enter and so we are in case (vii a), or v((k,bh) > IP I or v( (p,hJ) > IPnl which is impossible for v((j,h]) < Fp((k,h])+Fp((p])+ Fp(([q) < IPSI where P = [(p), (q3, (k,hj, or x* is too small for dom G to contain (q,h n-l the (k,h]-effective imputations in G - U dom G which have xp+xh > j=s+l v( p,h}) and large values of xq and again J(h) = ~ as in (vii a) above. The undominated imputations for the case we are considering are contained in the region J(h) which is bounded as follows. If xcJ(h), then x > xn p - P x >x x = xJ for all j q- q q (13) n xk > Xk, and xk > xk when xk + xh < v( (k,h). n Because if a < x then let S = (p,h) and M = (q,h) in the argument in P P (vii a) and then the coalition (k,hj causes no trouble in finding the a' in (vii a). See the Figures. And, if ak < xk and ak+ah > v((k,h)) then let S = (p,h} and M = (q,h) in (vii a) and then the coalition (k,h} causes no trouble in finding the a' in (vii a)o Also, if ak < x(> xk)

50 and ak+ah < v((k,h}), then the coalition [q,h] causes no trouble in finding a' in (vii a). To show xq > x* assume that Xp+Xh < v((p,hj) or Xk+xh < ((k,hJ) for if not then xi dom GS U dom Gn so that x is not [(kh (p,h} in the undominated area mentioned in the first paragraph of this sectiono So if xj+xh< v((j,hl) for j = p or k and xq < x* = xq, then m i Xh < v( (j,h))-xj < v( [j,h)-xj < v( (p, h3)-xp = xh (where m=n if j = p ii and m = s if j = k), and so xE dom x C dom G Thus x is not an undom(q,h) (qh) inated imputation. Before describing the additional part Ki(h) that needs to be added in J(h) in order to have a solution in this part, we will discuss which coalitions M satisfy the conditions M is in a partition P with IPi > IP,i and (14) M is effective in some part of J(h). For the other coalitions will not have to be considered in finding i i-i i K (h). Note that if E nA =, then we already have a solution for all of R before the ith step in the induction, so assume E iA # o Clearly, N/P if IPI > IPi I and Eil nAi 0.o Also, if (p,q) or (q,kJ are in a P with IPI > IP I and E nA', 0, then v(ip,qJ)+v((k,h)) < Pi I or v((q,k})+v((p,h}) < Ipil. (See Lemma 3.) I xcJ(h), then xp+Xq Xp+xq = -Xk-Xh = Pnl-v((k,h) = pi i -v((k,h]) > hPi > -v((khJ) > v([p,q]) where Ani = IPn -IP I, and so x is (p,q)- ineffectiveo If xcJ(h), then Xq+xk + x> = IP |-x -xh = P |-v((ph])>

51 Pi I-v( Ip,h]) > v( (q,kj), and so x is [q,k]-ineffectiveo Next, note that if (p,kjcP with IPI > IPi, then ac Ei-l Ai has, a. = Pi I jcN i i i and a +ak > v([p,k)o. Then x has x +xk > v( (p,kJ)o So if xcJ(h), we p k- p k get Xp+Xk > xn+xn > xp+x > v((p,k}), and so x is (p,k]-ineffectiveo Also, if (p,q,kJcP with IPI > pi |s then acEi lDAi has a. = jeN i i i i and a +a +ak > v( (p,q,k ). Then x has x +x+Xk > v( (pnq,k3). So if xcJ(h), then xp+xq+xk > xnxn+ > xi+xi+xi > v( p,q,k3), and so x is (pq,k3-ineffectiveo In summary, if N, (p,q}, (q,kJ, (p,k} or (p,q,k} are in a P with P I > jPi I, then they are ineffective in J(h)o The Ki(h) that we will describe in the next paragraph will have K (h) nAj = 0 for all j > n. So in determining Kl(h), only domination via (k,hJ, (p,h), (q,k,h], (p,k,hJ and [p,q,h) need be considered. We now describe how to get the additional part Kl(h) of the solution in J( h), We proceed to take maximal elements in successive A j]J'(h) as we did before in the A where j = 1l2,7-. The verification then of the following assertions is similar to the corresponding results done in Sections 3 and 4. First, K (h) = G (h) = E [A n J(h) is a solution on (J(h) OAl) U(J(h)-El)o Second, let G2(h) be the elements in ElnA2n J(h) that are maximal with respect to dom where M2is the coalition in P2 that can be effective in j(h)o There is only one such M2 by the preceeding paragraph. Then K2(h) = G2(h)U K'(h)-dom G2 (h) is a solution for [J(h) O(AUA2) ]U[J(h)-E ]. Continuing, let G (h) be

the elements in Ej-1 lAJ J(h) that are maximal with respect to dom. where MJ Mj:Pj may be effective in J(h). Then KJ(h) = GJ(h)UKJ-l(h)-dom GJ(h) is a solution for [J(h)n (AU...UAj)]U [J(h)-Ej]. Pick the first t such that J(h)C(A1 o...o LA ) j(J(h)-E ). Then Kl(h) = K (h) is a solution in J(h). The above process terminates for some t < n. Because if xcAj lOJ(h) for j > n, then Xu = IPJ < IP l and Xp+Xq > xn+xn and ~ = X.J~ ~p qa u~N s -x n-xn< P n n w so Xk+xh< |P xxpn- <P -xp x = v((k,h)). But such x are in dom K (h) for some w < s. Since t < n < i, the exceptional case (vii b) that we i are discussing in this section will never occur in finding K (h). The i s n i heavy broken lines in Figures 11, 12 and 13 show K] (h) on A A and A for the case where domination via (q,k,h}, (p,k,hj and (p,q,h} do not i enter in determining Kl(h), for example, if they are all in a P with IP! < IPn-, i i The K1 in equation (11) is the union of all such Kl(h) that may come in at the ith step of our induction, that is, = U Ki(h) 1 1 h i s n i iwhere (h,q] P, (h,kj eP and (h,p] eP for s < n < i. Since G LK -dom G was the desired solution for all but part of the J(h) regions and the K_ (h) are solutions in these regions, it follows that K Udom K = R.o

53 To prove that K ndomK = it is sufficient to prove that (15) Kl(h) ndom (GiU Ki- - dom Gi) = (16) (G1 U K - dom G ) ndom K1 (h) = and (17) K (h) ndom K (h') for.the four possible non empty J(h) and J(h') regions. We can prove these equations by again considering several cases described in the following. First, to prove (15), we need to show that i i i-1 i (15r) Kl(h) ndom (G UK - dom G ) = M for all M in a P with IPI > IP1 I. From (14) above if M = N, (q,kj, (p,k), (p,q} or (p,q,k} and MeP with IPI > IPi I then M is ineffective in J(h) so (15') is true for such M. From the definition of x*, (15') holds for M = (q,h}. (15') holds for M = (p,h} and (q,h} because J(h) was determined by the elements not in dom (GiU Ki-l-dom Gi) for M o p~~t ~i-1 i = [p,h] and (qhj. If M = (p,k,h] EP for some t < i, then x E E (A has Xp+Xk+Xh > v((p,k,hJ) and so x[ < iPi -v([p,k,h))< IPtl-v((p,k,h]),

54 and so if a is M-effective and realizable, then aq > x*. In this case, t t-1 t the set G (h) of maximal elements in E nA n J(h) with respect to dom is contained in the previously obtained set Gt of maximal elements (p,k,h) t-l t t t t t in E nA and dom G fn(K U[Et n(At Uo UA15)]) = Since K i t t t i t -dom G U[Et (A U UA15 )] and dom Kl(h)= dom G (h), we have (p,k,h) (p,k,h} (15') for M = (p,k,h>. If M = (p,q,h] ePj and j < i, then consider the two cases j < n and j > no If j < n define the points zJcAj which satisfy the equations Xk+xh = v((k,hJ), Xp+Xh v((phJ), Xp+Xq+Xh = v([pqh) and XU = IPJ. Then it is easy to show that, if z ucN x*, then we are in a case similar to (vii a), and if z < x* we are q q- q' in a case similar to M = (p,k,h) that is done just above. In the case j > n, if x.eGj and x is M-effective, then xp+xh > v( (p,h.) or xq+Xk < Pj I-v( (ph3), and if aJ(h), then aq+agk > x q+xk > P I-v((p,h)) > IPj -v((p,h}), and so x dom a is impossible~ This proves (15') for M = (p,q,ho. Replace p by k in this last argument and we get (15') for M = (q,k,h}o This proves equation (15). Next,to prove (16), we need to show (16') (GiUKi- dom Gi) ndom Kl(h) = M for all Mc-Pj for j < no By the paragraph containing equation (14), we then have dom Kl(h) = ~ for M = N, [p,q), (p,k), (q,k) and (p,q,k) since M

55 such M are ineffective in J(h). Also, dom Kl(h) = X for (q,h] is (q,h} first realized on A and i > no The remaining M that have to be considered all contain h and have their domination cones away from the xh vertex and toward xh = 0. But it is easy to see that in taking the successive maximal elements Gt(h) (t < n) in Et-l nAtn J(h) in the process of obtaining KI(h) that Gt(h) is contained in the previous maximal elements Gt in Et-1 nAt which were obtained in the process leading to Gi UKi''-dom G, with the only possible exception being the last non empty G (h) (u < n)o Since G JK-l-dom G CKtU [Et n(At+l U. UA15) ] t t t t dom G (h)Cdom G, dom Kl(h) = dom G (h) and dom G 0(Kt U[Et(At+ l o.. NMt 1i t A5) ])= I, we get dom Gt(h) n(GiU Kil-_ dom Gi) = 0 for all G (h) but the exceptional case Gu(h), By considering cases of all the remaining M, we can show that the elements in GU(h) are either in Gu or are "less maximal" than those in GU and so also dom Gu(h) f(GiU Ki-1-dom Gi) = Mu Tihis proves (16), Finally, to prove (17), we need (17') Kl(h)F dom K1 (h') - M for all M. But the boundaries of the regions J(h) or J(h') are determined by equations like (13) which are related by the definitions of the xj and Lj to the v(M) for certain two element coalitions M containing h or h' On the Aj with AJIEj-1 / I, that is, on the Aj with Aj nKj / I,

56 Lemma 5 separates the regions on Al U1.. UA on which complimentary two element coalitions can be effective, and using equation (13) thus separates the regions J(h) and J(h')o And by considering cases of the few remaining M that are effective in both J(h) and J(h'), it is easy to see that J(h) and dom J(h') are also separated by certain of the x M +xn = v((m,n)) planes, and so K1(h) n dom K1 (h') = (. This proves (17) and completes the discussion of the exceptional case (vii b). 6, REMARKS Our process for finding K terminates at the first Kf where EfnAf+l =, for example if Pf = (N) or if IPf+l1 < 0. Also note that a two player coalition M can be realized on the two possible Ai which are obtained from the corresponding partitions of type (2,2) or (2,1,1). It is clear in our process of taking successive maximal elements that we need only consider domination via M off the Aj with the higher IPj 1o From these remarks, it is clear, that for our solution K obtained above to hold, condition (10) about distinct imputation simplices AJ need not be satisfied by all Aio The simplices AJ need not be distinct for the partitions Pi that have Pj < 0, I < Pf I or Pj < IPf o where P = (N), or even when these conditions are not true but Ai is realized only by some of the partitions ((p,q), (k,h)J, ((p], (qi, (kh)} and ((pq], (kj, (h)]. Also, certain Aj need not be distinct if the v(M) for the M realizable on this Aj are small enrough so that the corresponding M-strictly effective regions on Aj are disjoint.

57 Our method of obtaining the solution K is constructive. From Lemma 4 and the fact that the dominion of a polyhedron is a polyhedron, we get that K is polyhedral. It is also conjectured that K is the unique solution but this has not been proved. In games in partition function form with distinct imputation simplices, the solutions obtained so far are not of the discriminatory nature and do not contain the bargaining curves that appear in the von Neumnann-Morgenstern theory

CHAPTER 4 n-PERSON GAMES WITH ONLY (n), (n-l,l) AND (1,1,.o o1) TYPE PARTITIONS 1. INTRODUCTION In this chapter, we will give some solutions for the n-person games where only partitions of the type (n), (n-l,l) and (1,1,... 1) enter into the problem. These games are a direct generalization of the 3-person games and thus the notation of this chapter will be similar to that of Chapter 2. The set of players is N = (1,..,nj, Consider the following partitions of N. 0 P- = (N} =l (N - (i}, (i}} i = 1,2,ooo n Pil = ((1}, (2}oo (n}} Q = (Q1o ~ o,Qt) = any other partition of N. Assume each partition P has an outcome function Fp defined on it, and let FpO(N) = c Fpi( (i)) = di, Fpi(N-[i}) = ei 58

59 Fpn+l (i) = gi i = 1,2,.,n. Also let Ci = ei + di = 2 n g g 1 + g2 + + In this chapter, we will consider games that have t (18) IQI = FQ(Qi) < max(O,c) i=1 for all Q pi (i = 0 1,2,..oo or n+l).o From assumption (18) and Theorems 1, 2 and 4 in Chapter 1, we need only consider the partitions i 0 P (i = 0,1,2,...,n) in discussing solutions, and P is only used to determine which pi(i = 1,. o,n) have IPi! > CIP0 = CO Assuming our games in normal form under S-equivalence (Section 4 of Chapter 1) gives di > O ei < ci gi > 0 g > 0. And by equation (1), the values of the coalitions used to find a solution K then are v(N) = c v(N - (i) = ei v((i}) = vi = 0o

6o For N-(i3 to be effective means that x.j < e or equivalently that -i xi > di where we use -i to mean that the sum is over all jcN-[i3o And an imputation x is realized by N-(i) only if xEA(ci). 2, THE CONSTANT SUM CASE Consider the case (19) c1 = C2 = o.. = cn. First, if cl < c, then A(c)L [A(g)-dom A(c)] is the unique solution by N Theorems 3 and 4, So we will assume that cl > c. Next, if cl < 0 or cl = 0, then the unique solution is A(g) or A(g)U ((0,0,o..,0)) respecttivelyo So we will further assume that cl > 0. Finally, a solution K for A(cl) can then be extended to a solution for all of R by Theorems 2 and 4, Therefore, we will only consider solutions K for A(cl) where cl > c and cl > 0. Theorem 9. A solution for the case given in (19) is [n/2] K = J (xcA(cl) Ixp > dp, p = il. i2o*oi2er; r=0 crr Xq < dq, q = i2r+l, i2r+2,.. in; i - is = xi -dis s = 2,4,...,2r) where [n/2] is the greatest integer in n/2 and each inner union is taken over the n' permutations or = (il, i2,9oo, in) of (1,2,.o,n) (n-2r) 'r.'2r which give distinct terms. In other words, aA(cl) is in K if and only if all ap-dp that are

61 positive are equal to each other in pairs. Figures 14 and 15 show K for n = 3 when d > cl and d < cl, respectively. Figure 16 shows je~N jcN K for n = 4 and d* < ci. For r = O, we get the term j N C = (xeA(cl) Ixq < dq, q =1,2,. n which is the core. For r = [n/2], we get the term K[n/2] = i) (xcA(cl)xp >dp, p = i, i2,...,i2[n/2]; Ln~/J i ni[n/2 -P Xin < di if n is odd; x - di xi - di. s = 2,4,...,2[n/2]). Let Z = (xeA(cl)lxp I> dp, p = 1,2,o..,n Then KZ = K[n/2] nZ is a "translation" of the solution to the (n,k) simple majority games when k = n-1 which was given by Bott in [1]. So cur solution K is the natural generalization of Bott's solution when k = n-l. Note that if X dj < cl, then C = 96 and Z f 9, and if jeN C dj > cl, then C f 9 and Z = 9, and if X dj = cl, then C = Z = jcN jEN ((da9 d2a..,dn)}o Geometrically, we have a simple game in the interior part Z of A(cl) and n truncated pyramid games (see page 81 of [7]) in the regions Sh = [xeA(cl) Xh < dh) which extend off each of the faces of Z. A

A(o2) x2 d2 x3 = d3 (o,o,o) (o,e,~ Figure 14. Solution for n = 3 and C ~ A. (0,0 cl) X1= d X2- d2 K z\ x= d3 / (,o0,0) (Os Figure 15. Solution for n = 3 and Z f 9.

63 (o,c,,o,o) A(/q) (0,0,0,0,l) 3 X3 = d3 =4 4 d m Figure 16. Solution for n = 4 and Z f a.

64 trace, xh = constant, in Sh gives an (n-l)-person game of the type being considered and this trace of K is the corresponding solution for this new game. In Z, the solution K is symmetric with respect to all permutations of the xi-di. In Sh, the solution K is symmetric with respect to all permutations of xi-di with i / h. Note that if Z 0 0, the dimension of K is smallest in the interior part Z of A(cl) and the dimension increases as one goes more toward the exterior parts, that is, as more Xi < di, The following two lemmas are useful in the proof of the theorem. Lemma 6. If X1 X2 = X2 = X2t-1 X2t = X2t+l X2m = X1 A ~V V V V V o V Y1 = Y2 Y3 = Y2t-1 = Y2t Yst+1 = = Y2m and X2m+j > Yam+j for j = 1,2, o,n-2m, then xi 1 i =1 Proof,; Observe that X2t > Y2t t = 1,2,o..,m X2t+1 = X2t > Y2t = Y2t-1 t = 1,2,...,m-l X1 = X2m> Ym = Y2m -1 X2m+j > Yam+j j = 1,2,..n-2mo Summing over all these gives the desired result.

Lemma 7. If 0 < X1 X X = 2 = X2t-1 X2t = X2t+1 = X2m+1 //\ V',/ / V V V Y1 = Y2 Y3 = Y2t-1 = Y2t Y2t+1 = Y2m+1 < 0 and X2m+l+j > Y2m+l+j for j = 1,2,...,n-2m-1, then n n xi > Yi i=l i=l Proof. Observe that X2t > Y2t t = 1,2,..,m X2t+l = X2t > Y2t = Y2t-1 t = 1,2,..,m-1 X1 > 0 > Y2m+l X2m+l+j > Y2m+l+j j = 1,2, o. n-2m-1. Summing over all these gives the desired result. Proof of the theorem. First, we prove Kndom K = 9. Since KNdom K = [(K-C)UC] ndom['(K-C) UC] = [(K-C) ndom(K-C)][J [(K-C) ndom C] U [C Qdom K], it is sufficient to prove that (20) K ndom C = 9 (21) C ndom K = 9, and (22) (K-C)F)dom (K-C) = 9.

66 If (20) fails, then there exists aEC and beK such a dom b for some -k kEN. Since N-(k) is effective, aj = V bj and ai > bi for all i / k, jCN jCN we get dk < ak< bk which implies bC. Since aeC, we also get bi < ai < di for i / k. It follows that b has exactly one coordinate with b. > d. (j — j J = k) which then implies bK-C. Thus b_/K which is a contradiction. If (21) fails, then there exists aeK and beC such that a dom b. -k Since a bj ai > bi for all i / k, and N-(k} is effective jeN jeN we get bk > ak > dk. This implies bjC, which is a contradiction. Assume that (22) fails. Then there exists a,beK-C such that a dom b. Since LbC there exists an i such that bi-di > 0O But bcK-C im-k plies that all bi-di that are positive are equal to each other in pairs. So after permuting the subscripts, we can assume b is of the form bs_l - ds-1 = bs - ds > 0, s = 2,4,..,2r b. < d. j = 2r+l, 2r+2,..,n where r > 1. a is N[(k} effective, so dk < ak < bk, which implies kc(1,2, ooo,2ro Thus we can take distinct k, i2, i3,o*.. i2m+lC (1,2,,..,2r] such that o<a dk ai - di = a - d Oaki2 1 i 2m '1m 2r= 2m+1 2m+i / V V v bk dk -d = bi d b - di 2 2 2m 2m 2m+1 2m+1

where eventually either (i) i2m+1 = k(in which case disregard the ">" in the last term), or (ii) bi - di < ~ 2m+1 2m+1 In cases (i) and (ii), Lemmas 6 and 7, respectively, imply that n n n n (a-di) > (b-di) or ai > bi, which is a contradiction i=l i=l i=l i=l and (22) follows. This completes the proof that K ndom K = A. It remains for us to prove that KU dom K = A(cl). Assume that bcA(cl)-K. Since /CCK, there exists i such that bi-di > 0. Also, there exists k such that 0 < bk-dk / bj-dj for an odd number of j / k, because if all such positive b.-d. could be set equal in pairs, then beK-C, By permuting subscripts, we can assume that the components of b-d are ordered as b. - d > b - dj j = 1,2. n-1 j j- j+l j+l bk - dk > 0 (23) bk - dk > bk+l - dk+l bq -d >O >b - d+l where k is odd and k < q. The following three cases will be considered.

(i ) q> 3 is odd (ii) q = 1, and (iii) q is even In case (i) let (n-i)cl = (bk-dk) - max(bk+l-dk+l,0) > 0 -(b 4 0) " q+l d+l)> O C = min(El, C2) > 0 (q-1)5 = (bj-dj) - ( q l7b2i-d2i )- (b2i+1-d2i+l)] i =1 - (nl)E > O0 Next define a by al - dl = 0 a2i - d2i a2i+l d2i+l = b2i d2i + E + 5 i 1,2,)/ aj = bj + e j = q+1, q+2.. n. Then aA(cl), because al = dl > 0 and a -di > bi-di implies ai > bi > 0 for all i f 1, and because

69 (q-1)/2 n (ai-di) = 0 + 2 (b2i-d2i) + C (bj-dj) L Z_ icN i=l j=q+l + (q-1)b + (n-l) = (bi-di) and so L ai = bi = cl. And aeK since the positive ai-di are equal iEN ieN in pairs. Also, a dom b, because ai-di > bi-di for all i 1, and al -1 = dl so N-( I is effective. Thus bc dom K. If one had to permute the subscripts of the components of b-d to get it in form (23), then the inverse permutation will get the corresponding a which is clearly still in K. This completes the proof of (i). Now, consider case (ii) where q = 1. Then define a by al - dl = 0 a2 - d2 = b2 - d2 + ~ + 52 a3 - d3 = b3 - d3 + e + 53 aj = bj + E j = 4,5,o.,n where c is the same as in case (i) and 32 and 63 are defined by 62 + 63 = (bl-d1) - (n-l)c > 0, and a2 - d2 = a3 - d3 if 62 + 63 > (b2-d2) - (b3-d3), or

7o E2 = O if t2 + 53 < (b2-d2) - (b3-d3). Then aeA(cl), because al = dl > 0 and ai-di > bi-di implies ai > b > 0 for all i / 1, and because n (ai-di) = (bi-di) + (n-l)E + (bl-dl) - (n-l)E iN i =2 = X (bi- di). iCeN And acK since a2-d2 and a3-d3 are either equal or non positive and all other a. -d. < 0 Also a dom b. Thus be dom K. -1 In case (iii) where q is even, let nc = ( bk-dk) - (bk+l-dk+l) >0 ~E = (bq+l-dq+l) > c: = min(E1, E2) > 0 (q-1)/2 25 = (bl-d)) [ (b2. -d2i) - (b2i+l-d2i+ ) ] 1i= - nc > 00 And define a by al -dl = aq - dq = bq -dq + c + a2i - d2i = aai+l - dai+l

71 b2i - d2i + i = a: = bj + E j = q+l, q+2,...,n. Then aEA(cl), because clearly ai > 0, and because 2 n.. / (ai-di) = 2 (b2i-d2i) + (bj-dj)+ nc + 26 i N i=l j=q+l =-7^ (bi-di)5 isN And aeK since the positive ai-di are equal in pairs. Also, a dom b, -1 because al-dl = aq-dq > 0 so a is N-(l) effective and ai-di > bi-di for all i / 1. So again bEdom K, which proves (iii). This completes the proof that K Udom K = A(cl), Thus the theorem is proved. 3 THE DISTINCT SIMPLICES CASE We will now consider the case cl > c2 >,.. > cm > c where m < n, and (24) c > cm+j for j = 1,...,n-m if m < n. In this case, the imputation simplices A(cj) (j = 1,2,...,m) are distinct and there is a unique solution K which is given in the following theorem. As before, we will not describe the parts of the solution on A(c) and A(g). For n = 3 and m = 1, 2 and 3, we get the solutions in Genus 1, Genus 2A and Genus 3A, respectively, given in Section 2 of Chapter 2.

72 Theorem 10. The unique solution for any game satisfying (18) and (24) is m m K = A(ci) - Jxl Xk < ej; xp < dp-Apj, p = 1,.,j 1=1 1 j i=l j= - j m Proofo First, we must show that K Udom K = A(c )o But it is j=1 J easy to show, that except for one case, that Vj = cA(c) xk = ej; -j Xp < dp-Apj p = l,.,j-l is contained in K and dom VjD x /xk < e j; -J -J p < d -Apj p = 1,...,j-1 where j = 1, o...,m The exceptional case occurs when j = m = n and J di < cn because then V = 0. But in this i~N n-l case, Vo U ([xeA(cn) Jxp = dp-Apn; xq < dq-Aqn, q = l, oo,n-1] is conp=l tained in K and dom V D x xk < en; xp < dp-Apn p = 1, n-n Thus dom K will contain all those imputations that were subtracted from A.A(c ) to obtain K. In fact, we only need to dominate with those j=l J imputations in K that are exactly effective except for the exceptional case. Next, we must prove that K dom K = 0. Let xcK be N-(j} effective and realizable. Then xcKN I xl xk < ej nA(cj), that is, xK, x. > d. — j and, xi = cjo From our definition of K, it is then clear that icoN xp < dp-Apj for p = 1,.oo, and j-l, and Lxk < e. Such xcan only -j

dominate via N-(j3 those z with zp < dp-Apj for p = 1,...,j-l, and Yp p L Zk < e j But from the definition of K, such JzK. This proves that -j Kn dom K = X for j = l,..,m, which is sufficient for K dom K = -j Therefore, K is a solution. Finally, we will prove that K is the unique solution by showing m that an imputation in lA(ci)-K cannot be in any solution K'. Let ac xk < e, that is, consider the term j = 1 in the equation -1 above for K. The proof that a is not in any solution K' is similar to the proof of Theorem 5 except that the set (2,5) is replaced by (2,3,..,n and so we omit it. But now we will give the proof for an arbitrary j, that is, we will prove that if a is in Di =.-x| 7 xk < ej; Xp < dp-Apj, = l,....,j-l then a cannot be in any solution K'o Assume that 0 < e < cj, for if e. < O, then there is nothing to prove, and define Br = cDj nA(cj) j xk < dr -j r where d = min(ej, rAjj_ 1 and Apq = Cp-cqo We will show that BaCK' Udom K'. Since K' is a solution, -j B CK' Udom K'. But from (18), (24) and Theorem 1, we get that Blndom K' = X unless M = N-(j) where j = l,o.om. But Br dom K' M -k

74 when k < j because if acB CD then ak < dk-Akj and so ai = cj -k -ak > cj-dk+Akj = Ck-d k = ek = v(N-(k)) and thus a is ineffective for N-k.), And B1 ndom K' = ' when m > k > j; because if aeBL and the -k intersection is non empty, then there exists bc K' nA(ck) such that -k b dom a which implies that C bi > bj > aj > ej-dl > cj-nj:j+l icN = c+1 > ck which says that b is not realized by N-(k] and thus contradicts b dom ao Therefore B lndom K' = ~ when k / j, and B'CK'Udom K'. -k -k -j Then, it is clear that D xJ xk < d' Cdom Bitdom K' and so -_ _j -j D fl x xk K d= K' = If d, 'then we have proved the unique-J ness part of our theorem. 1 1 I If d < ej, then d = A,j+ and k < Aj l K' =. So _j if bK'A(Ck), then bi > Aj,j+l and bj < ck-Ajj+l. Now we canr. -j show that B2CK'Udom K'. Because BeNdom K' = 5 when k < j, since -j -k if a B CD, then a is ineffective for N-(k] as proved in the paragraph above. And because B2 Mdom K' = ~ when m > k > j, since if not then there exists acB2 and beK' nA(ck) such that b dom a which -k implies that bj > aj = cj-> j d- > I -+1 -j -j

k-bj Ck-c+2,j+ l = Akj+2Aj,j+l < Aj,+1 which is a contradiction. Therefore, B2CK'Udom K'. Next, it is then clear that Djf x xk -j 2 2 J 2 < d QCdom B Cdom K' and so Din l Xk < d2 K' = If d2 ej, -j -0 -j thllen we have proved the uniqueness part of our theorem. If d2 < ej, then we continue as above to get BrCK' Udom K' for r -j = 3,4,..,r0 where finally d = ejo Then DJ ni xk < d = ej = -j J DjCdom BrOCdom K'. So Dj K' = n. Since j = 1, or m, this proves -j -j the uniquenriess of the solution K, and completes the proof of Theorem 10. 4, A SEPARATION THEOREM The following separation theorem will be used in the next section to show that for each strict inequality cq > cq+l in cl > c2 > o > m Cm > c we can partition UA(ci) into three parts. The first part is contained in every solutionO In the second. part, only domination via N-(j] (j = 1,.o*,q) need be considered in finding any solution. And in the third part, only domination via N- j (j = q+l,.,m) need be considered in finding any solution. Theorem 11. If c > > c > > ooo > C > c m+j for j = 1,..,,n-m, and K is any solution for a game satisfying (18), then xlxj > dj - Aj,q+l, j = i,o o o, or q] ndom K = -i

for i = q+l,..,m, and where again Akp = Ck-cpo Proof. Let Di = (xEA(ci)xj > dj - j,q+l for j = 1,..., or q]. We will first show that D nK = ( when i = q+l,..., and mo For let aED, that is, aEA(ci) and aj > dj-Aj,q+l for j = l,..o, or q, and then ak = ci-aj Cj-A ji-dj+Ajq+l ej = v(N-([j)o Then define b by bk -j = ak+ for all k f j and bj = aj+Aj,q+l-(n-1)c where ne = min j- ak, _-j Aj q+1 > O~ And then b > a and b dom a, because e and Aj,q+l-(n-l1) N -j > 0, bk = ak+(n-l)c < ej = v(N-(j ), and bp = ap+Aj,q+l -j -j peN peN = c. But bzK Udom K. If bcK, then a~ dom bCdom Ko If be dom K, then -j ac dom K by Lemma lo In either case, aiK, and therefore D fK = 0 when i - q+l,o o, and m. That is, if bcA(ci) ]K (i = q+l,.o, or m), then bj < dj- Ajq+l for j,o o o and qo So if xc dom K for i = q+l,,~. or m, then xj < dj-Ajq+l for j = 1,., and q. This completes the proof of the theorem. 5. INTERMEDIATE CASES We will now summarize some partial results for -those remaining games that are intermediate to the constant sum case of Section 2 and the distinct simplices case of Section 3G Thus, in addition to (18)

77 we will assume that cl.. = Cr > 1 Cr +> 1 ~~'cr cr+ Cr > > Cr +1 1 1 2 - - o.= Crq (25) > c > Cr +j for j = 1, n-r We will let rq = m as in previous usage. The solutions obtained so far for such games are closely related to those in Sections 2 and 3, As usual, we will not discuss that part of the solutions on A(c) and A(g). As a result of Theorem 11, we get that for each cri > cri+l in m (25) there is a partitioning of V = jUlA(cj) into the polyhedrons r -j Ti = V xi < ej for j = or r I Fi. = x. e- for j = 1,., and ri; Xk > dk - Ak,ri+l for k = 1., or ri and Li = x iV Xi > ej for j = 1,. o, and ri; -j Xk < dk - Akri+l for k = 1, oand ri We also define F0 to be those elements undominated via all N-(ij, FO = (xcVlxj < dj for j = l,o oo, and n}, that is, F0 is the core if the values of all coalitions with less than

78 n-l players are non positive. In Ti any imputation is N-(j3 strictly effective for j = 1,. o., or ri; and from Theorem 11, no imputation in ri TiQn UA(cj) is in dom K for k = ri+l,...,m where K is any solution. j=l -k It is also clear from Theorem 11 that Fi is contained in any K for q i = 0,1,..o, and q. (But in general F = J Fj need not contain the j=O intersection of all solutions even when m = n. ) And in Li, only domination via N- k) for k = ri+l,o,m need be considered in finding K. To find a solution K for a game satisfying (25), we consider K in different parts of Vo First, we give a solution for T1UFo Consider the solution given in Theorem 9 for the constant sum case when dk > ck (that is ek _< 0) for k=rl+l,1 o., and n. Let K0 be this solution intersected with T1. Then KO UF will be a solution for T1UF where in TiUF we only consider domination off of KO JF via N- ( j for j = 1,.o, and rl. Second, let us assume that we can find a solution FUKq_1 in F jLq_1 for all those games where the rql1 in the definition of Lql could be 1,2,,m-lo In doing this, the case where m < n follows easily from the case where m = n and cm = cm+l = o o = cn by setting dm+1 = ooo = dn = cmo That is, we can assume that rq = m = no Third, we can then get a solution for the F Uj(Ti-Til) by taking F[U(Kq_ 0T i_) when i = q-l and dk > ck for k = rq ltl,1.,n where only domination via N-(j} for j = ri_l+l,o o,r need be considered. Therefore, the problem reduces to finding a solution FUKq_1 in F ULq_1 where rql1 = 1,2o.oo and n-l1

79 The problem of finding a solution in F JL can be reduced someq-l what as follows. If K is any solution in V, then Lq_l fldom K = e' unless -k k = rql+l,., or n. But the only imputations in Lq_1 that are realizable by N-(kj for k = r q+1..., or n are on the imputation simplex A(crq-1+1) = o.. = A(cn). So a solution in (F ULql) nA(cn) can be extended to one in all of F UL 1 by simply adding the undominated imputations in (FUJL _1) A(ci) for i = Io. or1. And it can also be n shown that [J dom F contains exactly those elements in L A1 (c ) k=r +1 -k - q.-1 that are not in W = (xcA(cn) nLqllXj + xk < dj + dk - Aj,rq where j = 1,,. rq_l, k = rq_l+l,...,n] n irJ l xA(cn) nLq-l xk < dk for k = rq_+l1,. o,i,o..,n]. (-1 The subtracted terms in the definition of W are the imputations contained in (F0 Udom FO)0(A(cn) ULq_l). Therefore, our problem of finding a solution for games satisfying (25) reduced to finding a solution in the region W for the cases r = 1,2..., and n-l. Solutions in region W have been found for a large number of games for various values of n and rq l1 including all games witth n < 4 and all games with arbitrary n and r = n-2 and n-lo But few of the results q-1 for small n seem to generalize without some modification~ Work is contirnuing on these remaining problemso

CHAPTER 5 UNSOLVED PROBLEMS There are many conjectures and open questions in the theory of nperson games in partition function form, We will now list some of the more immediate ones for which we are presently seeking answers. In Chapter 3, we gave a solution for each 4-person game that has distinct imputation simpliceso As mentioned there we conjecture that this solution is unique. This could probably be proved in a manner similar to the uniqueness discussion for 3-person games given in Section 3 of Chapter;2 However, such an approach for the 4-person games would involve a large number of cases each involving an inductive proof and thus seems impractical. Hence, we are looking for a more direct or local type proof for uniqueness in the 3-person and 4-person games with distinct imputation simpliceso If successful, then we will try to generalize the treatment to handle n-person games with distinct simplices. Solutions have also been found for all 4-person games in which only partitions of type (4), (3,1) and (1,l,l,l) can have large outcomes (in the sense of equation (18)), Such games are covered in Chapter 4 when n = 4. By using the separation property in Lemma 5 and considering a large number of cases, we can also give solutions for all 4-person games in which only partitions of type (4), (2,2), (2,1,1) and (1,1,1,1) can have large outcomes. In addition solutions have been found for many other 4-person games in which both two and three player coalitions are 80

81 used in the domination. But there are too many games of this latter type to prove the general existence of solutions by just considering cases. Experience to date indicates that there is little difficulty in finding a solution for any given 4-person game by merely combining the methods for the various cases discussed above, but this has not yet been proved. Therefore, work is continuing on the proof of a general existence theorem for all 4-person games. We would like to answer the question of existence of solutions for all of the intermediate type games given in Section 5 of Chapter 4. Solutions in the region W (defined at the end of Chapter 4) are being sought for 5- and 6-person games in hope that some of these solutions will generalize. The solutions found so far in the region W are made up of parts of the solutions given in Section 2 of Chapter 4 (the constant sum case) along with certain maximal elements with respect to domination via certain coalitions N - (ij. Furthermore, the games in Chapter 4 are just a special case (k = 1) of those games in which only partitions of type (n), (n-k,k) and (1,1,..oo,1l) have large outcomes for some given k = 1,2,..., or [n/2], where [n/2] again stands for the greatest integer in n/2. We will attempt to find solutions for such games when k > 1. If successful then we will try to combine the results for various k values in order to get solutions for some games in which partitions of type (n), (n-l,l), (n-2,2),...,(n- n/2][n/2],[n/2]) are significant. Theorem 9 generalizes the solutions given by Bott in [1] when k = 1. Perhaps there are symmetric solutions for the constant sum

82 case when k > 1 which will also generalize the corresponding solutions by Bott when k > 1o The most outstanding problem in the theory is the proof of a general existence theorem for solutions of all n-person games or the demonstration of a counter example. Since Thrall games are a generalization of the von Neumann-Morgenstern games, the solution of this problem would solve the classical case also. More modestly, we will attempt to prove that theIre is a polyhedral solution (perhaps unique) for n-person games when the imputation simplices A(P) corresponding to different partitions P of N are distinct. We hope to obtain the solution in a manner similar to that in Chapter 3 where n = 4. That is, we will take maximal elements with. respect to "dom" on the successive simplices A(P) as the values of |P( decrease; and whenever the maximal elements dominate away too much from a previous solution for part of R, then we repeat the process of taking successive maximal e lements in the undominated parts This process should terminate in a finite number of steps. It is clear from the large number of cases considered in Chapter 3 that a more direct proof will need to be developed when n > 4. We have no example yet in which this process of taking successive maximal elements has not led to a solution for a particular game, but we note that when n > 5 then Lemma 5 fails and when n >6then there can be three non-trivial coali - tions in one partitionO However, if we are successful in our search for a solution in the distinct simplex case, then the results should give some insight into the other games where the simplices are not all dis

83 tinct. It is hoped that this would lead to some finite constructive process for solving the more difficult problem. But the solutions for the latter problem are not just a simple limiting situation of the distinct simplex case. We also remark that, for the von Neumann-Morgenstern games Shapley [4] has conjectured that there exists a solution which is contained in xi xi > v(Pj) for all PjeP where P is an arbitrary icPj partition of N. The corresponding conjecture for Thrall games would be only for any P that has |P| = max ([IQIIQE. This is consistent with our approach of taking successive maximal elements on the A(P), starting with a largest IPI. In Section 4 of Chapter 1 we stated that it is easy to prove that "dom' is preserved under S-equivalence, and thus "dom" and solution sets M are also preserved. It would be of interest to know if the converse is true, that is, whether a one to one map of the imputation spaces of two games which preserves "dom" is an S-equivalence. M Finally, we will just mention some less specific problems of possible interest. Several changes could be made in the basic definitions and assumptions in the Thrall theory to see what effect they have on our present results. iThe experimental work on n-person games could be reviewed in light of this approach, and possible new experiments designed. Additional studies could also be made into the relationship of Thrall's theory to some of the other recent approaches to n-person game theory (for example, see [33).

84 REFERENCES 1. Kuhn, H. W., and Tucker, A. W., editors, Contributions to the Theory of Games, Volume II, Annals of Mathematics Studies, Number 28, Princeton University Press, Princeton, 1953. 2. Luce, RH Duncan, and Raiffa, Howard, Games and Decisions: Introduction and Critical Survey, John Wiley and Sons, Inc., New York, 1957. 3. Maschler, Michael, "The power of a coalition," Econometric Research Program Research Memorandum No, 50, Princeton University, Princeton, 1963. 4. Shapley, L. S., "Open Questions," Dittoed paper presented at Princeton University Conference, 1953. 5. Stearns, R. E., "Three-person cooperative games without side payments," To appear in Annals of Mathematics Studies, Number 52, Princeton University Press, Princeton, 1963. 6. Thral., Ro M., "Generalized characteristic functions for n-person games," Proceedings of the Princeton University Conference of Octobey, 1.961, privately printed for members of the conference, 1962, pp. 157-160. 7. Tucker, A, W,, and Luce, R, D., editors, Contributions to the Theory of Games, Volume IV, Annals of Mathematics Studies, Number 40, Princeton University Press, Princeton, 1959. 8. von Neumann, John, and Morgenstern, Oskar, Theory of Games and Economic Behavior, third edition, Princeton University Press, Princeton, 1955.

UNIVERSITY OF MICHIGAN 3 901 5 03483 7057 3 9015 03483 7057