Yeremia Maroutian
1710, Prospect Ave. Cleveland, Oh. 44115
Correspondence to: Yeremia Maroutian , 1710, Prospect Ave. Cleveland, Oh. 44115.
Email: | |
Copyright © 2017 The Author(s). Published by Scientific & Academic Publishing.
This work is licensed under the Creative Commons Attribution International License (CC BY).
http://creativecommons.org/licenses/by/4.0/
Abstract
In this paper invented by D. Schmeidler (1969) for characteristic function games concept of nucleolus has been extended on fuzzy cooperative games. The fuzzy pre-nucleolus defined by a new way. On the set of classical cooperative games proved its coincidence with the already existed one. For a class of fuzzy games the pre-nucleolus exists and unique. The process of finding of pre-nucleolus illustrated on an example of a fuzzy game.
Keywords:
Fuzzy cooperative games, Fuzzy coalition, Fuzzy pre-nucleolus
Cite this paper: Yeremia Maroutian , The Pre-nucleolus for Fuzzy Cooperative Games, Journal of Game Theory, Vol. 6 No. 2, 2017, pp. 43-51. doi: 10.5923/j.jgt.20170602.03.
1. Introduction
Let N= {1, 2… n} be the set of all players. A fuzzy coalition is an n-dimensional vector with for each . A cooperative fuzzy game with the players set N is a pair (T, v), where is the set of all fuzzy coalitions and v is the characteristic function of that game which maps a real number to each fuzzy coalition.Cooperative fuzzy games reflect situations in which for players allowed to take part in a coalition with participation levels that may vary from non-cooperation to full cooperation. The obtained reward in this type of games defines depending on the level of cooperation. Participation levels at which players involved in cooperation gets described by fuzzy coalitions. Aubin (1981) has been explaining use of fuzzy coalitions by following way when he first introduced them in game theory. Every player can choose his level of participation in a coalition instead of whether to participate in it or not. As an example in favor of that approach can be considered case, when individual players reluctant to invest all of the available resources in enterprise where that coalition involved. For fuzzy cooperative theory extension of classical decision concepts on fuzzy games is an important topic. It is known, that not every concept of classical theory has its natural counterpart for fuzzy games. At the same time some results in classical cooperative games allow to be transformed on fuzzy games with of course significant differences. In this work we aimed to establish an important in classical theory optimality principle, i.e. nucleolus on fuzzy games.
2. Basic Definitions and Results
Together with fuzzy theory of nucleolus we are also going to deal with the classical version of the same concept. For that reason we need to reproduce here some preliminary facts from the classical theory of nucleolus. At the end of this paragraph we will bring the definition of nucleolus for fuzzy cooperative games.For classical cooperative games D. Schmeidler [1] has defined nucleolus as an imputation what is the best in the sense of a preference relation . To define the nucleolus we need the following notations. For the game and the imputation denote .Let is a classical cooperative game and is the set of all imputations for the game G.The difference is the excess of coalition S regarding to x. Defined that way excess can be interpreted as a measure for complain of coalition S from imputation x. Let consider the vector of excesses with components:From the definition of it is clear, that the components of ordered decreasingly. For the game v on the set defined a quasi-order the following way. Let if where is for the lexicographical order. It means, exist a number such that Definition 2.1 For and characteristic function v, the set is nucleolus for Y if vectors from are minimal in the sense of relation i.e.Theorem (D. Schmeidler, 1969). For every nonempty, convex and compact set the nucleolus exists and consists of only one vector. Theorem (A. Sobolev, 1976) Let for a game as a set of payoff vectors defined the set of pre-imputaions:Then the game G has a nonempty pre-nucleolusthat contains only one vector. For outcomes from the condition of individual rationality has been violated. For that reason the set of payoff vectors is not compact and hence, it is different of the set of imputations. Despite of that the statement about existence and uniqueness for pre-nucleolus continues to remain true. Fuzzy cooperative games possess infinite number of coalitions. That fact does not allow using the approach based on idea of lexicographic order to extend this concept on fuzzy games. From there arrives a need for a new definition of pre-nucleolus on fuzzy games. To be valid the needed definition should coincide with the existing one for classical games and at the same time to allow extending that concept on fuzzy cooperative games. Let (T, v) is an arbitrary fuzzy game, where is the set of all fuzzy coalitions and is the characteristic function of that game.Below we will prove that the newly defined pre-nucleolus coincides with already existing one. We will consider the set of only collectively rational payoff vectors, i.e. pre-imputations:Inductively defined sets X_{k}, T_{k} by accepting that | (3.1) |
For we will define sets X_{k}_{+1} the following way | (3.2) |
and sets T_{k} for | (3.3) |
where and is the distance between the point and set T_{k}:For sets true the following: when k increases, T_{k} does not decrease: If for some k_{0} it is turning out that then that entails the stabilization of corresponding set or otherwise, by increasing k, X_{k} does not decrease any more. The set obtained that way we will call the prenucleolus for fuzzy game (T, v).
3. About the Pre-Nucleolus for Classical Cooperative Games
In this paragraph first will be described the new definition of pre-nucleolus for the set of classical cooperative games. For that type of games below has been proved that pre-nucleolus defined both of the ways coincide.Let the pair means a classical cooperative game, where is the set of all players and a characteristic function satisfying to the condition First, let pay attention that in case of classical cooperative games relations (3.1) - (3.3) accept the following view: | (3.4) |
| (3.5) |
| (3.6) |
Construction of sets X_{k}, T_{k} after finite number of steps will be abrupt because finite is the set 2^{N}. The last set X_{k} will contain a unique vector, coinciding with the pre-nucleolus in sense of its initial definition. Takes place the following lemma: Lemma 3.1. Let andif Proof: For a given vector according to definition we have that Let denote by Similarly,Further, for the components of let Let be an arbitrary coalition. If thenIf it takes place the strong inequality then the lemma’s statement proved.We will accept now, that for all takes place only equality. Let also assume, that for some k < n and for every where Let consider excess where . If thenI.e. Let now too and is some coalition:Again, if it takes place the strong inequality, then If for all k take place only equalities then x = y, which contradicts the condition of lemma.Let numbers are all of different values accepted by the components of vector Below we will deal with the sets and defined following way:Lemma 3.2. If then Proof. Let and be an arbitrary coalition. It is clear, that for some . According to definition of for every . But then which means that Lemma 3.3. For all exist numbers l_{k} and sets X_{k} such that Proof. For k = 1 the relation (3.7) follows from definitions of sets X_{1} and Y_{1}. Accept it already has been proved that for some k and l According to lemma 2 supposed to take place inclusion . If because then exists such that and Necessary to prove that it will entail the coinsidence of sets and Let now for some and . Then will exist set such that and . Subsequently, . Which means, that . Because so according to lemma 3.1,By the other side, as far as thenFrom there it follows that Further, because and is the first value of which is smaller than As a result,Or otherwise, Which means, that Let now prove the opposite inclusion, i.e. if then too. As far as and so for every where Besides that, for every . It is remaining to proof that for arbitrary Accept that for some coalition Let consider the vector For coalitions for and From there it follows that for a number small enough, and every Which means that the constructed above vector is more preferable than . That contradicts to the fact that ν(X) is pre-nucleolus for the game . Hence, for every supposed to hold true the equality But then the received equality would mean, that and The last inclusion concludes the proof of our lemma.Theorem. 3.1 There is a number q such that .Proof. Because for every so according to lemma 3.3, we will have, that also If contains more than one point then it is obvious that . Then based on lemma 3.3 and lemma 3.2, and according to lemma 1 we will be able to construct the next set . The constructed that way last set will consist of only the nucleolus .
4. Fuzzy Games with Finite Sets of Coalitions
4.1. Let is a fuzzy cooperative game, where is some finite set of fuzzy coalitions. Below we will prove that in presence of some conditions this type of games possess a unique prenucleolus. Lemma 4.1. Let X is a convex polytope and χ is the solution for the next linear programming problem:Then exists a vector such that for every Proof. Let for every exists a vector such thatwhere is the solution of mentioned above linear programming problem. Consider now the vector Because of convexity of the set and for every which contradicts to the condition that is the optimal solution for our minimization problem. So, exists a vector such that for every From there the assertion of lemma 3.4 follows. Theorem 4.1 Let is a fuzzy game, where is a finite set of fuzzy coalitions that also contains coalitions for arbitrary . Then the game possesses a unique pre-nucleolus.Proof. We need to prove that after finite number of steps the process of construction of sets X_{k}, T_{k} will be abrupt and the last set X_{k} will consists of a unique point.The set X_{1} is solution for the following minimization problem: | (3.8) |
In problem (3.8) the number bounded below. Really, if then Summing all these inequalities by we will obtain thatfrom where ,what has been required to prove.When accepts its minimal value we obtain the solution of our problem:The corresponding set is: Further we need to find the That is the same as solving the following minimization problem:The solution X_{2} for this problem is a convex politope and the set T_{2} strictly contains the set The same will take place on the following steps too. As far as the set is finite, so construction of sets X_{k}, T_{k} will be abrupt after finite number of steps.Let now . It is remaining to prove that . If then from will follow that for arbitrary from where x = y. That concludes the proof of our theorem.4.2. Fuzzy Games with Piece-Wise Affine Characteristic FunctionsBelow proved a theorem about existence and uniqueness of pre-nucleolus for fuzzy games with piece-wise affine characteristic functions.Theorem 4.2. Let (T, v) is a fuzzy cooperative game with piece-wise affine characteristic function v. That means, exists a collection of simplexes what covers , and for where is a linear function and . Then the game (T, v) has a pre-nucleolus that consists of a unique point.Proof. According to definitions of sets X_{k}, T_{k} The set X_{1} is the solution for following minimization problem: | (3.9) |
Let consider the following linear programming problem: (3.9')where the is the set of all peaks of simplexes Accept that the pair is the solution for that problem, where is a convex politope. It is clear that We will prove that also is solution for the problem (3.9). For that reason we will need to show that the inequality holds true for all when Let is an arbitrary coalition and is a simplex with peaks which contains Then where and Because is an affine function on so we will have thatFrom there, really is a solution for the problem (3.9). So, we will have that X_{1} is the following set:According to definition of sets for a fixed and every what means that the product is constant for every . Let now are such coalitions that and From there it will follow that if for some numbers and then for every The latter one means that set T_{m} is the intersection of the set of all coalitions T with some hyperplane and subsequently is a convex set, because of convexity of T.Next we will rewrite the definition of in a different form:The set defined that way is solution for the following maximization problem: | (3.10) |
As it was in the beginning of the proof besides this problem also let consider the corresponding linear programming problem for peaks of simplexes that does not belong to T_{m}_{-1}: (3.10’)The problem (3.10’) has a solution because it is a linear programming problem and X_{m}_{-1} is a convex polytope. Let denote that solution by and prove that inequalities (3.10’) remain true for all and . For the inequality (3.10’) follows from definition of sets X_{m}. For (3.10’) is true because for that kind of the right side of (5’) is equal to 0 and the left side is not negative as far as .Let now and Accept that is a simplex for what and are peaks for that simplex. According to the Karatheodory’s theorem:The last inequality in the chain above takes place because of convexity of metric by the variable As a result, has been proved that the solution for the problem (3.10’) also is solution for (3.10). From there according to lemma 4.1 exists such that and for arbitrary takes place equality in (3.10’). Then because and so As a result to that the dimension of T_{m} will increase by at least one. From there because as its proved above the sets T_{m} are convex, so after finite number of steps T_{m} will coincide with T and the corresponding set will contain only one point.4.3. An Example for Calculation of Pre-NucleolusThe paragraph below devoted to finding of the pre-nucleolus for fuzzy game from a parameterized class. Let considered a game with the following characteristic function It is clear that for this game v(1) =1 and Solving of the problem will start from dividing the square on eight triangle subsets and figureing out values of on each one of them. Let denote these subsets by (i =1… 8) and start to describe them.Based on inequalities that define it is obtained that and from there For are true the following inequalities: From what it follows that The definition of implies that for hold true the inequalities:So, for Analogically to in this case tooFurther, because From inequalities that define follows that for On hold true the following inequalities:To find sets X_{1} and T_{1} enough to calculate the following magnitude: whereLet now to calculate the magnitude of by the scheme below:Further by turn will be figured out magnitudes of the following inner maximums:Now, when the values for by subsets already have been found can be calculated value for the preliminary expression: Further, because for x with so from there it is clear that That value together with definition of the set gives that Let denote To find sets X_{2}, T_{2} should be calculated the magnitude of whereThe magnitude of also will be calculated by subsets , the same way as it has been done with the At the end it is remaining to calculate one more magnitude, which will give us the set X_{2}: So, as a result it obtaines that From there for the pre-nucleolus v(X) of initial game it follows that
Note
1) Results that included in this paper have been part of author’s doctoral dissertation written in early 1990’s. There is available a copyright certificate from the US Copyright Office.
References
[1] | SCHMEIDLER D. 1969. The nucleolus of a characteristic function game. –SIAM J. OF MATH. 1, vol. 17, pp. 1163-1170. |
[2] | SOBOLEV A. 1976. Characterization of the optimality principles in cooperative games by functional equations. – Math Methods in Social Sciences. - Vilnius, pp. 94-151. (In Russian). |
[3] | AUBIN JP, 1981. Cooperative fuzzy games. Math Oper.es 6: 1-13. |