int. Journal of Game Theory, VoL 7, Issue 2, page 95-112. Physica-Vertag, Vienna.
S o m e T h e o r e m s on the C o r e o f a N o n - S i d e p a y m e n t G a m e w i t h a Measure S p a c e o f Players 1 ) By T. lchiishi, Pittsburgh 2), and Sh. Weber, Jerusalem 3)
Abstract: The present paper studies games without sidepayments in which an arbitrary positive a-finite measure space of players is given. Several necessary and sufficient conditions for nonemptiness of the core, and also a sufficient condition, are obtained for a wide class of games. 1. Introduction The purpose of the present paper is to provide several conditions for non-emptiness of the core of a non-sidepayment game. The point of departure for our investigation is the Fan theorem on a system of linear inequalities [Fan]. It is now widely known that Schmeidler [ 1967], in his study of a sidepayment game with a measurable space of players, established equivalence of non-emptiness of the core and balancedness of the game, and that Kannai [ 1969] observed later that Schmeidler's equivalence theorem can be obtained directly by applying the above Fan theorem. Roughly speaking, the present paper shows that this Fan theorem can also provide a logical basis even for study of non-sidepayment games. This is, indeed, done in two ways as follows: (1) by applying the original Fan theorem repeatedly to a non-sidepayment game; and (2) by generalizing the Fan theorem in the context of vector lattices and then applying the somewhat generalized version to the game. In the main theorems in Section 4 of this paper, necessary and sufficient conditions for non-emptiness of the core are formulated. Little use is made of convexity of the sets, Vs'S of attainable utility allocations, in any of the present theorems. (Compare an equivalence theorem of Billera [1970], in which all Vs's are assumed convex). Besides, the cardinality of the set of players is not assumed finite; an arbitrary o-f'mite positive measure space of players is given to the model. This last point seems to deserve more emphasis from an economist's point of view. In fact, the following discussion has been one of the major motivations for the present study: It is already known that if the game is an atomless market game with a ffmitely 1) This paper was presented at the Fourth International Workshop on Game Theory, CorneU University, June, 1978. 2) Tatsuro lchiishi, Graduate School of Industrial Administration, Carnegie-MeUon University, Pittsburgh, Pa 15213, USA. 3) Shlomo Weber, Institute of Mathematics, Hebrew University, Jerusalem, Israel.
96
T. Iehiishi and Sh. Weber
many types of commodities, then the core is non-empty, since the core is identical to the set of Walras allocations [Aumann, 1964] and there does exist a Walras allocation [Aumann, 1966]. But when there are infinitely many types of commodities in an atomless economy, conditions for non-emptiness of the core have been an open problem, although Bewley [ 1973] has shown equivalence of the core and the set of Walras allocations even for this case. (Existence of a Walras allocation for Bewley's model of an atomless economy has been an open problem.) Analysis of an economic model with infinitely many types of commodities is important, because one can suitably treat future commodities and uncertainty within its framework. Also important is analysis of an economic model with an atomless measure space of agents, as was emphasized in Aumann [1966]. Now, if the study in one direction (i.e., to deduce informations on the core from inforrnations on Walras allocations) is hard because of difficulties with Walras allocations, then one should try the other direction, (the core =~Walras allocations). The above equivalence theorems ofAumann [ 1964] andBewley [ 1973] are powerful enough to justify this. Recall that non-sidepayment games are sufficiently general to describe cooperative behaviour in market economies, regardless whether there are finitely or infinitely many types of commodities. Theorems of the present paper, therefore, provide not only an insight into the structure of a solution concept (i.e., the core) of cooperative games, but also a new way to characterize the Walras allocations of atomless economies even if there are infinitely many types of commodities. A brief ,'liscussion on the core literature is given in Section 6 of this paper. Basic mathematical tools used in the present paper are those of topological vector spaces. Some terminology and theorems are collected in the Appendix.
2. Notation and the Model Let (M, m,/a) be a measure space, fixed throughout the present paper. M is a set, /a is a positive measure defined on M, m is a family of all/a-measurable subsets of M. The measure # is assumed to be o-finite, i.e., there exists a sequence of pairwise disjoint measurable sets El, E2 . . . . . E n , . . . such that
U E n = M and/a (En) < ~' for each n = 1,2 . . . . Clearly, the sequence satisfying n=l
these conditions is not unique but we shall fix it throughout this paper. In our interpretation, M is the set of players, rn is the family of all feasible coalitions and/a (S) is the fraction of the totality of players belonging to the coalition S. Denote by L the family of all equivalence classes of #-essentially bounded measurable scalar functions on M, where two functions are equivalent if their difference is a /a-null function. A member [u] in L~ is interpreted as a utility allocation as follows. Take a generic function u in the class [u]; then the player m enjoys his utility level u (m),/a -- a.e. in M. (L o, II II~ ) is, therefore, the Banach space of utility allocations. When no confusion may arise, a function u and its equivalence class [u] are not distinguished in the present paper, and L is regarded simply as a function space. This helps to avoid unnecessarily complicated wording.
Some Theorems on the Core of a Non-Sidepayment Game
97
Denote by L 1 the family of g-integrable scalar functions on M. Note that L 1 can be regarded as a family of all continuous linear functionals on L , when L is endowed with a suitable topology. Two sets are called equivalent if their symmetric difference is negligible. Denote by rnu the family of all such equivalence classes of members in m. A coalition S E m and its equivalence class [S] E rn# are not distinguished either in the present paper, when no confusion is likely to arise. For each S E m (or more pricely, for each ,~ [S] E rn~) denote by L ~. (S) the subspace ([u] E L I u (m) = 0,/a -- a.e. inM kS). Denote also byL1 (S) the subspace ([u] EL1 l u (m) = 0,/a -- a.e. i n M \ S ) . Denote also b y L l (S) the subspace ([u] E L t I u (m) = 0,/a -- a.e. i n M \ S } . Note that by [ul > u2 (ul = u2, u l / > u2, resp.)] we mean [ul ( m ) > u 2 (m)(ul (m) = s s S = u2 (m), u 1 (m) i> u2 (m), resp.) for # - a.e. in S] where u l, u% E L ~ , and if u E L then ul S means its restrictions to S. Now let us define two topologies, which shall be used in the paper. 1. For each S E m denote by PS the topology on L (S) such that for each ul, u2 E L . (S) withul > u 2 the sets (u E L (S) l ul > u > u 2 ) are open. S S S 2. By o (Lo~, L 1) we shall denote the weak topotogy on L ~ , which is generated by the space L1, where L I is regarded as a subspace of the conjugate space o f L (34). Now with each coalition S a set V (S) C L (S) is associated. The set V (S) can be interpreted as the set of possible utility levels that can be obtained by that coalition without outside help. We require that each V (S) is a comprehensive set, i.e. if u E V(S),u' E L (S) andu ~>u', thenu' E V(S). s A game is a correspondence (i.e. a set-valued map) V: r e - * L , such that V (S) C Lo. (S) for every S E m .
Definition 2.1 : An allocation u E V (M) is blocked by the coalition S if there exists u ' E V(S) such that u' > u . s Definition 2.2: An allocation u E V (M) will be in the core if it cannot be blocked by any coalition. Remark 2.3: Let S be a coalition with # (M kS) > 0. Then if u is in the core, then ul s does not belong to the interior of V (S) (in PS - topology). The proof of this fact is straightforward. ,We shall assume, without loss of generality, that each V (S) contains the origin of L (S). Then it sufficies to consider the intersection of V (S) with the nonnegative orthant o f L (S), and we shall denote this intersection by V (S). By int V (S) we shall denote the interior of V (S) in the nonnegative orthant o f L (S) with respective to the relativized topology PS" From the above discussion, it is clear that a blocking coalition is effective only when + it has positive measure. So, define rnu = {[S] E rnu IS E m,~.(S)> 0), where [S] is the
98
T. Ichiishi and Sh. Weber §
4-
equivalence class of S. For eachS E rnu denote ms = {[T] E mu l# (T kS) = 0), where [T] is the equivalence class of T. Denote m = U mE and for each S:
n=l
n
mS = ~ r mS, and m will be a set of all incomplete coalitions with the positive measure, where S is incomplete if/a (M kS) 3> 0.
3. Preliminary Observations
Section 3.1 : Now we need some lemmas in order to be able to formulate our results. Lemma 3.1.1: The core of the game V is non-empty, if and only if for each incomplete coalition S there exists a family o f linear functionals (f~v_) val (fS E L I (S) for each v El) and a corresponding family of nonnegative numbers {a~v)v~l such that: 1. int V (S) c L= (S) \ G (S) where G (S) is the set of solutions of the system
rSu
2. The game H defined by H (S) = L~ (S) \ G (S), if S E ~ , and H (S) = V (M), if S E [M], has a nonempty core. Proof: Let us prove the first part of the lemma. Suppose that u is in the core of H and there edst two families (.t'v), (av), satisfying 1., 2. Suppose also that u is blocked by some coalition S in the game V, i.e. there exists u' E V (S) such that u' 3> u. Denote S u" = (u + u')/2. Then u" > u and u" E int V (S) and, therefore, u" E H (S). Hence, u S is blocked by S in the game H, a contradiction. Therefore, the core of V is nonempty. Assume, now, that u0 is in the core of V. Given coalition S consider the system of inequalities in L~ (S):
(*), fTUdt-t >~fTuod#, where T E'm S. Let us define a family of linear functionals ~T}T~ ms in the following way:
f S . u = fs u X r dg = fT udl~, where u E L~ (S), Xr is a characteristic function of the set T. Then the system (*) can be rewritten as follows: (**) (fTs u/> a S ) , where T ~ ms and a s = fT uod~. Denote a set of solutions of (**) by G (S) and its complement in L= (S) by H (S). It is easy to verify that the allocation Uo belongs to the core of H: Uo can be blocked only by elements of Gs, and not of Hs, and this is the case for all S. Now let us show that H (S) D int V (S). Assume u @ G (S) then u ~> u0. Otherwise, there exists a coaliS tion T, such that T C S and u < Uo. In this case the inequality f S u/> offT does not hold -
T
and u 9 G (S), a contradiction. Now, since u >/Uo, it follows that u does not belong to s
Some Theorems on the Core of a Non-Sidepayment Game
99
int V (S). Therefore, if u E G (S) then u ~ int V (S) or H (S) D int V (S). It is the case for all incomplete coalitions, and the lemma is proved. Q.E.D.
Lemma 3.1.2: Suppose A and B are two nonempty closed convex subsets o f L= with respect to the o (L.~, L 1 ) topology. Suppose also that A is compact with respect to the same topology. Define J x (f) = inf f . u, where f C L 1, X is a subset o f Lo~. Then uEX A N B --/:f) if and only if the inequality JA (f) + JB (-- I") <<-0 holds for each f E L 1. Proof: Suppose A C~B 4= 0. Then there exists u EA NB. Then for all f E L l : f " u >~:A (f) and -- f . u >~SB (-- f). Hence, JA (f) + JB (-- JO <~O. Suppose now thatA n B = 0. Then, by Lemma A.1.3, there exists f0 EL1 such that inf f0 " u > sup f0 " u. Theorefore, inf f0 " u > - - inf { - f 0 9 u), i.e. uEA u~B uEA u~B JA (fo) + JB ( - - f o ) > O, and the intersection of A and B is nonempty if and only if JA ( f ) + J B (--J0 ~< 0 f~ e a c h f E L l ' Q.E.D. Lemma 3.1.3: Given a coalition S, let (aS}, where T E mS' be a family o f nonnegative numbers, such that: 1. For each pair o f disjoint sets T1, T2 E mS the equality a T S 1 + aS 2 = a T S 1 uT~ holds; and 2. a S <~Kla (T), where the positive constant K does not depend upon T. Then there exists a unique element u E Loo (S), such that f T udl.t = aST for each T E m_~S"(The element u will be called the "primitive e l e m e n t " o f the family (~ST), T E mS.) Proof: Note that throughout this lemma the concepts "open set" ("closed set", "compactness", resp.) mean open set (closed set, compactness, resp.) with respect to o (Loo (S), L 1 (S)) topology on L~ (S). For each T E ms defineA T = (u E L ~ (S) [Hull ~
r/
-
(rz)
• n
Then it is easy to check that I~A UTI E i= f q1A Ti . Note that for each T E mS A T is a subset of the set B = (u E L~o (S) [ [lull ~
100
T. Ichiishiand Sh. Weber
all A T, T E mS is nonempty, and there exists u E
r A T' The uniqueness of such TE ~/$ u follows immediately. If u' :~u"~ u', u" EL| (S) then there exists a coalition S' such S that S' C S and fs, u' dla --/:f s, U" dla and one of two inequalities f s, U, dla = a sS, or fs' u" d/l = a S, does not hold.
Q.E.D.
Section 3. 2: We now turn to preliminary observations of a somewhat different approach which uses a generalized version of the Fan theorem in the context of vector lattices. For each S E mu, define Vs = ([u] EL= (S) [ there is no u Vs such that u' Is s>U Is.}. Define also a map, proJs: L~ (34) ~L~, (M), by:
(proj s
U)
(m)
] u(m),
;for all m E S,
I (0,
forallmEM\S.
Then, a utility allocation u is in the core, if (1) projM u E VM, and (2) projs u E~VS for every S E ~ . Now, let B ( L = , L=) be the vector space of all continuous linear maps from (Z~ (M),I[ I[Lo.(M)) to (Z~ (M),II IIL~.(M)).B (L~,, L~) is a normed space when endowed with the uniform operator topology II II [see, e.g., Dun ford/Schwartz, VI. 1.1, p. 475]. We are going to reformulate the core using this normed space (B (L~,, L..),II II). Since the set M plays two roles in the definition of core (giving the criterion for feasibility of a utility allocation, and being a possible blocking coalition), the two roles have to be explicitly distinguished. Let I be, therefore, an index set defined as + § mu u (co}, where 60 is a new single point adjoining rnu and define xi's in B (L**, Lo.) by: proJs,
if i = [S] 6 m#+'
Xi
t projM,
if i = w.
[The member, projM, ofB (L=, L~)appears twice here, as X[M 1 and x w .] The vector space L= (M) has an order structure induced by the positive cone L*~ (M) = {[u] EL~o (M) I u (m) ~>0,/~-a.e. inM}. A subset C i ofL~. (M) is defined by:
{
~Vs,
i f / = [S] E
VM,
i f / = ~.
rn +
Lemma 3. 2.1: Let V = ( V S }Sem be a game, and define {x i I i E I), (C i I i E I} as in the preceding paragraph. Then, the following are true:
(i) I f T: B (L~, L~ ) -+ L~ (34) is a linear map such that Tx i 6 Ci for every i E L then Tx ~ is in the core o f the game V;
Some Theoremson the Core of a Non-SidepaymentGame
101
(ii) I f u E Loo (34) is in the core of the game V, then there is a continuous linear map T: B (L~,, L=) ~ L . . (M) such that Tx i E Cifor every i E l a n d such that Tx = u. Proof: (i) Given such a linear map T, it suffices to show that projs T(projM ) = T(projs) for every S E m~. Since ~VS C L~ (S), projs T(projs ) = T(projs). Similarly, projM\S T(projM\S ) = T(projM\S ). Adding the two equalities yields: projs T(projs ) + projM\S T(projA/\S) = T(projs ) + T(projM\S ) = T(projM ). Or, T(projs ) = projs T(projs) = projs [projs T(proJs) + projM\S T(projM\S)] = = projs T (projM). (ii) Given a member u of the core, one can easily check that the evaluation map eVu : B (Loo, Loo) -~ L~o (M), defined by: evu (f) = f ( u ) , for every f E B (L~, Lo.), satisfies all the requirements for T.
Q.E.D.
Corollary 3.22: Let V = (Vs)s~ m be a game, and define (x i [ i E l ) , {Ci I i E I ) as in the paragraph preceding (3.2.1). Then the following three statements are equivalent: (i)
ThereexistsalinearmapT.'B(L~,Loo)-+L~(M)suchthatTxiECiforevery iEI; (il) there existsacontinuous linearmap T: B (L~,Lo.)-+ L~ (M)such that T x i E C i for every i E 1; (iii) The core of the game V is non-empty. By (3.2.2), the core is characterized as a family of continuous linear maps from a normed space (B (L~o,L~), II II) to an ordered topological vector space (Lo. (M), II IIL.o(M),L+(M)). Proof of the following Lemma 3.2.3 is straightforward:
Lemma 3.2.3: Ira game V = {Vs)s~ m satisfies comprehensiveness, then the set Ci defined in the paragraph preceding (3.2.1) is full for each i E l .
4. Main Results
Section 4.1: Let us formulate now our main results, which conclude necessary and sufficient conditions for nonemptiness of the core in the general case (Theorems 4.1.1,4.1.2, and 4.2.1) and sufficient conditions for the special class of games (Theorem 4.1.3). Theorem 4.1.1: Let V (M) be a closed convex subset of L~ with respect to the o (L oo, L 1) topology. Then the game V = ~VS) S E m, has a nonempty core, if and only if for each incomplete coalition S there exists u S E L~ (S) such that:
102
T. Ichiishi and Sh. Weber
(i) (ii)
u S ~ int V (S), sup_ II u s II < o~; S~m (iii) There exists a non-negative number p >~o such that the inequality n n sup VM (f) ~ ht>~suP0 [i~'=lhi aTi --oil f - - i=~'1 hifTi II] h~ f~ each f E L l ' where i = 1, 2 . . . . . n,'fT " is a linear functional which is defined by." fT. " u = fT. U)~T.dp, l
u EL
l
1
l
(S), aT., = T.cS sup fri usdiz, SUPVM(f) = u~t~(M) su f " u, and
o = sup i~=l h i aTi, where h i vary under the conditions h i > 0 and n II ~ hifTill= l,ZiE'm S. i=1
Theorem 4.1.2. Let V (M) be a closed convex subset of L.. With respect to the o (L=, L 1) topology. Then the game V = { VS }s~'~has a nonempty core, if and only if for each incomplete coalition S there exists a family of nonnegative numbers (aS}, T E ms such that aS 1 u T~ = aS + aS~ for each pair of coalitions Tx, T2 E "ms with a I~-null intersection; 1"1 (ii) a S ~ K II (T) where the positive constant K does not depend upon S and T; (iii) A primitive element u S of the family (a S} T E "~sdoes not belong to int V(S); (iv) is the same as (iii) of Theorem 4.1.1. (i)
Theorem 4.1.3: Suppose that for each incomplete coalition S there exists a family o f numbers {uS}, satisfying (i), (ii), and (iv) of Theorem 4.1.2 and suppose that (iii') for each S E -m the inequality/3 S =
sup f r udu <<-a s holds for at least one of u~ V(S)
T ~ ms. Then the game V has a nonempty core. Section 4.2: For any s e t I ( t o be interpreted as an index set), denote by 9 R the family of all non-negative valued functions h on I with finite support. The support of h E 9[ R is denoted by supp h. ~+
Theorem 4. 2.1: Ira game V = { VS}S~ m satisfies comprehensiveness, then the following two conditions are equivalent. (i) (ii)
The core of the game V is non-empty; Foreach(h, la)E~R§215 ~ § thereexisty(X'U) Ei~III (Ci+L+~(M))and z (x,u) E I I (Ci --L~ (M))such that (v (x''~), z (x'~)) = (y~(x,u), z~(X,u))for i~l
Some Theorems on the Core of a Non-SidepaymentGame every positive number a, such 2; (Xiy} x,u) + k~y}X"u')) iEl " <~ 2 (h i + k i' ) y i( ~ * x ' , u + u ' ) -iEl (k',tl')Ei~.§
I ~
103
that 2; (#;z} x'") +u'.z!X"u')/ i~l , , -t t 2 (~i + ~)z}X+x',~+.') for every (k,/~), i~1 9 z i( X , u ) < 0 f o r e v e r y ieIZ kiYiX'u)-( ieI 2; ui
( k , ~ ) E e R + X e R f o r w h i c h 2; ( k i - - # i ) x
i = O,andsueh that
2; (h i y } x ' u ) - / l iz} k' ~ ))/,l[ ~ (h i - I ~ i) x i I I E L (/14) I ( k , / ~ ) E e R iEI i~I I (Xi -- ~i) xi ~ 0 } is order bounded from above, where I, {x i [ i E I ) ,
• eR ,
{Ci [ i E l } are deft'ned in the paragraph preceding (3.2.1). Remark 4.2.2: It is easy to check that the following conditions are equivalent:
(i)
i zl (k; - .;) x i : O;
(ii)
2; (XS --/aS) + k --/a w = 0,/1 -- a.e. in M, where mLis the range S~m~ : S~rn (mu) of any fixed injection ~: m+u-+ m such that L([S]) E [S] for every [S] E m§
Remark 4.2.3: It is also easy to check the identity: 1[ 2; (h i --tAi)X i 11 = inf
i~I
N m
~p\
N
[
2;
SErnL:S~m
(ks -#S) + ( X - U ~ ) l,
where N ranges over the g-null subsets of M and m~is defined as in Remark 4.2.2,
5. Proof of the Theorems Let us prove now the theorems which were formulated in two previous sections. Proof o f Theorem 4.1.1. By Lemma 3.1.1, the core of the game V is nonempty if and only if for each incomplete coalition S there exists u S E L= (S), such that if we denote by G (S) the set of solutions of the system (**) (see Lemma 3.1.1) and by H (S) the set L= (S) \ G (S), then the game H defined by: H (S) as above if S ~ m; H (S) = V (M) ifS ~ [M], has a nonempty core. Then by Remark 2.3, ifu E V(M) is in the core of H, the projection u onto S does not belong to H (S). (It is clear, that H (S) is open with respect to the PS - topology.) Therefore, the game Hhas a nonempty core if and only if there exists u E V(M), such that the projection of u onto each S E ~ belong to G (S). Denote by G a set of all u E L~o such that the projections of u onto each S E ~ belong to G (S). Now we have to show that if all conditions of the theorem are fulfilled, then G N V (M) ~: 0. We are going to do it by using Lemma 3.1.2. But in order to be able to apply this lemma, we have to prove that G is nonempty. The natural way to do it is the using of the Fan's
104
T. Ichiishi and Sh. Weber
results (Lemmas A.1.1 and A. 1.2). Note now that for each S the system (**) can be regarded as a system of linear inequalities on Loo. Hence, the set G is the set of all u E L , satisfying (**) for eachS E -m or satisfying U {-fT " u/> a~}, T E mS" If we will S~r~
gather the inequalities corresponding to the same equivalence class, then the last system can be rewritten as: (***) {fT" u >i aT}T~-ffl where a T = Sup a S .
TCS
In order to describe the solutions of (***) Lemma A.I.1 will be used. In our case the space X of Lemma A. 1.1 is L x and the conjugate space X * is ' L~. By Lemma n A.1.1 a solution u ~ L ~ of (***) exists if and only if o = Sup i~l xi aTl' where n
n = 1,2 . . . . . Xi >~O, T i E "m and II i=1 ~ XifT~ It = 1. We shall prove that o is finite if and only i f K = Sup II u S II is finite. S~m (i)
Suppose K < oo. Note IIfT IIz~ = fM • d# = la (T). Note also that Su aS = Sup STu e dp <~Kp (T). Therefore, if n
II Z
n
i=1
XifT. II = 1,or f M ( ~ X i • z
I
1,then ~
i=1
Xila(Ti) = 1 and
n
o=
n
Sup
,,~ i = l ~ifr,=1 ' (ii)
~
i=1
~'i
aTi
<~ sup
hi>~O
~ Xi 9 K 9 g, (Ti) = K.
i=1
Therefore o is finite. Suppose Sup II u s II = ~. Then for each positive n u m b e r N there exists a coaliS~m tion $I such that II Us IIL~ = I[ u~ ll~ ,e ~ > N . Then there exists a subset $2 E m o f S l such that us~ S~ >N• M" Tl]~ $2 ~>a Sz} = f S.z_ u SL. d p > N p ( S 2 ) " Choose Xl = lip ($2). Then II Xl fS2 II = 1 and o ~> Xl as2 >~N. It follows from here that o is infinite. Therefore, the set G is nonempty if and only if for each S E ~there exists u s E int V (S) and Sup II u S IIz~ < oo. S~ Note that G = U Gp, where Gp = (u E G [ Ilull <~ p}. By Lemma A.I.1, Gp is o>10
nonempty if p ~> o. Therefore, the intersection G n V (M) is nonempty if and only if there exists a number p/> o such that GO f~ V (114)r O. GO and V (M) are both closed convex sets of L , with respect to the o ( L . , L~ ) topology. Since GO is nonempty for p ~> o, then, by Lemma 3.1.2, Gp n V (M) is nonempty if and only if JGo (f) + JV(M) (--f) <~0 for e a c h f E L1. (By Lemma A.1.4, GO is a compact subset of L.. with respect to the o ( L . , L a) topology.). By Lemma A. 1.2, JGp (f) =
Some Theoremson the Core of a Non-SidepaymentGame n
105
n
hi~>0Sup [i~1 )ti aT. --P Iff - i=12; XifTJl]', Note thatJv(M) (--f) = -- V(M)SUp(f) - and, therefore, G and V (M) are disjoint sets if and only if there exists p 1> o such that n
n
V(M)SUp(f)>~ xi~>SuP0[i~l )ti aT. --P Ill-- i=2;1XifTi II]f~176 proof of the theorem.
Q.E.D.
Proof of Theorem 4.1.2: If the core of game V is non-empty, then, by Theorem 4.1.1, for each incomplete coalition S there exists u S E L= (S) such that if we shall denote aS = ST Us dta, T E ~, then conditions (i), (ii), (iii) and (iv) are fulfilled. Suppose now that for each S E N there exists a family {aS}, satisfying all conditions of Theorem 4.1.2. Then, by Lemma 3.1.3, there exists a primitive element Us, such that fT Us dt~ = a s, T E "mS. Note that from (ii) it follows that II u s II < g for each S E N. Therefore, all conditions of Theorem 4.1.1 are fulf'dled and the game V has a non-empty core. Q.E.D. Remark 5.1 Let us consider condition (iii) of Theorem 4.1.2. Denote ~T = Sup fT udla. Let us fix some coalition S. Of course, the situation when u~ V(S) u E int V (S) but fT udla < ~ST is possible even in the case of convex V (S). But if aS ~>~S for some set T E ms, then the primitive element u S does not belong to int V (S). Otherwise, there exists x E int V (S) such that x >TuS and therefore ~s >>.f T xdg > S u S d/a = a S, a contradiction. Proof of Theorem 4.1.3, follows immediately from Remark 5.1.
Q.E.D.
We now turn to the proof of Theorem 4.2.1. Let E be a locally convex space over the field R of real numbers, and F a topological vector space over R ordered by a cone K Given an indexed family {x i ! i E l ) of members of E, and an indexed family (Ci i i El} of subsets o f F , the central question here is summarized as:
Question 5.2: When does there exist a continuous linear map T: E ~ F such that Tx i E C i + K for everyi EI? For the special case in which Ci is a singleton for each i E l , the question has already been answered by Riedl's version of the Fan/Hustad theorem (see (A.2.5) in the Appendix) and the present task is to generalize this. Since the Fan/Hustad theorem follows easily from the Mazur/Orlicz theorem (see (A.2.4) in the Appendix), it suffices to generalize the latter. Althoug the present proof of Lemma 5.3 merely follows the celebrated technique of Pt(tk [1956], its full account is given here for expository purpose. Lemma 5.3. Let E be a vector space over R, F an order complete vector lattice over R, and p a sublinear map from E to F. Let {x i t i E I) be an indexed family of members
106
T. Iehiishi and Sh. Weber
orE, and {Ci I i E l ) an indexed family o f subsets ofF. Then, the following two conditions are equivalent: (i) (ii)
There is a linear map T : E-~ F, such that Txi E Ci + K for every i E I, and that p (x)>_- T x f o r e v e r y x EE; For each h E 9 R there exists yX E II (Ci + K), such that I ~ + i~l ~, hi y~ + )2 lai y~ <<. Z (h i + lai) y~+U for every h, U E I R+, and such that iEl i~1 i~I p ( Zi~l hixi)>1 i~l h i Y ) f~
X E* R ~+
Proof." (i) ~(ii): For each h E ~ R+, define y x by: y~ = Tx i for every i E l . It is straightforward to check that all the conditions of (ii) are satisfied.
(ii) ~ (i}: Take any x E E and any h E 9 R+. Then, p (x + ~ h i xi) + p (-- x) >~p (~ h i xi) >~ ~, h i y~, or - p (-- x) ~
(p (X -t- ~_,hiXi) -- Z hiy~} q- {19 (X' + ~ tZiXi) -- )2 IdiY~)
= ~p (x + z x~ x~) + p (x' + )2 ~ xt)) - ~z ~ y~ + ~ u~ y~ >~p (X + X' + ~, (h i + lai)xi) -- ~, (h i + Idi)y~ +u'. By the generalized Hahn-Banach Theorem (see (A.2.3.) in the Appendix), there exists a linear map T: E ~ F such that q (x) >i Tx for every x E E. By choosing h E 9 R such that ;~i = 1 and h h = 0 for every h 4: i, one concludes q (-- xi) < p (-- x i + xi) - y ~ where y x E Ci + K. So, T (-- x i) <~q (-- x i) <<.- y~, and thus, Tx i E Ci + K for every i E l . On the other hand by chosing ;~ E 9 R§ such that h h = 0 for every h, one concludes q (x) < p (x), and thus Tx <~p (x) for every x E E .
Q.E.D.
Lernma 5.4: Let E be a locally convex space, and F a topological space which is also an order complete vector lattice ordered by a normal cone K. Let {x i I i E l } be an indexed family o f members orE, (Ci i i E l } an indexed family of subsets ofF, and consider the following two conditions: (i) (ii)
There is a continuous linear map T: E ~ F such that Txi E Ci + K for every iEI; There exists a neighborhood U of O in E, and for each h E ~ R there exists yXE II (Ci + K), such that y h = yah for every positive real number ~, such
Some Theorems on the Core of a Non-SidepaymentGame
107
that Z hi yX + i~1 Pi Y~ < ~ (hi + #i) Y~ +~ for every ~, p e ~ R+, such that iE1 i~1 ~, Xi y ~ < O for every h E f R+ for which Y, hi x i = O, and such that the set i~l ~ i~1 ( ~ kiy ~ C F I h E 9 R+, i~1 hixi @ U) is order bounded from above. i~l 1 Then, (ii)implies (i). Furthermore, if the topological interior of K is non-empty, then (i) implies (ii). Proof." [(i) and Int K r 0] :* (ii): Fix any u E Int K, and define U = (x E E t Tx <<,u}. The set Uis a neighborhood of 0 inE. For each h E 9 R+, define y x by: yX = Tx i for I every i E 1. It is straightforward to check the conditions of (ii).
(ii) ~'(i): Let b E K be an upper bound of the set (Z kiy ~ E F I X E * R+, h i x i E U). One may assume, without loss of generality, that the O-neighborhood U is convex and circled. Denote by m the Minkowski functional for U. Then, the map p: E ~ F, x ~ m (x) b is sublinear. Take any h E * R. If Z hi x i = 0, then I
p (Z hixi)
~
m (OO)b = O >l ~. Xiyx. If Z h i x l e O , t h e n I
p (Z k i xi) = m (~ hi x i) b >f m (Z hi xi) (~. hi y~ / m (Y, h k Xk)} = Z ~ y~. Thus, all the conditions of (ii) in Lemma 5.3 are satisfied, or there exists a linear map T: E -~F such that (A) Tx i E Ci + K for every i E I , and that (B) p (x) >/Tx for every x E E . It suffices to show that the result (B) implies continuity of T. Let W be any full neighborhood of O in F, and choose a positive number/3 so that Jr/~b E W. It will be shown that T (~U) C W; i.e., that - b <~Tx <<.b for every x E U. Notice that m (x) < 1 i f x ~ U. So, Tx <.p (x) = m (x) b <~b. Also, T (--x) ~
~- b. Q.E.D. It seems that the above (5.4) completely answers Question (5.2). But in order to study the core of a game, one needs actually to answer a stronger question:
Question 5.5 When does there exist a continuous linear map T: E -* F such that Tx i ~Cifor every i EI? It is clear that any answer to (5.5) can be an answer to (5.2). The converse is also true for. interesting cases, as the following trivial consideration shows: Let E, F, K, (x i I i E l ) , {Ci I i E l ) be defined as in the paragraph preceding (5.2). Define II = I2 =-1, and consider the enlarged index set J = Ix + Is. Let {2/. I] E J-), ( C / l i E J) be defined by:
x~ if]EI1 --xj i f j E I 2 ,
{
C~ --Ci.
if]Ell ifjEl2,
108
T. Ichiishiand Sh. Weber
and consider Question (5.2) in which {x i t i E I ) and {Ci I i E l } are replaced by {~/I ] E J) and {~ I] E J}, respectively. If C i is full in F for each i E I, then any answer to this new question is an answer to (5.5). Corollary 5.6: Let E, F, K {x i I i E I}, {Ci I i E l } be as in Lemma 5.4. Assume that the topological interior o f K is non-empty, and that C i is full in F for each i E L Then, the following two conditions are equivalent:
(i) (ii)
There is a continuous linear map T : E -~ F such that Tx i E Ci for every i E I ; There exists a neighborhood U o f 0 in E, and for each (k, #) E 9 R+ X 9 R I~ I ~+ there exist y (x'~) E II (C i + K) and z (x'u) E ll (C i - K), such that (yCX,~), iEl i~I Z(k,~)) = (y~(k,~) z~(X,~)) for every positive real number ~, such that E (k.v!X,~)+k'.v(.~',~')~ - F, (u.z(.X'~)+u'.z(.X"~')~ iEl " t~z t~z " iEl ,~-t t ,-t t ,
~< 2; (ki + ~,'3v(.x§247 -- ~ (t~i + I~) z~X+x"u+u')for every (k, I~), iEI t " ~t iEl (~', If) E 9 R~+ • 9 ~R+, such that ~ ~z"y~X,. ~) - ~ ~'i" z(k'u)i <<"~-0for every I 1 i~I i~I (k, Iz) E I~ R~+ • ~ R+ for iEIF" (ki - lzi) x i = O , and such that I (X,u)
X
n~+,
-
E tO is
order bounded from above. Proof o f Theorem 4.2.1: By (3.2.2), the core is characterized as the family of all continuous linear maps T from a normed space (B (L**, L**) I1 II) to a topological vector space (L| (M), II IIL**(M))ordered by a cone L***(M), such that Tx i E C i for
every i E l , where {x i I i E l } and {Ci I i E l } are defined in the paragraph preceding (3.2.1). Put E = B (L.., L**), F = L** (M), and K = L ~ (M). By (A.2.2) in the Appendix, the space F is an order complete vector lattice ordered by K, and the cone K is normal. It is easy to see that the topological interior of K is non-empty. By (3.2.3), C i is full in F for each i E I. Corollary 5,6 is now applicable. Q.E.D. 6. Discussion of the Literature Sidepayment Games with Finitely Many Players: A condition equivalent to non-emptiness of the core, called the balancedness condition, was discovered independently by Bonclareva [ 1962] and by Shapley [ 1967]. Sidepayment Games with a Measurable Space o f Players: Schmeidler [ 1967] established a condition equivalent to non-emptiness of the core, where the core is formulated as a certain class of additive set functions. Later, Kannai [ 1969] pointed out that Schmeidler's condition can be obtained directly by applying Fan's theorem [1956] on a system of linear inequalities. He also provided a necessary and sufficient condition for the core to have a countably additive set function. Problems related to the latter question were
Some Theorems on the Core of a Non-SidepaymentGame
109
systematically studied in an important paper, Schmeidler [ 1972], in which he established remarkable usefulness of the exact envelope of a game.
Non-Sidepayment Games with Finitely Many Players: Sufficient conditions for nonempty of the core have been obtained by three different approaches. The most successful approach, originated by Scarf [1967, 1973], developed a considerably elaborate algorithm for a member of the core of a balanced game. See also Shapley [ 1973]. The second approach is due to Scarf in his unpublished paper, and toAubin as reported in Ekeland [ 1974]; assuming convexity as well as a stronger version of balancedness they reduced the problem to Kakutani's fixed-point theorem. The third approach is due to Billera [ 1970]; assuming convexity, he reduced the problem to the study of hyperplane games, which are essentially the same as sidepayment games. Billera also provided a necessary and sufficient condition for non-emptiness of the core. Non-Sidepayment Games with a Measure Space of Players: Kannai [ 1969 ] applied the result of Scarf [ 1967] to the case in which there are countably many players, and provided a sufficient condition for non-emptiness of the core. He did not treat an atomless measure space of players. [C.f. the fourth paragraph in Section 1 of the present paper.]
Appendix Section A. 1. In this section we collect some lemmas which were used in the previous sections. Lemmas A. 1.1 and A. 1.2 are the part of the fundamental results o f F an [1956] and Lemmas A.1.3, A.1.4 are the famous theorems of functional analysis [see Dunford~Schwartz]. Lemma A.l.1. Let {u )uEI be a family of elements, not all zero, in a real normed linear space, X, and let { ~ ) ~ I be a corresponding family of real numbers. Let n
o = Sup ~=1 ?~ia., when n = 1, 2, 3 , . . . ; ut ~ I a n d Xi vary under the conditions ?~i>0, 1 <<.i
The system (f " u >1a v } ~ i of linear inequalities has a solution f E X * , if and only ire is finite (X* is a conjugate space of X), I f the system ~f " u v >1av}v~ I has solutions f E X*, and if the zero-functional is not its solution, then o is equal to the minimum of the norms of all solutions of this system.
Lemma A. 1.2. Let F* denote the set of all f E X ~, satisfying: ~f . u v >1'~)v~I and IIf II ~
n
supremum of the expression, i=1 ~ Xi ~v/ - P IIx -- i=1 ~ Xi u II, when n = 1,2,3 . . . .
uiEIandXi>~Ovary.
110
T. Ichiishiand Sh. Weber
Lemma A. 1.3. Suppose A and B are two non-empty disjoint closed convex subsets of a locally convex topological space X. Suppose also that A is a compact. Then there exists a continuous linear functional f on X such that inf f . x > S u p x~_A x~B
f.x.
Lemma A. 1 4. Let X be a separable Banach space. Then each bounded subset M of the conjugate space X* is conditionally compact in X* with respect to the weak topology on X* which is generated by X. Section A.2 A subset K of a vector space F over the field R of real numbers is called a cone, if (1) K n ( - K) = O, (2) XK c K for every X E R § and (3) K is convex, where O denotes the zero element in F, R§ the set of all non-negative real numbers. A cone K in F induces a vector ordering >i on F, by defining y ~>y' if and only i f y - y ' E K ; in this context F is called an ordered vector space, and K the positive cone. Given a subset B of an ordered vector space F, if y E F satisfies (1)y/> b for every b E B, and (2) y' ~>y whenever y ' i> b for every b EB, theny is called the supremum of B. The infimum of a set can also be defined in an obvious way. An ordered vector space F is called a vector lattice, if the supremum (or the infimum) of every pair (.v, y'} of elements o f F exists. A vector lattice F is called order complete, if any subset B in F that is majorized in F (i.e., any subset B in F for which there exists y E F such that y 1> b for every b EB) has the supremum in F. A subset B of an ordered vector space is called full if B = ~v" E F ly >~y" >~y' fory EB, y'EB}. When F is a topological vector space, a certain class of cones induce vector orderings that prove compatible naturally with the given topology. The positive cone K of an ordered topological vector space is called normal, if there is a neighborhood basis of O for the topology consisting of full sets. It is easy to prove [see, e.g., Peressini, 2.1 ..7, p. 64]: Lemma A.2.1: The positive cone K of a n ordered normed space F is normal if and only if there is an equivalent norm II II on F such that y >/y' >i 0 implies IIy II >1 IIy' II. The following theorem (A.2.2) is well-known to functional analysts, but the present authors could not find any references for its statement nor for this proof: Theorem A.2.2: If(M, m, la) is a positive o-finite measure space, then (L** (M), II IIL.o(M)) is an order complete vector lattice ordered by a normal cone LL (M') = ([u] ELo, ( M ) l u (a)>~O,p--a.e. inM). Proof: Normality ofL + (/14) is a straightforward result of (A.2.1). The vector space L1 (M) ordered by the positive cone L~ = (be] EL1 (114) If(a) ~>0, p -- a.e. inM} is a vector lattice, hence it has the decomposition property, and the cone L~ generates L t (/14).Then, by Reisz' theorem [see e.g., Peressini, 1.2.4, p. 23], the vector space (L t )b of all order bounded linear functionals on L 1 (/14)ordered by the cone of positive linear functionals, is an order complete lattice. Therefore, it suffices to show
Some Theorems on the Core of a Non-Sidepayment Game
111
that L~, (M) = (L i )b. Recall that L.~ (3/) is the set of all continuous linear functionals on (Ll (M), II IIL (M))" See, e.g.,Dunford/Schwartz [1958, IV. 8.5, p. 289]. It is easy again by (A.2.1)~to check that the posivite cone L~" is normal in (L1 (M), II [IL (M~) So, by Krein-Grosberg's theorem [see, e,g.,Peressini, 2.1.21, p. 72], L.. (M) ~ (]~-1")~. On the other hand, direct application of Nachbin-Namioka's theorem [see, e.g., Peressini, 2.2.17.c, p. 88] shows (Ll)b C L . . Q.E.D. LetE be a vector space overR and F an ordered vector space over R with the positive cone K. A map p : E ~ F is called sublinear, ifp (x) + p (x') >t p (x + x'), and ~p (x) = p (oct) for all x, x' in E and all a in R+. For any set I (to be interpreted as an index set), denote by ~ R+ the family of all non-negative real valued functions on I
with finite support. Theorems on existence of linear maps from E to F, some of which already appeared in Section A. 1, when F = R : Theorem A.2.3 (Hahn-Banach): Let E be a vector space over R, F an order complete vector lattice over R, and p a sublinear map from E to F. I f T is a linear map from a linear subspace M orE to F such that p (x) >t Tx for every x EM, then T can be extended to a linear map TI of E into F such that p (x) >t Tlx for every x EE. Theorem A.2.4 [Mazur/Orlicz]: Let E be a vector space over R, F an order complete vector lattice over R, and p a sublinear map from E to E Let {xi I i EI} and {Yi [i EI} be indexed subsets o r e and F respectively. Then, the following two conditions are equivalent:
(i)
ThereisalinearmapT:E-~FsuchthatTxi>~YiforeveryiEIandsuchthat p (x)>~ T x f o r e v e r y x EE;
(ii)
F~
?~xi)>~i~I Xiyi"
Theorem A.2.5 [Fan/Hustad]: Let E be a locally convex space, and F a topological vector space which is also an order complete vector lattice ordered by a normal cone K. Let (x i l i E I} and ~vi l i E I) be indexed subsets orE and F respectively, and consider the following two conditions (i) and (ii):
(i) (ii)
There is a continuous linear map T : E-> F such that Tx i ~ Y i for every i E I ; There is a neighborhood U of 0 in E and a member b o f F such that for every X E ~I R~+iorwhich ~ XixiEU, itistruethatb>l ~ Xiy i. i~1 iE1
Then (ii) replies (i). lf, furthermore, the topological interior e l K is non-empty, then (i) implies (ii). Riedl [ 1964] pointed out that the classical Hahn.Banach theorem can be generalized into the present form (A.2.3) without virtually changing a proof, and the Mazur-Orlicz theorem [1953]and the Fan/Hustad' theorem [1956, 1960], which are proven by direct application of the Hahn-Banach theorem, can also be generalized into (A.2.4) and (A.2.5).
112
T. Iehiishi and Sh. Weber
Acknowledgement We w o u l d like to express our deep gratitude to Professor Kannai (Math. Dept., The H e b r e w Univ.) and to Professor Schiiffer (Math. Dept., Carnegie-Mellon Univ 9 for their stimulating discussions, assistance, and c o n t i n u o u s e n c o u r a g e m e n t during our research 9 References
Aumann, R.Z. Market with a Continuum of Traders. Econometrica 32, 1964, 39-50. Existence of Competitive Equilibria in Markets with a Continuum of Traders. Eeonometrica 34, 1966, 1-17 9 - : A Survey of Cooperative Games without Side Payments. Essays in Mathematical Economics in Honor of Oskar Morgenstern, ed. by M. Shubik. Princeton 1967, 3-27. Bewley, T. : Existence of Equilibria in Economies with Infinitely Many Commodities. Journal of Economic Theory 4, 1972, 514-540. - : The Equality of the Core and the Set of Equilibria in Economies with Infinitely Many Commodities and a Continuum of Agents9 International Economic Review 14, 1973, 383-394. Billera, L.J. : Some Theorems on the Core of an n-Person Game Without Side-Payments9 SIAM Journal on Applied Mathematics 18, 1970, 567-579 9 Bondareva, 0.31. : The Core of an N Person Game. Vestnik Leningrad University 13, 1962, 141 142 ( in Russian). Dunford, N., and Z T. Schwartz: Linear Operators, Part I, Interscience. New York 1958. Ekeland, I.: La th~orie des jeux et ses applications a I economic mathematlque. Verd6me 19749 Fan, K. : On Systems of Linear Inequalities. Paper 5. Linear Inequalities and Related Systems, ed. by H.W. Kuhn and A.W. Tucker. Annals of Mathematics Studies 38, Princeton 1956, 99-156 Hustad, O. : Linear Inequalities and Positive Extension of Linear Functionals. Mathematica Scandinavica 8, 1960, 333-338. Kannai, Y. : Coun~ably Additive Measures in Cores of Games. Journal of Mathematical Analysis and Applications 27, 1969, 227-240. Kelley, J.L., and L Namioka: Linear Topological Spaces. Princeton 1963. Mazur, S., and W. Orlicz: Sur les espaees m&riques lineaires, II. Studia Mathematica 13, 1953, 137-.179. Peressini, A, L. : Ordered Topological Vector Spaces. New York 1967. Pt~k, V. : On a Theorem of Mazur and Orliez. Studia Mathematica 15, 1956, 365-366. Riedl, J9 : Partially Ordered Locally Convex Vector Spaces and Extensions of Positive Continuous Linear Mappings. Mathematische Annalen 157, 1964, 95 - 124. Scarf, H.: The Core of an N Person Game, Eeonometrica 37, 1967, 50-69. - : The Computation of Economic Equilibria. New Haven 19739 Schaefer, H.H. : Topological Vector Spaces. New York 1966. - : Banaeh Lattices and Positive Operators. Berlin 1974. Schmeidler, D. : On Balanced Games with Infinitely Many Players. Research Program in Game Theory and Mathematical Economics. Research Memorandum 28.Jerusalem 1967. - : Cores of Exact Games I. Journal of Mathematical Analysis and Applications 40, 1972, 2 1 4 225. Shapley, L.S.. On Balanced Sets and Cores. Naval Research Logistics Quarterly 14, 1967, 453-460 9 - : On Balanced Games without Side Payments. Mathematical Programming, ed. by T.C. Hu and S.M9 Robinson. New York 1973, 261-289. -:
Received May 1977 (received version March, 1978)
