9_522_cevikel.dvi EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 3, No. 1, 2010, 107-117 ISSN 1307-5543 – www.ejpam.com A linear Interactive Solution Concept for Fuzzy Multiobjective Games Adem C. Çevikel∗ and Mehmet Ahlatçıoğlu Yildiz Technical University, Art-Science Faculty, Department of Mathematics, Istanbul, Turkey Abstract. In this paper, we deal with multiobjective two-person zero-sum games with fuzzy payoffs and fuzzy goals. The aim of the paper is to explain new concepts of solutions for multiobjective two-person zero-sum games with fuzzy payoffs and fuzzy goals. We assume that each player has a fuzzy goal for each of the payoffs. A degree of attainment of the fuzzy goal is defined and the max-min strategy with respect to the degree of attainment of the fuzzy goal is examined. If all of the membership functions both for the fuzzy payoffs and for the fuzzy goals are linear, the max-min solution is formulated as a nonlinear programming problem. The problem can be reduced to a linear programming problem by making use of Sakawa’s method, the variable transformation by Charnes and Cooper and the relaxation procedure. 2000 Mathematics Subject Classifications: 03E72, 91A05, 91A80 Key Words and Phrases: Agragated fuzzy goal; Fuzzy numbers; Fuzzy payoff matrix; Nonlinear programming problem;Max-min solution; Multiple payoff matrices; Relaxation procedure; Two-person zero-sum games. 1. Introduction We consider multiobjective two-person zero-sum games with fuzzy payoffs and fuzzy goals.A payoff matrix with elements represented as fuzzy payoff matrix. For any pair of strate- gies, a player receives a payoff represented as a fuzzy number, i.e., the strategy itself is not fuzzy but the payoffs are fuzzy. For example, when a payoff matrix of a game is constructed by information from a competitive system, elements of the payoff matrix would be ambiguous if imprecision or vagueness exists in the information. this paper is related to the research fields both of multiobjective games and fuzzy games. Most of the studies on multiobjective games are on two-person games [5, 11, 13, 20] but recently a couple of articles have been de- voted to the studies of n-person multiobjective games [10, 21]. The research on fuzzy games has been develop by Aubin [1, 2] and Butnariu [6, 7]. Recently, Campos [8] has explored ∗Corresponding author. Email addresses: a evikel�yildiz.edu.tr (A. Çevikel), mahlat i�yildiz.edu.tr (M. Ahlatçıoğlu) http://www.ejpam.com 107 c© 2009 EJPAM All rights reserved. A. Çevikel, M. Ahlatçıoğlu / Eur. J. Pure Appl. Math, 3 (2010), 107-117 108 zero-sum fuzzy matrix game. The problem treated by Campos was a game with a single pay- off, and the min-max problem was formulated using the fuzzy mathematical programming method. Moreover, Sakawa and Nishizaki [14, 17] have explored zero-sum multiobjective fuzzy matrix games. In this paper, a new solution concept in a two-person zero-sum multiobjective fuzzy matrix game is proposed. In section 2, a fuzzy expected payoff is defined, and a degree of attainment of a fuzzy goal is considered in games with fuzzy payoff matrices. The max-min solution with respect to a degree of attainment of a fuzzy goal is also defined. In section 3, the method for computing the solution of a multiobjective game is proposed when membership functions of fuzzy goals and shape functions of L-R fuzzy numbers for fuzzy payoffs are linear. Cook’s example [12] for computing the max-min solution is formulated as a nonlinear programming problem, but it can be transformed to a linear programming problem by making use of the Sakawa’s method [18], by using the variable transformation by Charnes and Cooper [9] and the relaxtion procedure [19]. 2. Background Definition 1 (Zero-sum game with fuzzy payoffs). When Player I chooses a pure strategy i ∈ I and Player I I chooses a pure strategy j ∈ J, let eai j be fuzzy payoff for Player I and −eai j be a fuzzy payoff for Player I I. The fuzzy payoff eai j is represented by the L-R fuzzy number : eai j = � ai j , a′i j , ài j � LR (1) where ai j is a mean value, a′i j is a left spread and ài j is a right spread. The two-person zero-sum fuzzy game can be represented as a fuzzy payoff matrix : eA=   ea11 ... ea1n ... ... ... eam1 ... eamn   (2) The game defined by (2) is called a two-person zero-sum game with fuzzy payoffs. When each of the players chooses a strategy, a payoff for each of them is represented as a fuzzy number, but an outcome of the game has a zero-sum structure such that, when one player receives a gain the order player suffers an equal loss. Assuming that each of the two players has r objectives, the following multiple fuzzy payoff matrices represent a multiobjective two-person zero-sum game with fuzzy payoffs : eA1 =   ea1 11 ... ea1 1n ... ... ... ea1 m1 ... ea1 mn   , ..., eAr =   ear 11 ... ear 1n ... ... ... ear m1 ... ear mn   (3) A fuzzy payoff can be extended to a fuzzy expected payoff by using mixed strategies in a procedure similar to the extension from a payoff to an expected payoff in conventional two- person zero-sum games. A. Çevikel, M. Ahlatçıoğlu / Eur. J. Pure Appl. Math, 3 (2010), 107-117 109 Definition 2 (Fuzzy expected payoff). For any pair of mixed strategies x ∈ X and y ∈ Y , the kth fuzzy expected payoff of Player I is defined as the fuzzy number x eAk y =   m∑ i=1 n∑ j=1 ak i j x i y j , m∑ i=1 n∑ j=1 a′ki j x i y j , m∑ i=1 n∑ j=1 àk i j x i y j   LR (4) characterized by the membership function µx eAk y : Dk→ [0,1] (5) where Dk ∈ R is the domain of the kth payoff for Player I . Definition 3 (Fuzzy goal). Let the domain of the kth payoff for Player I be denoted Dk ∈ R . Then the fuzzy goal s G k with respect to the kth payoff for Player I is defined as the fuzzy set on the set Dk characterized by the membership function µeGk : Dk→ [0,1] (6) A membership function value of a fuzzy goal can be interpreted as a degree of attainment of the fuzzy goal. Then we assume that, for any pair of payoffs, a player prefers the payoff having the greater degree of attainment of the fuzzy goal to the other payoff.[15] Definition 4 (A degree of attainment of a fuzzy goal). For any pair of mixed strategies (x , y), let the kth fuzzy expected payoff for Player I be denoted by x eAk y and let the kth fuzzy goal for Player I be denoted by s G k . Then a fuzzy set expressing an attainment state of the fuzzy goal is represented by the intersection of the fuzzy expected payoff x eAk y and the fuzzy goal s G k . The membership function of the fuzzy set is represented as µk a(x ,y) (p) =min(µx eAk y(p),µeGk (p)) (7) where p ∈ Dk is a payoff for Player I. A degree of attainment of the kth fuzzy goal is defined as the maximum of the membership function (7), i.e., ⌢ µ k a(x ,y)(p ∗) =max p µk a(x ,y) (p) =max p n min(µx eAk y(p),µeGk(p)) o (8) A degree of attainment of the fuzzy goal can be consider to be a concept similar to a degree of satisfaction of the fuzzy decision by Bellman and Zadeh [4] when the fuzzy constraint is replaced by the fuzzy expected payoff, and it can be also interpreted as a possibility of attainment of the fuzzy goal. When Player I and I I choose mixed strategies ⌢ x and ⌢ y, respectively, the degree of attainment of the kth fuzzy goal ⌢ µ k a(x ,y)(p ∗) is determined by (8). We assume that Player I supposes that Player I I choose a strategy ⌢ y so as to minimize Player I ’s degree of attainment of the aggregated fuzzy goal ⌢ µ a( ⌢ x , ⌢ y ) (p∗), i.e., Player I ’s degree of attainment of the aggregated A. Çevikel, M. Ahlatçıoğlu / Eur. J. Pure Appl. Math, 3 (2010), 107-117 110 fuzzy goal, assuming he choose ⌢ x , will be v(x) = miny∈Y ⌢ µ a( ⌢ x , ⌢ y ) (p∗). Hence,Player I chooses a strategy so as to maximize his degree of attainment of the aggregated fuzzy goal v(x). In short, we assume that Player I behaves according to the maximin principle in terms of a degree of attainment of the aggregated fuzzy goal [16]. Definition 5 (Maximin solution with respect to a degree of attainment of the aggregated fuzzy goal). For any pair of mixed strategies (x , y), let a degree of attainment of the aggregated fuzzy goal for Player I be denoted ⌢ µa(x ,y)(p ∗). Then Player I ’s maximin value with respect to a degree of attainment of the aggregated fuzzy goal is max x∈X min y∈Y ⌢ µa(x ,y)(p ∗) (9) and such a strategy x is called the maximin solution with respect to the degree of attainment of the aggregated fuzzy goal. The maximin solution can be consider to be the solution maximizing the function, which is the minimal value of the function with respect to the opponent’s decision variables. We assume that a player has no information about his opponent or the information is not useful for the decision making if he has. We can also consider Player I I ’s minimax solution with respect to a degree of attainment of the aggregated fuzzy goal in a similar way. 3. Solution Concept We show a new method for computing the max-min solution of multiobjective game. 3.1. Multiobjective Two-person Zero-sum Games with Fuzzy Payoffs and Fuzzy Goals. Consider multiobjective two-person zero-sum games with fuzzy payoffs eAk, k = 1, .., r. We assume that a player has a fuzzy goal for each of the objectives, which expresses the player’s degree of satisfaction for the payoff. Let Player I ’s membership function of the fuzzy goal for the kth objective be denoted by µeGk (pk) for the kth payoff pk. When the membership function µeGk(pk) of the fuzzy goal is linear, it can be represented as µeGk(p k) =    0 1− ak−pk ak−ak 1 if pk < ak if ak ≤ pk ≤ ak if ak < pk    (10) where, for the kth objective, ak is the payoff giving the worst degree of satisfaction for Player’s I and ak is the payoff giving the best degree of satisfaction for Player I ’s. Morever, when the membership function µeak i j (pk) of the element eak i j, which is a fuzzy A. Çevikel, M. Ahlatçıoğlu / Eur. J. Pure Appl. Math, 3 (2010), 107-117 111 number, of the fuzzy payoff matrix eAk for the kth objective is linear, it can be represented as µeak i j (pk) =    0 (pk − ak i j + ák i j ) �ák i j (ak i j + àk i j − pk) �àk i j 0 if pk < ak i j − ák i j if ak i j − ák i j ≤ pk < ak i j if ak i j ≤ pk ≤ ak i j + àk i j if ak i j + àk i j < pk    (11) In general, the degree of attainment of the fuzzy goal can be represented as the following vector expression:   max p1 min(µx eA1 y(p 1),µeG1(p1)) ............................... max pr min(µx eAr y(p r),µeGr (pr))   . (12) For such a problem, we employ the fuzzy decision rule by Bellman and Zadeh [4], as an aggregation rule of multiple fuzzy goals in a way similar to the previous subsection. Then the membership function of the aggregated fuzzy goal is expressed as ⌢ µa(x ,y)(p ∗) =min k∈K max pk min(µx eAk y(p k),µeGk(p k)), (13) where p∗ = (p1∗ , ..., pr∗ ). Then, Player I ’s maximin value with respect to a degree of attain- ment of the aggregated fuzzy goal is represented as max x∈X min y∈Y ⌢ µa(x ,y)(p ∗) =max x∈X min y∈Y min k∈K max pk min(µx eAk y(p k),µeGk (pk)). (14) When membership functions are linear, the maximin strategy with respect to a degree of attainment of the aggregated fuzzy goal can be obtained by solving the mathematical pro- gramming problem in the following theorem. Theorem 1. For multiobjective two-person zero-sum games, if membership functions of the fuzzy goal and shape functions of L-R fuzzy numbers for fuzzy payoffs are linear such as (10) and (11), Player I ’s maximin solution with respect to a degree of attainment of the aggregated fuzzy goal is equal to an optimal solution to the nonlinear programming problem: maximize x ,σ σ sub ject to m∑ i=1 n∑ j=1 (ak i j +àk i j )xi y j−ak m∑ i=1 n∑ j=1 àk i j xi y j+ak−ak ≥ σ, ∀y ∈ Y, k = 1, ..., r m∑ i=1 x i = 1 x i ≥ 0, i = 1, ..., m (15) if the optimal value σ∗ satisfies 0≤ σ∗ ≤ 1 [14, 17]. A. Çevikel, M. Ahlatçıoğlu / Eur. J. Pure Appl. Math, 3 (2010), 107-117 112 We can calculate the maximin solution with respect to a degree of attainment of the fuzzy goal by applying a method using the relaxation procedure by Shimizu and Aiyoshi [19], in a process similar to a single-objective case and then we obtain the maximin solution. Consider the following relaxed problem for problem (15) by taking L points y l , l = 1, ..., L satisfying y l ∈ Y, i.e., n∑ j=1 y l j = 1, y l j ≥ 0, j = 1, ..., n. maximize x ,σ σ sub ject to m∑ i=1 n∑ j=1 (ak i j +àk i j )xi y l j −ak m∑ i=1 n∑ j=1 àk i j xi y l j +ak−ak ≥ σ, l = 1, ..., L, k = 1, ..., r m∑ i=1 x i = 1 x i ≥ 0, i = 1, ..., m (16) Let σ = ⌢ σ, where ⌢ σ is a constant value in [0,1]. Then the constraints of the relaxed problem (16) become as follows: m∑ i=1 n∑ j=1 (ak i j + àk i j)x i y l j − ak ≥ ⌢ σ( m∑ i=1 n∑ j=1 àk i j x i y l j + ak − ak), l = 1, ..., L, k = 1, ..., r m∑ i=1 x i = 1 x i ≥ 0, i = 1, ..., m , (17) we can find maximal constant value ⌢ σ satisfying the constraints (17). m∑ i=1 n∑ j=1 (ak i j + àk i j )x i y l j − ak = Pk l m∑ i=1 n∑ j=1 àk i j x i y l j + ak − ak = Qk l , (18) the first constraint of the relaxed problem (16) is equivalent to following condition Pk l Qk l ≥ σ, k = 1, ..., r, l = 1,2, ..., L (19) We can find the maximal constant value ⌢ σ of the problem (17) by making use of the Dinkel- A. Çevikel, M. Ahlatçıoğlu / Eur. J. Pure Appl. Math, 3 (2010), 107-117 113 bach algorithm [3] as follows: maximize r sub ject to Pk l − ⌢ σtQ k l − r ≥ 0 ( m∑ i=1 n∑ j=1 (ak i j + àk i j )x i y l j − ak)− Pk l = 0, ( m∑ i=1 n∑ j=1 àk i j x i y l j + ak − ak)−Qk l = 0 m∑ i=1 x i = 1 x i ≥ 0, k = 1, ..., r, l = 1,2, ...L, t = 1,2, ..., T (20) Where we have denoted ⌢ σt = min § Pk l Qk l ª and ⌢ σ1 = 0 . If maximize r = 0, terminate, then the feasible solution x∗ and the maximal constant value ⌢ σ must be the optimal solution� x∗,σ∗ = ⌢ σ � of the relaxed problem (16). Otherwise, i.e., if maximize r 6= 0, set t = t + 1, and solve it again. We can find the maximal constant value ⌢ σ by repeating this procedure in a finite number of iterations. The minimization problems for the test of feasibility and the generation of the most violated constraint are represented as follows: minimize m∑ i=1 n∑ j=1 (ak i j +àk i j )x L i y j−ak m∑ i=1 n∑ j=1 àk i j x L i y j+ak−ak sub ject to n∑ j=1 y j = 1 y j ≥ 0, j = 1, ..., n, k = 1, ..., r. (21) The minimization problems (21), which generates the most violated constraint, can be re- duced to lineear programming problems by using the variable transformations by Charnes and Cooper [9].Set 1   m∑ i=1 n∑ j=1 àk i j x L i y j + ak − ak   = tk, k = 1, ..., r (22) and y j t k = zk j , k = 1, ..., r (23) A. Çevikel, M. Ahlatçıoğlu / Eur. J. Pure Appl. Math, 3 (2010), 107-117 114 The minimization problem (21) can be rewritten as follows r linear programming problems: minimize zk ,tk m∑ i=1 n∑ j=1 (ak i j + àk i j)x L i zk j − ak tk sub ject to n∑ j=1 zk j = tk m∑ i=1 n∑ j=1 àk i j x L i zk j + (a− a)tk = 1 zk j ≥ 0, j = 1, ..., n , k = 1..., r. (24) The kth problem in (24) is a linear programming problem which has decision variables zk = (zk 1 , ..., zk n) and tk, and has the two equality constraints and the nonnegative conditions of the decision variables. Since there are r problems, the test for feasibility for the original problem and the generation of the most violated constraint can be accomplished by solving the r linear programming problems and finding the problem having the smallest optimal value. The algorithm for computing the maximin solution to a multiobjective two-person zero- sum games with fuzzy payoffs and fuzzy goals can be summarized in the following steps. Algorithm Step 1: Identify r fuzzy goals for the payoffs. Choose an initial point y1 ∈ Y and set l = 1. Then formulate a relaxed problem (16), which is a linear fractional programming problem. Step 2: Formulate the constraints (17) by setting σ = ⌢ σ in the constraints of the relaxed prob- lem (16) and set t = 1. Compute an optimal solution (x∗,σ∗) by making use of the problem (20) and If maximize r = 0, then the feasible solution x∗ and the maximal constant value ⌢ σ must be the optimal solution � x∗,σ∗ = ⌢ σ � of the relaxed problem (16). Then set x L = x∗ go to Step 3. Otherwise, i.e., if maximize r 6= 0, set t = t + 1, and solve it again. Step 3: Formulate r minimization linear programming problems (24) with x L. Step 4: Solve r problems (24) and obtain r optimal solutions (zk∗ , tk∗), k = 1, ..., r. Let each of the minimal objective function values be denoted by φk(zk∗ , tk∗), k = 1, ..., r and then let φ ⌢ k (z ⌢ k ∗ , t ⌢ k ∗ ) =min k∈K φk(zk∗ , tk∗). Step 5: If φ ⌢ k (z ⌢ k ∗ , t ⌢ k ∗ ) ≥ σ∗ + ε, terminate, where ε is a predetermined constant. Then x L is a maximin solution with respect to a degree of attainment of the fuzzy goal. Otherwise, i.e., if φ ⌢ k (z ⌢ k ∗ , t ⌢ k ∗ )< σ∗ + ε, set l = l + 1, return to Step 2. We can also obtain Player I I ’s minimax solution with respect to a degree of attainment of a fuzzy goal in similar way. A. Çevikel, M. Ahlatçıoğlu / Eur. J. Pure Appl. Math, 3 (2010), 107-117 115 Example 1. Assuming that each player has three pure strategies and three objectives, we consider a multiobjective two-person zero-sum game with fuzzy payoffs be represented by [12, 17]. eA1 =   (2,0.2,0.2) (5,0.5,0.5) (1,0.8,0.8) (−1,0.8,0.8) (−2,0.4,0.4) (6,0.1,0.1) (0,0.1,0.1) (3,0.5,0.5) (−1,0.8,0.8)   , eA2 =   (−3,0.8,0.8) (7,0.3,0.3) (2,0.4,0.4) (0,0.5,0.5) (−2,0.2,0.2) (0,0.7,0.7) (3,0.4,0.4) (−1,0.8,0.8) (−6,0.5,0.5)   , and eA3 =   (8,0.1,0.1) (−2,0.5,0.5) (3,0.7,0.7) (−5,0.5,0.5) (6,0.4,0.4) (0,0.6,0.6) (−3,0.8,0.8) (1,0.6,0.6) (6,0.1,0.1)   . Let fuzzy goals eG1, eG2 and eG3 of Player I for the three objectives be represented by the following linear membership functions : µeG(p) =    0 i f p1 < −1 p1+1 7.5 i f − 1≤ p1 ≤ 6.5 1 i f 6.5< p1    µeG(p) =    0 i f p2 < −2 p2+2 7.5 i f − 2≤ p2 ≤ 5.5 1 i f 5.5< p2    and µeG(p) =    0 i f p3 < −1 p3+1 6.8 i f − 1≤ p3 ≤ 5.8 1 i f 5.8< p3    We computed the maximin solution by the Algorithm and obtained following solution : x1 = 0.4434, x2 = 0.3178, x3 = 0.2388 y1 = 1, y2 = 0, y3 = 0 (25) The degree of attainment of the fuzzy goal for the maximin solution was σ∗ = 0.246059388. In Algorithm , we set the initial value of y as y1 = 0, y2 = 1, y3 = 0, and the number of iterations was three. REFERENCES 116 4. Conclusion In this paper we have considered the maximin solutions with respect to a degree of at- tainment of the fuzzy goal and have presented the computational method for their solutions. We have used Sakawa’s method, the Dinkelbach algorithm, the variable transformation by Charnes and Cooper and the relaxation procedure for minimax problems by Shimizu and Aiyoshi for the maximin solutions of multiobjective two-person zero-sum games with fuzzy payoffs and fuzzy goals. For multiobjective two-person zero-sum games, if membership functions of the fuzzy goal and shape functions of L-R fuzzy numbers for fuzzy payoffs are linear, the maximin solution with respect to a degree of attainment of the aggregated fuzzy goal presented with a new solution concept. Finally, A numerical example has illustrated the proposed method and obtained the same solution with Sakawa. References [1] J.P. Aubin, Mathematical Methods of Game and Economic Theory (North- Holland,Amsterdam,1979). [2] J.P. Aubin, Cooperative fuzzy game, Math. of Oper. Res. 6 (1981) 1-13. [3] E.B. Bajalinov, Linear -Fractional Programming Theory, Methods, Applications and Soft- ware, [4] R.E.Bellman and L.A. Zadeh, Decision making in a fuzzy environment, Manag. Sci. 17 (1970) 209-215. [5] D.Blackwell, An analog of the minimax theorem for vector payoffs, Pacific J. Math. 98 (1956) 1-8. [6] D.Butnariu, Fuzzy games: A description of the concept, Fuzzy Sets and Systems 1 (1978) 181-192. [7] D.Butnariu, Stability and shapley value for n-person fuzzy game, Fuzzy Sets and Systems 4 (1980) 63-72. [8] L.Campos, Fuzzy linear programming models to solve fuzzy matrix games, Fuzzy Sets and Systems 32 (1989) 275-289. [9] A.Charnes and W. Cooper, Programming with linear fractional function, Naval Res. Lo- gist. Quart. 9 (1962) 181-186. [10] A.Charnes, Z.Huang, J.Rousseau and Q. Wei, Cone extremal solutions of multi-payoff games with cross-constrained strategy set, Optimization 21 (1990) 51-69. REFERENCES 117 [11] I. Olivtti and C. Milano, A decision model under certainty with multiple payoffs, in: A. Mensch, Ed., Theory of games; Techniques and Applications (American Elsevier,New York,1966) 50-63. [12] W.D. Cook, Zero-sum games with multiple goals, Naval Res. Logist. Quart. 23 (1976) 615-622 [13] I. Nishizaki and M.Sakawa, Two-person zero-sum games with multiple fuzzy goals, J. Japan Soc. Fuzzy Theory Systems 4 (1992) 504-511. [14] I. Nishizaki and M.Sakawa, Fuzzy and Multiobjective Games for Conflict Resolution, Kluwer Academic Publishers 2003. [15] I. Nishizaki and M.Sakawa, Equilibrium Solutions for Multiobjective Bimatrix Games Incorporating Fuzzy Goals, Journal of Optimization Theory and Applications, 86 (1995) 433-457. [16] I. Nishizaki and M.Sakawa, Equilibrium Solutions in Multiobjective Bimatrix Games with Fuzzy Payoffs and Fuzzy Goals, Fuzzy Sets and Systems, 111 (2000) 99-116. [17] M.Sakawa and I. Nishizaki, Max-min solutions for fuzzy multiobjective matrix games, Fuzzy Sets and Systems, 67 (1994) 53-69. [18] M.Sakawa, Interactive computer program for fuzzy linear programming with multiple objectives, Int. J. Man-Machine Studies, 18 (1983) 489-503. [19] K.Shimizu and E.Aiyoshi, Neccesary conditions for min-max problems and algorithm by a relaxation procedure, IEEE Trans. Automat. Control AC-25 (1980) 62-66. [20] M.Zeleny, Games with multiple payoffs, Int. J. Game Theory 4 (1975) 179-191. [21] J.Zhao, The equilibria of a multiple objective game, Int. J. Game Theory 20 (1991) 171-182.