5_232_alimohammedy.dvi EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 3, No. 2, 2010, 187-193 ISSN 1307-5543 – www.ejpam.com Extended Concavifications and Exact Games M. Alimohammady1∗ and V. Dadashi 2 1 Department of Mathematics, Faculty of Basic Sciences,University of Mazandaran, Babolsar, Iran, 2 Islamiz Azad University–Sari Branch, Sari, Iran Abstract. In this paper we propose new version of cooperative games. In fact the notion of cooperative games and their concavifications are extended. As a consequence, in this new setting it turn out that coreV 6= ; if and only if cav(u)(CΩ) = u(CΩ). 2000 Mathematics Subject Classifications: 46M35, 54H25, 47H10. Key Words and Phrases: concavification, game, exact game, balanced game. 1. Introduction Usually, a game V with a continum players is a bounded real valued function defined on ∑ the Borel subsets of I = [0,1] such that V (;) = 0. Any member of ∑ is interpreted as coalition of player, V (R) gives the maximum payoff achieved by efforts of all members in the coalition R. Of course with this interpretation usually it is assumed that V is non-negative and not identically zero. In [1] a cooperative game is viewed as a real valued function u defined on a finite set of points in the unit simplex, also a concavification of u used to characterize well-known classes of games. 2. Preliminaries Let X be a normed space. The space of all continuous linear functionals defined on X is called the dual space of X and denoted by X ∗. Let 〈., .〉 : X × X ∗→ R be the duality pairing in X ×X ∗. The weakest topology on X that make continuous all elements of x∗ ∈ X ∗ is called the weak topology on X . Let φ : X → X ∗∗ defined by φ(x) = gx where gx(x ∗) = 〈x∗, x〉, x∗ ∈ X ∗ and ‖gx‖ = ‖x‖. The weakest topology on X ∗ that make continuous all φ(x) is called the weak∗ topology on X ∗. The weak topology on X and the weak∗ topology on X ∗ are usually denoted by σ(X , X ∗) and σ(X ∗, X ) respectively. ∗Corresponding author. Email addresses: amohsen�umz.a .ir (M. Alimohammady), v.dadashi�iausari.a .ir (V. Dadashi) http://www.ejpam.com 187 c© 2010 EJPAM All rights reserved. M. Alimohammady, V. Dadashi / Eur. J. Pure Appl. Math, 3 (2010), 187-193 188 Definition 1. Let X be a normed space, (a) a net {xn} in X is called weak∗ convergent in X , if there exists an element x ∈ X such that lim n→∞ |x∗(xn)− x∗(x)|= 0, ∀x∗ ∈ X ∗; (b) a subset A of X is called compact in weak∗ topology or weak∗ compact set if every net in A contains a subnet which is weak∗ convergent in A. Definition 2. A game V is called a balanced game if sup ∑ (R) αRµ(R)u(CR)≤ u(CΩ), where sup is taken over all finite sums ∑ (R)αRµ(R)u(CR), αR ≥ 0 and ∑ (R)αRµ(R) = 1. Definition 3. Given such a function u, we consider the concavification of u, denoted by cav(u), which is a function defined on ∆= {g : g ≥ 0, g is simple measurable f unction and ∫ Ω gdµ= 1}, as the infimum of all concave functions that are greater than or equal to u. Since the infimum of a family of concave functions is concave, so cav(u) is concave and is greater than or equal to u as it is shown in Lemma 2. Definition 4. In the extended version of cooperative game, we consider a non-empty set Ω and a finite measure space (Ω, ∑ ,µ), a game V is a bounded real valued function on ∑ such that V (;) = 0. For R ∈ ∑ , we denote by χR the characteristic function of R. Let B be the Banach space spanned by the set {χR : R ∈ ∑ } with the sup norm, where χR is the characteristic function of R. Then the space of all bounded additive functions on ∑ is denoted by BA would be isometrically isomorphic to the norm-dual of B. A payoff µ of V is an element of BA with µ(Ω) = V (Ω). The core of V consists of all payoffs µ such that µ(R) ≥ V (R) for each R ∈ ∑ . We can also identify the coalition R CR = χR µ(R) . Thus, the coalition will be identified with the uniform distribution over the members of R. A game V is converted a function u defined over the points CR for R ∈ ∑′ , where ∑′ = {R ∈ ∑ : µ(R) 6= 0}. The value of u at CR is the average of the worth of R, that is, u(CR) = V (R) µ(R) . We set H = { f :△→ R | f is concave and f ≥ u on ∆′} where, ∆′ = {CR : R ∈ ∑′}. For any g ∈∆ we set Lg = { ∑ (R)αRµ(R)u(CR) : g = ∑ (R) αRχR and αR > 0, ∑ (R)αRµ(R) = 1}. We can define two functions w : ∆→ R and cavu : ∆→ R by w(g) = sup Lg and cavu(g) = inf H(g). M. Alimohammady, V. Dadashi / Eur. J. Pure Appl. Math, 3 (2010), 187-193 189 3. Main Results Theorem 1. For any game V , core(V ) is bounded and weak∗ compact. Proof. For each λ ∈ core(V ), 0 ≤ λ(R) ≤ λ(Ω) = V (Ω), (∀R ∈ ∑ ). Therefore, core(V ) is bounded. For each net (λα)⊆ core(V ), since bounded sets in B are relatively weak∗ compact, so (λα) has a subnet (λαβ )β∈I which converges in weak∗ topology to λ0 ∈ B. But λ0(Ω) = limλαβ (Ω) = V (Ω) and λαβ (R) ≥ V (R) (∀R ∈ ∑ ), it shows that λ0(R) ≥ V (R). Both implies that λ0 ∈ core(V ). These facts imply that core(V ) is weak∗ compact. Lemma 1. w is a concave map. Proof. For ε > 0 there are two elements ∑ (R) αRµ(R)u(CR) and ∑ (R′) βR′µ(R ′)u(CR′) such that tw(g) + (1− t)w(h)− ε = t[w(g)− ε] + (1− t)[w(h)− ε] < t ∑ (R) αRµ(R)u(CR) + (1− t) ∑ (R′) βR′µ(R ′)u(CR′) ≤ w(t g + (1− t)h). Lemma 2. cav(u)(CR)≥ u(CR). Proof. By concavity of cav(u) and f ∈ H it follows that f ≥ u. Hence cav(u) ∈ H and cav(u)(CR)≥ u(CR), for any R ∈ ∑ . Proposition 1. w(g) =cav(u)(g) for any g ∈ △. Proof. Suppose ∑ (R) αRµ(R)u(CR) ∈ Lg . Choosing g = ∑ (R) αRχR such that αR ≥ 0 and ∑ (R) αRµ(R) = 1. Then cav(u)(g) = cav(u)( ∑ (R) αRχR) = cav(u)( ∑ (R) αRµ(R) χR µ(R) ) ≥ ∑ (R) αRµ(R)cav(u)( χR µ(R) ) ≥ ∑ (R) αRµ(R)u(CR). This shows that w(g) ≤ cav(u)(g). For the converse, we note that w is concave from Lemma 1, w(CR)≥ u(CR). Therefore, cav(u)≤ w. M. Alimohammady, V. Dadashi / Eur. J. Pure Appl. Math, 3 (2010), 187-193 190 Definition 5. λ ∈ BA is called linear support of f :△→ R at g ∈△ if f (g) = ∫ Ω gdλ and f (g′)≤ ∫ Ω g′dλ (∀g′ ∈ △). Proposition 2. cav(u)(CΩ) = u(CΩ) if coreV 6= ;. Proof. coreV 6= ; implies that there is λ ∈ BA which satisfies λ(Ω) = V (Ω) and λ(R) ≥ V (R) (∀R ∈ ∑′ ). Set f : △ → R by f (g) = ∫ Ω gdλ. It is clear that f would be a concave map. On the other hand, f (CR) ≥ u(CR). Therefore, f ∈ H, so cav(u)(CR) ≤ f (CR) for any R ∈ ∑′ . But f (CΩ) = u(CΩ) which implies that, cav(u)(CΩ) ≤ u(CΩ). So from lemma 2 cav(u)(CΩ) = u(CΩ). Corollary 1. λ is a linear support for cav(u) at CΩ if λ ∈ core(V ). Proposition 3. V is balanced game if core(V ) 6= ;. Proof. Assuming coreV 6= ; by proposition 2 yields cav(u)(CΩ) = u(CΩ). Since cav(u)(CΩ) = w(CΩ) = sup{ ∑ (R) αRµ(R)u(CR) : ΣαRµ(R) = 1,αR ≥ 0, ∑ (R) αRχR = CΩ}, so ∑ (R) αRµ(R)u(CR)≤ cav(u)(CΩ) = u(CΩ). Hence, sup ∑ (R) αRµ(R)u(CR)≤ u(CΩ). Lemma 3. Suppose that S is the set of all simple functions on (Ω, ∑ ,µ) and f : △ → R is the concave map. Then for any g ∈ S, there is a linear map G such that G(g) = f (g) and f (h)≤ G(h), (∀h ∈ S) Proof. The function − f is a convex function. Now applying Hahn Banach Theorem for L =< {g} > and − f , there is a linear function F : S→ R such that F(g) = − f (g) and F(h) ≤ − f (h), (∀h∈ S). Set G = −F , then G(g) = f (g) and f (h)≤ G(h), (∀h ∈ S). Theorem 2. coreV 6= ; if cav(u)(CΩ) = u(CΩ)(Here, we have not assumed that the elements of core(V ) are bounded). Proof. Since cav(u) is a concave map, so from lemma 1, there is a linear map G : S → R such that cav(u)(CΩ) = G(CΩ) and cav(u)(CR) ≤ G(CR). Then G(CΩ) = u(CΩ) = V (Ω) µ(Ω) and u(CR) ≤ cav(u)(CR) ≤ G(CR). Define λ : ∑ → R by λ(R) = G(χR). It easy to see that λ is a finitely additive measure. Moreover, λ(Ω) = G(χΩ) = µ(Ω)G( χΩ µ(Ω) ) M. Alimohammady, V. Dadashi / Eur. J. Pure Appl. Math, 3 (2010), 187-193 191 = µ(Ω)G(CΩ) = µ(Ω) V (Ω) µ(Ω) = V (Ω). Also λ(R) = G(χR) = µ(R)G( χR µ(R) ) = µ(R)G(CR)≥ µ(R)u(CR) = µ(R) V (R) µ(R) = V (R). Therefore, λ ∈ core(V ) which it completes the proof. Definition 6. [4] A game V is called an exact game if for each coalition R there is λ ∈ core(V ) such that λ(R) = V (R). Theorem 3. Suppose V is an exact game. Then u is continuous at CΩ if and only if each λ ∈ core(V ) is countably additive. Proof. It is well known that λ ∈ BA is countably additive if and only if it is continuous at Ω. Assume λ ∈ core(V ), u is continuous at CΩ and (Rn)n is a monotone sequence in Ω such that ⋃ Rn = Ω. We must show that λ(Rn) → λ(Ω). From the assumption u(CRn ) → u(CΩ). But u(CRn ) = V (Rn) µ(Rn) ≤ λ(Rn) µ(Rn) ≤ λ(Ω) µ(Rn) = V (Ω) µ(Rn) . Tending n → ∞ and since u(CRn ) and V (Ω) µ(Rn) → u(CΩ), so λ(Rn) µ(Rn) → u(CΩ) = V (Ω) µ(Ω) . But µ is a measure so µ(Rn) → µ(Ω). This shows that λ(Rn) → V (Ω) = λ(Ω). For the converse, we assume that λ ∈ coreV is countably additive, (Rn) ⊆ ∑′ , ⋃ Rn = Ω and a is a limit point for (u(CRn ))n. Without loss of generality one can assume that u(CRn )→ a (otherwise we can pass to a subsequence). From exactness of V for each Rn there is λn ∈ coreV such that λn(Rn) = V (Rn). From the compactness of core(V ), one can assume λn → λ, where λ ∈ coreV . Assume ε > 0, there is k ∈ N satisfying in λ(Rn) > λ(Ω)− εµ(Ω) for any n ≥ k. There is m′ ∈ N such that |λm(Rn)− λ(Rn)| < ε and so λ(Rn) < λm(Rn) + ε for each m ≥ m′. Consider n ≥ k and l′ ≥ max{n, m′}, now for each l ≥ l′, u(CΩ) = V (Ω) µ(Ω) = λ(Ω) µ(Ω) < λ(Rn) + εµ(Ω) µ(Ω) = λ(Rn) µ(Ω) + ε < λl(Rn) µ(Ω) + 2ε ≤ λl(Rl) µ(Ω) + 2ε= V (Rl) µ(Ω) + 2ε ≤ V (Rl) µ(Rl) + 2ε= u(Cl)+ 2ε = a+ 2ε. M. Alimohammady, V. Dadashi / Eur. J. Pure Appl. Math, 3 (2010), 187-193 192 Therefore, u(CΩ) ≤ a. On the other hand, u(CRn ) = V (Rn) µ(Rn) ≤ λ(Rn) µ(Rn) ≤ λ(Ω) µ(Rn) . Let n →∞, then a ≤ λ(Ω) µ(Ω) = V (Ω) µ(Ω) = u(CΩ). Hence, a = u(CΩ). Set BAR = {λ ∈ BA,λ(R) = V (R)}. Then if λ ∈ BAR we can define fλ(g) = ∫ Ω gdλ. So we define coreRV = {λ ∈ core(V );λ(R) = V (R)}. Lemma 4. BAR 6= ; if R ∈ ∑ and R 6= ;. Proof. It is easy to see that, there is λ0 ∈ BA, such that λ0(S) 6= 0. Set λ = V (S) λ0(S) λ0. Then λ ∈ BAR. Lemma 5. (a) Let λ ∈ BAR and fλ :△→ R by fλ(g) = ∫ Ω gdλ. Then fλ(CR) = u(CR). (b) Let λ ∈ coreR(V ), then fλ(CR) = u(CR) and fλ(CS)≥ u(CS), (∀S ∈ ∑ ). Proof. (a) fλ(CR) = ∫ Ω CRdλ= λ(R) µ(R) = V (R) µ(R) = u(CR). (b) It is similar to (a) fλ(CR) = u(CR). For an arbitrary element S ∈ ∑ , fλ(CS) = ∫ Ω CSdλ= λ(S) µ(S) ≥ V (S) µ(S) = u(CS). Theorem 4. Suppose that V is an exact game. Then u = inf{ fλ : λ ∈ coreRV,R ∈ ∑ }. Proof. For each λ ∈ coreRV , then fλ(CR) ≥ u(CR). Therefore, inf{ fλ : λ ∈ coreR(V ),R ∈ ∑ } ≥ u. Since V is an exact game so for each R ∈ ∑ , there is a λ ∈ coreR(V ). It follows by Lemma 3 fλ(CR) = u(CR). Hence, u = inf{ fλ : λ ∈ coreR(V ),R ∈ ∑ }. Theorem 5. Let u = inf{ fλ : S ∈ ∑ ,λ ∈ BAS ,λ(Ω) = V (Ω)}. Then the equation ∑ αRCR = βCT + (1− β)CΩ implies ∑ αRu(CR) ≤ βu(CT ) + (1− β)u(CΩ), where αR > 0, ∑ αR = 1,β ∈ [0,1] and T is a coalition. Proof. Consider R ∈ ∑ . Then u(CR) = fλ(CR) where, λ ∈ BAR is suitable element with λ(Ω) = V (Ω). It is easy to see that fλ(CΩ) = u(CΩ). Suppose that L denotes the segment connecting (CR,u(CR)) to (CΩ,u(CΩ)). Then L lies on the graph of fλ. Since cav(u) is concave, L is below the graph of cav(u). As cav(u) ≤ fλ, L is above the graph of cav(u). Thus, L is on the graph cav(u). Now by concavity of cav(u), ∑ R αRcav(u)(CR) ≤ cav(u)( ∑ R αRCR) = cav(u)(βCT + (1− β)CΩ) = βu(CT ) + (1− β)u(CΩ). That is ∑ R αRu(CR)≤ βu(CT ) + (1− β)u(CΩ). REFERENCES 193 References [1] Y Azrieli and E Lehrer. On concavification and convex games. Game Theory and Informa- tion 0408002, Economics Working Paper Archive at WUSTL. [2] G B Foland. Real Analysis: Modern Techniques and Their Applications (2nd edition). Wiley-Interscience/John Wiley Sons, Inc, 1999. [3] W Rudin. Functional analysis. McGraw-Hill Inc. Book company, New York, 1991. [4] D Schmeidler. Cores of exact games. J. Math. Anal. Appl 40: 214–225 1972. [5] D Schmeidler. Subjective probabilities without additivity. Econometrica 57: 571–587 1989. [6] L S Shapley. Cores of convex games. Int. J. Game Theory 1: 11–26 1971. [7] A W Tuker.Contributions to the theory of games. Princeton University press. Princeton, NJ, 307317.