A property of the undominated core for TU games (Mathematics of Decision Making under Uncertainty and Related Topics)
9
0
0
全文
(2) 45 game (N, v)\in\Gamma is a vector x\in \mathbb{R}^{N} that satisfies. x(N)=v(N) .. (1). The set of all pre‐imputations for a game (N, v)\in\Gamma is denoted by X(N, v) . An imputation for a game. (N, v)\in\Gamma. is a vector. x\in X(N, v). that satisfies. x_{i}\geq v(\{i\}) , \forall i\in N.. (2). I(N, v) is the set of all imputations for a game (N, v)\in\Gamma. A feasible vector for a game (N, v)\in\Gamma is a vector. x\in \mathbb{R}^{N}. that satisfies. x(N)\leq v(N) .. (3). The set of all feasible vectors for a game (N, v) is denoted by X^{*}(N, v) . Let. \sigma. be a mapping that. associates with every game (N, v)\in\Gamma' a set \sigma(N, v)\subseteq X^{*}(N, v) where \Gamma' is a subset of. \Gamma.. \sigma. is called. a solution on \Gamma'. Definition 2.1 A solution \sigma(N, v)\subseteq X(N, v). \sigma. on. \Gamma'. satisfies the Pareto optimality (PO) if for every game (N, v)\in\Gamma',. .. Definition 2.2 A solution. \sigma. on. \Gamma'. satisfies the individual rationality (IR) if for every game (N, v)\in\Gamma',. any x\in\sigma(N, v), x_{i}\geq v(\{i\}) for all i\in N.. For a game (N, v)\in\Gamma , define a game. (N, v^{-})by^{1}. v^{-}(S)= \min\{v(S), v(N)-\sum_{i\in N\backslash S}v(\{i\})\}, \foral S\underline{\subset}N, Definition 2.3 A solution. \sigma. on. \Gamma'. satisfies the property. I. (4). (PR‐I) if for games (N, v), (N, w)\in\Gamma' such. that v^{-}(S)\geq w^{-}(S) for all S\subset N , and v^{-}(N)=w^{-}(N), \sigma(N, v)\subseteq\sigma(N, w) .. For a game (N, v)\in\Gamma, x\in X^{*}(N, v) and S\subseteq N, a reduced game is a game (S, v_{S}^{x})\in\Gamma . Here. player set and v_{S}^{x} is the characteristic function which is defined by. Definition 2.4 A solution. \sigma. on. \Gamma'. \sum_{i\in S}v(\{i\}) for all. \sigma. on. \Gamma'. and. S. is the. S.. satisfies the reduced game property (RGP) if for a game (N, v)\in\Gamma',. any x\in\sigma(N, v) and any S\subset N, S\neq\emptyset,. Definition 2.5 A solution. v,. x. (S, v_{S}^{x})\in\Gamma' and x_{S}\in\sigma(S, v_{S}^{x}) .. satisfies the property II (PR‐II) if for a game (N, v)\in\Gamma', v(S)=. S\subseteq N , then x\in\sigma(N, v) , where x_{i}=v(\{i\}) for all i\in N.. 1In[6] , this game is expressed as (N, v') ..
(3) 46 3. Core for TU games. In this section the undominated core on. \Gamma. is characterized by axioms where the reduced game is. defined as follows.. Definition 3.1 For (N, v)\in\Gamma, x\in \mathbb{R}^{N} and S\underline{\subset}N , we define a reduced game (S, v_{S}^{x})\in\Gamma by. v_{S}^{x}(T)= \min\{v(T\cup(N\backslash S)), v(N)-\sum_{i\in S\backslash T} v(\{i\})\}-x(N\backslash S) =v^{-}(T\cup(N\backslash S))-x(N\backslash S) , \forall T\subseteq S, T\neq\emptyset,. (5). v_{S}^{x}(\emptyset)=0. Remark 3.2 This reduced game is a variation of the reduced game by Moulin [7]. The latter is used for characterizing the core (See [1\theta]). Definition 3.3 For a game (N, v)\in\Gamma and for. x,. y\in X(N, v),. x. dominates. y. via S\subset N if. x_{i}>y_{i}, \forall i\in S,. x(S)\leq v(S). (6). .. Definition 3.4 The undominated core of a game (N, v)\in\Gamma , denoted by DC(N, v) , is defined by. DC(N, v)= { x\in I(N, v) :. x. is not dominated by any y\in I(N, v) }.. (7). The core of a game (N, v)\in\Gamma , denoted by C(N, v) , is defined by. C(N, v)=\{x\in X(N, v) : x(S)\geq v(S), \forall S\subseteq N, S\neq\emptyset\} .. (8). The core and the undominated core were considered in Gillies [3]. The following is the main theorem of this paper.. Theorem 3.5 The undominated core is the only solution on. \Gamma. which satisfies RGP, IR, PR‐I, and. PR‐II.. To prove this theorem, we need 6 lemmas.. Lemma 3.6 The undominated core on. \Gamma. satisfies RGP.. Proof: It suffices to see when the unmoderated core is nonempty. For (N, v)\in\Gamma , suppose DC(N, v)\neq \emptyset and let x\in DC(N, v) . Hence x\in I(N, v) . For S\subset N, S\neq\emptyset , consider. x(S)=v(N)-x(N\backslash S)=v_{S}^{x}(S) .. (S, v_{S}^{x}) . By definition, (9).
(4) 47 Claim 3. 6A.. x_{i}\geq v_{S}^{x}(\{i\}). Proof of Claim 3.. |S|\geq 2 .. Assume. 6A :. for all i\in S.. If |S|=1 , that is, S=\{i\} then. x_{i}<v_{S}^{x}(\{i\}). v_{\{\}}^{x_{\dot{i}}}(\{i\})=x_{i}. because x\in I(N, v) . Let. for i\in S . Then. x(N\backslash S)+x_{i}<x(N\backslash S)+v_{S}^{x}(\{i\}) =v^{-}(\{i\}\cup(N\backslash S)). = \min\{v(\{i\}\cup(N\backslash S)), v(N)-\sum_{j\in S\backslash \{i\} v(\{j\}) \} \leq v(N)-\sum_{j\in S\backslash \{i\} v(\{j\}). (10). .. From this,. x(N \backslash S)+x_{i}+\sum_{j\in S\backslash \{i\} v(\{j\})<v(N)=x(N) .. (11). \sum_{j\in S\backslash \{i\} v(\{j\})<x(S\backslash \{i\}) .. (12). That is,. This implies that there exists j^{*}\in S\backslash \{i\} such that. x_{j^{*}}>v(\{j^{*}\}) .. (13). Define z\in \mathbb{R}^{N} by. where \delta and. \varepsilon. z_{j}=\{begin{ar y}{l x_{j}+\varepsilon, ifj\n{i\}cup(N\backslahS); x_{j}*-\delta, ifj=^{*}; x_{j}, otherwise, \end{ar y}. (14). are determined so that. 0< \delta=\varepsilon|\{i\}\cup(N\backslash S)|<\min\{x_{j}*-v(\{j^{*}\}), v^{- }(\{i\}\cup(N\backslash S))-x(\{i\}\cup(N\backslash S))\} . Then. z\in I(N, v). and. z. dominates. completes the proof of Claim 3.. From Claim 3.. 6A. x. \{i\}\cup(N\backslash S). via. in. (N, v) .. This contradicts. x\in DC(N, v) .. (15) This. 6A. \square. and (9), we see (S, v_{S}^{x})\in\Gamma_{I} and x_{S}\in I(S, v_{S}^{x}) . We shall show x_{S}\in DC(S, v_{S}^{x}) .. Assume that y\in I(S, v_{S}^{x}) dominates. x_{S}. via T\subset S in (S, v_{S}^{x}) . That is,. y(S)=v_{S}^{x}(S)=x(S). ,. y_{\dot{i}}\geq v_{S}^{x}(\{i\})=v^{-}(\{i\}\cup(N\backslash S))-x(N\backslash S), \forall i\in S, y_{i}>x_{i}, \forall i\in T,. y(T)\leq v_{S}^{x}(T)=v^{-}(T\cup(N\backslash S))-x(N\backslash S). .. (16).
(5) 48 We let Q\equiv\{i\in S\backslash T:x_{i}>v(\{i\})\} and P\equiv\{i\in S\backslash T:x_{i}=v(\{i\})\} . By (16), x(T)+x(N\backslash S)<y(T)+x(N\backslash S). \leq v^{-}(T\cup(N\backslash S))\equiv\min\{v(T\cup(N\backslash S)), v(N)- \sum_{i\in S\backslash T}v(\{i\})\} \leq v(N)-\sum_{i\in S\backslash T}v(\{i\}). (17). .. This implies. \sum_{i\in S\backslash T}v(\{i\})<v(N)-x(T)-x(N\backslash S)=x(S\backslash T) .. (18). Hence there exists i\in S\backslash T such that x_{i}>v(\{i\}) . That is, Q\neq\emptyset . Define z\in \mathbb{R}^{N} as follows.. z_{i}=\begn{ary}l x_{i+\varepslon_{i},f\nNbackslhS; y_{\doti}-ela_{\doti},f\nT; v({i\}),fnP; x_{i}-\etado{i},f\nQ ed{ary}. where. (19). 0<\delta_{i}<y_{i}-x_{i}, \forall i\in T,. \varepsilon_{i}>0, \forall i\in N\backslash S, (20). 0<\eta_{i}\leq x_{i}-v(\{i\}), \forall i\in Q. y(T)-x(T)-\delta(T)+\varepsilon(N\backslash S)=\eta(Q) \varepsilon(N\backslash S)\leq\delta(T) Indeed, we can find \delta_{i}, \varepsilon_{i} and. \eta_{\dot{i}. ,. .. which satisfy (20) as follows. Since x(Q)- \sum_{i\in Q}v(\{i\})>0 , choose. k\geq 2 so that. 0< \frac{y(T)-x(T)}{k}\leq x(Q)-\sum_{\dot{i}\in Q}v(\{i\}). .. (21). Second, choose \eta_{\dot{i}}>0, \forall i\in Q so that. \eta(Q)=\frac{y(T)-x(T)}{k}>0 and \eta_{i}\leq x_{i}-v(\{i\}), \forall i\in Q . Choose \delta_{i}>0,. i\in T. so that. y_{i}-x_{i}- \delta_{i}<\frac{\eta(Q)}{|T|} for all. i\in T .. (22). This implies y(T)-x(T)-\delta(T)<\eta(Q) .. Finally, determine \varepsilon_{i}>0, i\in N\backslash S so that the equality in (20) is satisfied. Then. \varepsilon(N\backslash S)-\delta(T)=\eta(Q)-[y(T)-x(T)]= (\frac{1}{k}-1)[y(T) -x(T)]\leq 0 .. (23).
(6) 49 So (20) is feasible with respect to \delta_{i}, \varepsilon_{i} and. \eta_{i} .. From (19) and (20). z(N)=x(N \backslash S)+\varepsilon(N\backslash S)+y(T)-\delta(T)+\sum_{i\in P}v (\{i\})+x(Q)-\eta(Q) =x(N)=v(N). .. z(T\cup(N\backslash S))=y(T)+x(N\backslash S)-\delta(T)+\varepsilon(N\backslash S). \leq v_{S}^{x}(T)+x(N\backslash S)-\delta(T)+\varepsilon(N\backslash S). (24). = \min\{v(T\cup(N\backslash S)), v(N)-\sum_{i\in S\backslash T}v(\{i\})\}- \delta(T)+\varepsilon(N\backslash S) \leq\min\{v(T\cup(N\backslash S)), v(N)-\sum_{i\in S\backslash T}v(\{i\})\} \leq v(T\cup(N\backslash S)). .. From (19) and (20), we see z_{i}\geq v(\{i\}) for all z. dominates. x. i\in N .. From this and (24), z\in I(N, v) . Consequently,. via T\cup(N\backslash S) in (N, v) , which contradicts x\in DC(N, v) . This completes the proof. of Lemma 3.6. \square. Lemma 3.7 The undominated core on. \Gamma. satisfies IR, PO ,PR‐I and PR‐II.. Proof: By definition, the undominated core satisfies IR and PO. It is known (Rafels/Tijs(1997)) that for any game (N, v) such that I(N, v)\neq\emptyset, DC(N, v)=C(N, v^{-}) . By the definition of the core, C(N, v^{-})\subseteq C(N, w^{-}) for any (N, v), (N, w) such that v^{-}(S)\geq w^{-}(S) for all S\subset N , and. v^{-}(N)=w^{-}(N) . Since I(N, v)\neq\emptyset , we have I(N, w)\neq\emptyset , which implies DC(N, w)=C(Nw^{-}) . Hence DC(N, v)\subseteq DC(N, w) and the unmoderated core satisfies PR‐I. It satisfies PR‐II since any \square. imputation can not dominate itself.. Lemma 3.8 If a \mathcal{S} olution. \sigma. on. \Gamma. satisfies RGP and IR, then it satisfies PO.. Proof: For (N, v)\in\Gamma , let x\in\sigma(N, v) . By RGP and IR,. x_{i} \geq v_{\{\dot{i}\} ^{x}(\{i\})=\min\{v(\{i\}\cup(N\backslash \{i\}) , v(N)-\sum_{j\in\{i\}\backslash \{i\} v(\{j\})\}-x(N\backslash \{i\}) =v(N)-x(N\backslash \{i\}). From this, x(N)\underline{>}v(N) . Since \sigma(N, v)\underline{\subset}X^{*}(N, v), x(N)\underline{<}v(N) . Hence we have x(N)=v(N) .. Lemma 3.9 If a solution all. (N, v)\in\Gamma.. \sigma. on. (25). .. \Gamma \mathcal{S} atisfies. \square. RGP, IR, PR‐I and PR‐II, then DC(N, v)\subseteq\sigma(N, v) for.
(7) 50 Proof: Suppose that a solution. \sigma. satisfies RGP, IR and PR‐I. For (N, v)\in\Gamma , if DC(N, v)=\emptyset. , then it trivially holds. Suppose DC(N, v)\neq\emptyset . So I(N, v)\neq\emptyset . Let x\in DC(N, v)\subseteq I(N, v) . Since DC(N, v)=C(N, v^{-}), x\in C(N, v^{-}) . Hence, x(S)\geq v^{-}(S) for all S\subseteq N . Define a game. (N, v_{x})\in\Gamma by v_{x}(S)=x(S) for all S\subseteq N . Since x(S)=v_{x}(S) for all S\subseteq N and (v_{x})^{-}=v_{x} , we have (v_{x})^{-}(S)\geq v^{-}(S) for all S\subseteq N and (v_{x})^{-}(N)=v^{-}(N)=v(N) . By PR‐I, \sigma(N, v_{x})\subseteq\sigma(N, v) . By the assumption and by Lemma 3.8,. x\in\sigma(N, v_{x}) . Hence, x\in\sigma(N, v) . Lemma 3.10 Suppose that. \sigma(N, v)\subseteq C(N, v). \sigma. on. \sigma. satisfies IR and PO. That is, \sigma(N, v_{x})\underline{\subset}I(N, v_{x}) . By PR‐II,. \square \Gamma. satisfies RGP and IR. If v(S)=v^{-}(S) for all S\subseteq N then. .. Proof: Let x\in\sigma(N, v) . By RGP, x_{S}\in\sigma(S, v_{S}^{x} ) for all S\subseteq N . By IR, x_{i}\geq v_{S}^{x}(\{i\}) for all i\in S. Since v(S)=v^{-}(S) for all S\subseteq N , we have. v(S) \leq v(N)-\sum_{j\in N\backslash S}v(\{j\}). v_{S}^{x}(\{i\})=v(\{i\}\cup(N\backslash S))-x(N\backslash S) for all i\in S .. i\in S .. for all S\subseteq N . This implies. Hence, x(N\backslash S)+x_{i}\geq v(\{i\}\cup(N\backslash S)) for all. This implies x(T)\geq v(T) for all T\subseteq N since. \{\{i\}\cup(N\backslash S) : i\in S, S\subseteq N\}=\{T\subseteq N\} . Hence we have. x\in C(N, v) .. Lemma 3.11 If a solution. (26). \square. \sigma. on. \Gamma. satisfies RGP, IR and PR‐I, then \sigma(N, v)\subseteq DC(N, v) for all. (N, v)\in\Gamma. Proof: Assume I(N, v)\neq\emptyset . Since (v^{-})^{-}(S)=v^{-}(S) for all S\subseteq N , by PR‐I and Lemma 3.10 we have. \sigma(N, v)=\sigma(N, v^{-}). and. \sigma(N, v^{-})\subseteq C(N, v^{-}) .. Then. C(N, v^{-})=DC(N, v) .. Hence. \sigma(N, v)\subseteq. DC(N, v) . Next assume I(N, v)=\emptyset . By Lemma 3.8 and IR, \sigma(N, v)\subseteq I(N, v)=\emptyset . Hence \sigma(N, v)=. \emptyset\subset DC(N, v). .. \square. From Lemmas 3.6 and 3.7, the undominated core satisfies all properties in the statement of the theorem. From Lemma 3.9 and 3.11, a solution on. \Gamma. must coincide with the undominated core if it. satisfies all properties in the statement of the theorem. This completes the proof of the theorem.. \square. The next examples show that the properties in Theorem 3.5 are independent.. Example 3.12 Let PR‐II. Let. \sigma^{1}(N, v)=I(N, v) for all (N, v)\in\Gamma . By definition,. N=\{1,2,3\}. x=(1,2,0)\in I(N, v) .. and. v(N)=3, v(13)=v(23)=2, v(12)=1. Let. S=\{1,2\} .. We see. and. \sigma^{1}\mathcal{S} atisfies IR, PR‐I and. v(i)=0. for i=1,2,3 . Then. x_{\{1,2\}}\not\in I(\{1,2\}, v_{\{1,2\}}^{x})=\sigma^{2}(\{1,2\}, v_{\{1,2\}}^ {x}). because. v_{\{1,2\}}^{x}(\{1\})=2>x_{1}=1 . Hence it does not satisfy RGP. Example 3.13 Let not satisfy PR‐II.. \sigma^{2}(N, v)=\emptyset for all (N, v)\in\Gamma . Then. \sigma^{2} satisfies IR,PR‐I and RGP. But it does.
(8) 51 51 Example 3.14 Let. \sigma^{3}(N, v)=C(N, v) for all (N, v)\in\Gamma . By definition_{f}\sigma^{3}\mathcal{S}atisfie\mathcal{S} IR and PR‐. II. Let’s see it satisfies RGP. Let x\in C(N, v) . Then by definition, v_{S}^{x}(S)=x(S) for all S\subseteq N.. x(T)=x((N\backslash S)\cup T)-x(N\backslash S)\underline{>}v((N\backslash S) \cup T)-x(N\backslash S)\geq v_{S}^{x}(T). for all T\subseteq S .. Hence. x_{S}\in C(N, v_{S}^{x}) . Next, let’s see it does not satisfy PR‐I. For N=\{1,2,3\} , let v(i)=w(i)=0 for i=1,2,3 and v(N)=w(N)=5 . Let v(12)=w(12)=2 and v(13)=w(13)=3 . Let v(23)=5 and. w(23)=6 . Then C(N, v)=\{(0,2,3)\} and C(N, w)=\emptyset , while v^{-}(S)=w^{-}(S) for all S\underline{\subset}N. Example 3.15 Let. \sigma^{4}(N, v)=\{x\in X^{*}(N, v) : x_{i}\leq v(N)-v^{-}(N\backslash \{i\}), \forall i\in N\} for all (N, v)\in\Gamma.. For \mathcal{S} ufficiently large \varepsilon>0, y_{\dot{i}}\equiv v(N)-v^{-}(N\backslash \{i\})-\varepsilon<v(\{i\}) for some. i\in N. as well as. y(N)\leq v(N) , but y\in\sigma^{4}(N, v) . So \sigma^{4}(N, v) does not sati_{\mathcal{S}fy} IR. Suppose v^{-}(S)\geq w^{-}(S) for all S\subseteq N and v^{-}(N)\geq w^{-}(N) . Then v(N)=w(N) and v(N)-v^{-}(N\backslash \{i\})\leq w(N)-w^{-}(N\backslash \{i\}) for all. \sigma^{4}(N, v)\subseteq\sigma^{4}(N, w) . Hence \sigma^{4} satisfies PR‐I. Next suppose v(S)= \sum_{i\in S}v(\{i\}) for all S\subseteq N . Then \sigma^{4}(N, v)=\{x\in X^{*}(N, v) : x_{i}\leq v(\{i\}), \forall i\in N\} , which implies x\in\sigma^{4}(N, v) where x_{i}=v(\{i\}) for all i\in N . Hence \sigma^{4} satisfies PR‐II. Next suppose x\in\sigma^{4}(N, v) . Let S\subseteq N. i\in N .. This implies. Since x(N)\leq v(N) , it holds x(S)\leq v(N)-x(N\backslash S)=v_{S}^{x}(S) .. v_{S}^{x}(S)-(v_{S}^{x})^{-}(S \backslash \{i\})=v_{S}^{x}(S)-\min\{v_{S}^{x}(S \backslash \{i\}), v_{S}^{x}(S)-v_{S}^{x}(\{i\})\} = \max\{v_{S}^{x}(S)-v_{S}^{x}(S\backslash \{i\}), v_{S}^{x}(\{i\})\}. (27). Here. v_{S}^{x}(S)-v_{S}^{x}(S \backslash \{i\})=v(N)-\min\{v((S\backslash \{i\})\cup (N\backslash S)), v(N)-v(\{i\})\} = \max\{v(N)-v((S\backslash \{i\})\cup(N\backslash S)), v(\{i\})\}. (28). So. v_{S}^{x}(S)-(v_{S}^{x})^{-}(S \backslash \{i\})=\max\{v(N)-v(N\backslash \{i\} ), v(\{i\}), v_{S}^{x}(\{i\})\}. ) \max\{v(N)-v(N\backslash \{i\}), v(\{i\})\}. (29). =v(N)-v^{-}(N\backslash \{i\}) Hence. x_{S}\in\sigma^{4}(S, v_{S}^{x}) .. So \sigma^{4} satisfies RGP.. References. [1] Bejan C and Gomez JC (2012) Axiomatizing core extensions. International Journal of Game Theory 41, 885‐898.. [2] Chang C (2000) Note: remarks on the theory of the core. Naval Research Logistics 47, 456‐458. [3] Gillies D. (1959) Solutions to general non‐zero sum games. In: Tucker A and Luce R (eds),. Contributions to the theory of games, vol.IV, Annals of Math. Studies, 40,Princeton University Press, 47‐58..
(9) 52 [4] Grabish M and Sudhölter P (2012) The bounded core for games with precedence constraints. Annals of Operations Research 201, 251‐264.. [5] Izquierdo J.M. and Rafels C (2018) The core and the steady bargaining set for convex games. International Journal of Game Theory 47, 35‐54.. [6] Llerena F and Rafels C (2007) Convex decomposition of games and axiomatizations of the core and the. D ‐core.. International Journal of Game Theory 35, 603‐615.. [7] Moulin H (1985) The separability axiom and equal sharing methods. Journal of Economic Theory 36,187‐200.. [8] Peleg B and Sudhölter P. (2003) Introduction to the Theory of Cooperative Games. Kluwer. Academic Publishers, Boston,MA.. [9] Rafels C and Tijs S (1997) On the cores of cooperative games and the stability of the Weber set. International Journal of Game Theory 26, 491‐499.. [10] Tadenuma K (1992) Reduced games, consistency and the core. International Journal of Game Theory 20, 325‐334. Kensaku Kikuta. Professor Emeritus, School of Business Administration, University of Hyogo E‐mail address: kenkikuta@gmail.com.
(10)
関連したドキュメント
For example, a maximal embedded collection of tori in an irreducible manifold is complete as each of the component manifolds is indecomposable (any additional surface would have to
Indeed, if we use the indicated decoration for this knot, it is straightforward if tedious to verify that there is a unique essential state in dimension 0, and it has filtration
It is suggested by our method that most of the quadratic algebras for all St¨ ackel equivalence classes of 3D second order quantum superintegrable systems on conformally flat
In Section 3, we show that the clique- width is unbounded in any superfactorial class of graphs, and in Section 4, we prove that the clique-width is bounded in any hereditary
In this paper, under some conditions, we show that the so- lution of a semidiscrete form of a nonlocal parabolic problem quenches in a finite time and estimate its semidiscrete
Inside this class, we identify a new subclass of Liouvillian integrable systems, under suitable conditions such Liouvillian integrable systems can have at most one limit cycle, and
This paper develops a recursion formula for the conditional moments of the area under the absolute value of Brownian bridge given the local time at 0.. The method of power series
Then it follows immediately from a suitable version of “Hensel’s Lemma” [cf., e.g., the argument of [4], Lemma 2.1] that S may be obtained, as the notation suggests, as the m A
