روش برنامه ریزی خطی برای حل بازی های ماتریس با ارزش بازه ای

Matrix game theory is concerned with how two players make decisions when they are faced with known exact payoffs. The aim of this paper is to develop a simple and an effective linear programming method for solving matrix games in which the payoffs are expressed with intervals. Because the payoffs of the matrix game are intervals, the value of the matrix game is an interval as well. Based on the definition of the value for matrix games, the value of the matrix game may be regarded as a function of values in the payoff intervals, which is proven to be non-decreasing. A pair of auxiliary linear programming models is formulated to obtain the upper bound and the lower bound of the value of the interval-valued matrix game by using the upper bounds and the lower bounds of the payoff intervals, respectively. By the duality theorem of linear programming, it is proven that two players have the identical interval-type value of the interval-valued matrix game. Also it is proven that the linear programming models and method proposed in this paper extend those of the classical matrix games. The linear programming method proposed in this paper is demonstrated with a real investment decision example and compared with other similar methods to show the validity, applicability and superiority.

Game theory is engaged in competing and strategic interaction among players/subjects in management sciences, operational research, economics, finance, business, social sciences, biology, engineering, etc. It began in the 1920s and has achieved a great success [1], [2], [3], [4] and [5]. The simplest game is the zero-sum game involving only two players. A payoff matrix A=(aij)m×nA=(aij)m×n may be used to model such a two-person zero-sum game, which is usually called as a matrix game for short, where aijaij is the amount of reward/loss which player I wins (and hereby player II loses) when players I and II choose their pure strategies αiαi(i=1,2,…,m)(i=1,2,…,m) and βjβj(j=1,2,…,n)(j=1,2,…,n), respectively. Traditionally, the payoffs aijaij are represented by crisp values, which indicate that they are precisely known. This assumption is reasonable for clearly defined games, which have many useful applications, especially in finance, management and decision making systems [1]. In the real world, however, there are some cases in which the payoffs are not fixed numbers known and have to be estimated even though two players do not change their strategies. An example is one in which different advertising strategies of two competing companies lead to different market shares and the market shares must be estimated. Hence, fuzzy games have been studied [6], [7], [8], [9], [10], [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26] and [27]. Dubois and Prade [4] gave a brief overview and discussion on the fuzzy games with crisp sets of strategies and fuzzy payoffs due to the lack of precision on the knowledge of the associated payoffs. Bector and Chandra [5] and Nishizaki and Sakawa [2] made good overviews on update research of this topic. Bector et al. [6] and [7], respectively, studied the matrix games with fuzzy goals and fuzzy payoffs by using the defined fuzzy linear programming duality. Campos [9], Campos and Gonzalez [10] and Campos et al. [11] proposed ranking function based methods for solving fuzzy matrix games. However, only crisp solutions were provided [9], [10] and [11]. Maeda [16] defined the equilibrium strategy of fuzzy matrix games by using the fuzzy max order. Again, only crisp solutions were provided. Also the classical minimax theorems were not utilized. One theoretically sound property of game theory is that the mathematical models of the matrix game formulated from the standpoints of the two players are a pair of linear programming models which are dual of each other. Hence, solving either of the linear programming models can obtain the strategies of the two players by applying the duality theorem of linear programming. Nishizaki and Sakawa [17], [18] and [19] proposed fuzzy linear programming models of fuzzy matrix games, which only provided crisp solutions. There were also some studies on cooperative games under fuzzy environments [8], [19], [21], [23], [25] and [26] and matrix games under the intuitionistic fuzzy setting [27]. In most of the fuzzy matrix games [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [15], [16], [17], [18], [19], [21], [22], [23], [24] and [27], the payoffs were viewed as fuzzy numbers and assumed that their membership functions are already known a priori. Similarly, in most of the stochastic games [28], [29], [30] and [31], the payoffs were viewed as random variables and also assumed that their probability distributions are already known a priori. These membership functions and probability distributions play an important role in corresponding methods. In reality, it is not always easy for players to specify the membership functions or the probability distributions in uncertain environments. In some cases, the payoffs may only vary within certain ranges for fixed strategies and may be considered as interval estimates, i.e., the matrix games with payoffs of intervals [32], [33], [34], [35], [36], [37], [38], [39], [40] and [41], which usually are called the interval-valued matrix games for short. Interval computing has been a well established field by Moore [42] and successfully applied to some areas [43], [44], [45], [46], [47], [48] and [49]. Also interval linear programming problems have been studied in details and duality results have been obtained [41], [49], [50], [51], [52], [53] and [54]. Stated as earlier, the matrix game is mathematically equivalent to a pair of primal–dual linear programming problems [1]. Thus, theoretically interval-valued matrix games are solvable by using the interval linear programming methodology. Recently, Collins and Hu [12], [32] and [33] investigated crisply and fuzzily determined interval-valued matrix games by using an appropriate fuzzy interval comparison operator and theoretically proposed a pair of interval linear programming models for both players. In order to be able to transform these models into the classical standard linear programming models, Collins and Hu [12], [32] and [33] assumed that player I's gain-floor and player II's loss-ceiling are trivial intervals, i.e., real numbers. As pointed out by Collins and Hu themselves [12], [32] and [33], this assumption seems to be unrealistic and unreasonable in that the value of the interval-valued matrix game being a linear combination of the entries in the interval-valued payoff matrix should be an interval from the viewpoint of a logic. It is worthwhile pointing out that Collins and Hu [12], [32] and [33] further proposed an important technique for solving generic interval inequalities through introducing the interval comparison operator or fuzzy ranking index, which has a good potential of application to the interval-valued matrix games. In [34], the upper and lower bounds of the value of the interval-valued matrix game were determined through developing a pair of two-level mathematical programming models, which were transformed into a pair of ordinary one-level linear programming models by the duality theorem of linear programming and a variable substitution technique. However, Liu and Kao [34] focused on how to obtain the lower and upper bounds of the value of the interval-valued matrix game and did not propose any specific method for solving corresponding optimal strategies for players. In addition, the method [34] resulted in many additional variables and constraints in the derived auxiliary linear programming models, which require a large amount of computation. Nayak and Pal [55] constructed a pair of interval linear programming models for the interval-valued matrix game. However, Nayak and Pal [55] chose only the lower bounds of player I's gain-floor and player II's loss-ceiling as objective functions and hereby transformed the interval linear programming models into the classical linear programming models in terms of the interval inequality relations [51] and [52]. The resulting inappropriate formulations and vital mistakes have been pointed out and corrected by Li [56]. The bi-objective linear programming models were derived and suggested to be solved by the lexicographic method [56]. Based on the defined interval inequality relations and the fuzzy ranking index, Li et al. [57] derived a pair of bi-objective linear programming models from the constructed auxiliary interval programming models for the interval-valued matrix game. The bi-objective linear programming models were solved by using the weighted average method rather than the lexicographic method [56]. Essentially, the weighted average method [57] is a ranking one based on the acceptability index of the interval comparison operator [51] and [52]. Stated as earlier, the value of the interval-valued game matrix should be an interval from the viewpoint of logic. Thus, this paper focuses on developing a simple and an effective linear programming method to determine the lower and upper bounds of the interval-type value of the interval-valued game matrix. The linear programming method is developed on the fact that the value of the matrix game is a non-decreasing function of the values aijaij in the payoff intervals. A pair of auxiliary linear programming models is formulated to obtain the upper bound and the lower bound of the interval-type value of the interval-valued matrix game by using the upper bounds and the lower bounds of the payoff intervals, respectively. By a variable transformation technique, the auxiliary linear programming models are transformed into a pair of linear programming models which can be easily manipulated through using the existing Simplex method of linear programming. Using the duality theorem of linear programming, it is proven that two players have the identical interval-type value of the interval-valued matrix game and the linear programming models and method proposed in this paper extend those of the classical matrix games. The rest of this paper is organized as follows. In the next section, the definition and notations are briefly introduced for the classical matrix games. In Section 3, the interval-valued matrix game is formulated and the monotonicity of its value is discussed. To obtain the lower and upper bounds of the interval-type value of the interval-valued matrix game, a pair of auxiliary linear programming models is derived from the definition of the value of the matrix game and the monotonicity. In Section 4, the linear programming method proposed in this paper is illustrated with a real investment decision example and compared with other similar methods. Conclusion is made in Section 5.