# A Graphical Method for Solving Interval Matrix Games

Authors: Handan Akyar; Emrah Akyar
Journal: Abstract and Applied Analysis
 (2011)

---

## Abstract

2×n or m×2 interval matrix games are considered, and a graphical
method for solving such games is given. Interval matrix game is
the interval generation of classical matrix games. Because of
uncertainty in real-world applications, payoffs of a matrix
game may not be a fixed number. Since the payoffs may vary within
a range for fixed strategies, an interval-valued matrix can
be used to model such uncertainties. In the literature, there are
different approaches for the comparison of fuzzy numbers and
interval numbers. In this work, the idea of acceptability index is
used which is suggested by Sengupta et al. (2001) and Sengupta and
Pal (2009), and in view of acceptability index, well-known
graphical method for matrix games is adapted to interval matrix
games.


---

## Body

## 1. Introduction

The simplest game is finite, two-person, zero-sum game. There are only two players, playerI and player II, and it can be denoted by a matrix. Thus, such a game is called matrix game. Matrix games have many useful applications, especially in decision-making systems. In usual matrix game theory, all the entries of the payoff matrix are assumed to be exactly given. However, in real-world applications, we often encounter the case where the information on the required data includes imprecision or uncertainty because of uncertain environment. Hence, outcomes of a matrix game may not be a fixed number even though the players do not change their strategies. Therefore, interval-valued matrix, whose entries are closed intervals, is proposed by many researchers to model this kind of uncertainty (see [1–6]).The solution methods of interval matrix games are studied by many authors. Most of solution techniques are based on linear programming methods for interval numbers (see [1, 2, 5, 6]). We present, in this paper, a simplistic graphical method for solving 2×n or m×2 interval matrix games and provide a numerical example to exemplify the obtained algorithm.


### 1.1. Interval Numbers

An extensive research and wide coverage on interval arithmetic and its applications can be found in [7]. Here, we only define interval numbers and some necessary operations on interval numbers.An interval number is a subset of real line of the form(1.1)a=[a-,a+]={x∈R:a-≤x≤a+},
where a-,a+∈ℝ and a-≤a+. If a-=a+, then a=[a,a] is a real number.Mid-pointm(a) and radius r(a) of interval number a is defined as (1.2)m(a)=a-+a+2,r(a)=a+-a-2,
respectively.Elementary arithmetic operation⋆∈{+,-,×,÷} between two interval numbers a and b is given by (1.3)a⋆b={a⋆b:a∈a,b∈b}.
For division operator, it is assumed that 0∉b. For any scalar number α, αa is defined as (1.4)αa={[αa-,αa+],forα≥0,[αa+,αa-],forα<0.


### 1.2. Comparison of Interval Numbers

To compare strategies and payoffs for an interval matrix game, we need a notion of an interval ordering relation that corresponds to the intuitive notion of a better possible outcome or payoff.A brief comparison on different interval orders is given in [8, 9] on the basis of decision maker’s opinion.


#### 1.2.1. Disjoint Intervals

Leta=[a-,a+] and b=[b-,b+] be two disjoint interval numbers. Then, it is not difficult to define transitive order relation over these intervals, as a is strictly less than b if and only if a+<b-. This is denoted by a<b, and it is an extension of “<” on the real line.


#### 1.2.2. Nested Intervals

Leta=[a-,a+] and b=[b-,b+] be two interval numbers such that a-≤b-<b+≤a+. Then, b⊆a. Here, the set inclusion only describes the condition that b is nested in a, but it cannot order a and b in terms of value.Leta and b be two cost intervals, and the minimum cost interval is to be chosen.  (i)
If the decision maker (DM) is optimistic, then he/she will prefer the interval with maximum width along with the risk of more uncertainty giving less importance.(ii)
If DM is pessimistic, then he/she will pay more attention on more uncertainty. That is, on the right hand points of the intervals, and he/she will choose the interval with minimum width.The case will be reverse whena and b represent profit intervals. Therefore, we can define the ranking order of a and b as (1.5)a⋁b={a,iftheDMisoptimistic,b,iftheDMispessimistic.
Here, the notation “⋁” denotes the maximum among the interval numbers a and b. Similarly, we can write (1.6)a⋀b={b,iftheDMisoptimistic,a,iftheDMispessimistic.
Likewise, the notation “⋀” denotes the minimum among the interval numbers a and b.


#### 1.2.3. Partially Overlapping Intervals

The above-mentioned order relations cannot explain ranking between two overlapping closed intervals.Here, we use the acceptability index idea suggested by [8, 10]. This comparison method is mainly based on the mid-points of the intervals.Let𝕀ℝ be the set of all interval numbers. The function (1.7)A:IR×IR⟶R,A(a≺b)=m(b)-m(a)r(a)+r(b),r(a)+r(b)≠0 is called acceptability function.Form(b)≥m(a), the number 𝒜(a≺b) is called the grade of acceptability of the interval number a to be inferior to the second interval number b.By the definition of𝒜, for any interval numbers a and b, we have  (i)
𝒜(a≺b)≥1 for m(b)>m(a) and a+≤b-,(ii)
𝒜(a≺b)∈(0,1) for m(b)>m(a) and b-≤a+,(iii)
𝒜(a≺b)=0 for m(b)=m(a). In this case, if r(a)=r(b), then a is identical with b. If r(a)≠r(b), then the intervals a and b are noninferior to each other. In this case, the acceptability index becomes insignificant, so DM has to negotiate with the widths of a and b.Leta and b be two cost intervals, and minimum cost interval is to be chosen. If the DM is optimistic, then he/she will prefer the interval with maximum width along with the risk of more uncertainty giving less importance. Similarly, if the DM is pessimistic, then he/she will pay more attention on more uncertainty, that is, on the right end points of the intervals, and will choose the interval with minimum width. The case will be reverse when a and b represent profit intervals.Example 1.1.
Leta=[-5,-3] and b=[2,6] be two intervals. Then,
(1.8)A(a≺b)=4-(-4)1+2=83>1.
Thus, the DM accept the decision that a is less than b with full satisfaction.Example 1.2.
Leta=[2,8] and b=[1,15] be two intervals. Then,
(1.9)A(a≺b)=8-53+7=0.3∈(0,1).
Hence, the DM accept the decision that a is less than b with grade of satisfaction 0.3.Example 1.3.
Leta=[2,18] and b=[5,15] be two intervals. Then, 𝒜(a≺b)=0.Here, both of the intervals are noninferior to each other. In this case, the DM has to negotiate with the widths of a and b as listed inTable 1.
These can be written explicitly as(1.10)a⋁b={b,ifA(a≺b)>0,a,ifA(a≺b)=0,r(a)<r(b),DMispessimistic,b,ifA(a≺b)=0,r(a)<r(b),DMisoptimistic,
where, a⋁b denotes the maximum of the interval numbers a and b. Similarly,
(1.11)a⋀b={b,ifA(b≺a)>0,a,ifA(b≺a)=0,r(a)>r(b),DMisoptimistic,b,ifA(b≺a)=0,r(a)>r(b),DMispessimistic.
Here, the notation a⋀b represents the minimum of the interval numbers a and b.Table 1Optimistic outlookPessimistic outlookProfit intervalsDM will prefer the intervala instead of b, because DM will pay more attention on the highest possible profit of 18 unit ignoring the risk of minimum profit of 2 unit.DM will prefer the intervalb, because his/her attention will be drawn to the fact that the minimum profit of 5 unit will never be decreased.Cost intervalsDM will pay more attention on the minimum cost of 2 unit, that is, the left hand points both of the cost intervalsa and b, and select a instead of b.DM will again prefer the intervalb, because DM will pay more attention on the maximum cost of 15 unit will never be increased.Proposition 1.4.
The interval ordering by the acceptability index defines a partial order relation on𝕀ℝ.Proof.
(i) If𝒜(a≺b)=0 and r(a)=r(b), then a≡b, and we say that a and b are noninferior to each other. Hence, it is reflexive.
(ii) For any interval numbera and b, 𝒜(a≺b)>0, and 𝒜(b≺a)>0 implies a=b. Therefore, 𝒜 is antisymmetric.
(iii) For any interval numbersa,b,c∈𝕀ℝ if
(1.12)A(a≺b)=m(b)-m(a)r(b)+r(a)≥0,A(b≺c)=m(c)-m(b)r(c)+r(b)≥0,
then m(c)-m(a)=[m(c)-m(b)]+[m(b)-m(a)]≥0. Hence,
(1.13)A(a≺c)=m(c)-m(a)r(c)+r(a)≥0.
Thus, 𝒜 is transitive.On the other hand, acceptability index must not interpreted as difference operator of real analysis. Indeed, while𝒜(a≺b)≥0 and 𝒜(b≺c)≥0, the inequality (1.14)A(a≺c)≥max⁡{A(a≺b),A(b≺c)}
may not hold.Actually, leta=[-2,2],b=[-1,21/20]andc=[-1/2,3/4], then(1.15)A(a≺b)=1121,A(b≺c)=233,
but(1.16)A(a≺c)=121<233.For any two interval numbersa and b from 𝕀ℝ, either 𝒜(a≺b)>0, or 𝒜(a≺b)=𝒜(b≺a)=0, or 𝒜(b≺a)>0. Also, 𝒜(a≺b)<0 can be interpreted as the interval number b is inferior to the interval number a, since 𝒜(b≺a)>0.Additionally, for any interval numbersa, b, c, and d, the following properties of acceptability index is obvious. (1.17)IfA(a≺b)≥0,A(c≺d)≥0⟹A(a+c≺b+d)≥0,A(a≺b)≥0⟹A(a+c≺b+c)≥0,A(a≺b)≥0⟹A(-1⋅b≺-1⋅a)≥0.


### 1.3. Matrix Games

Game theory is a mathematical discipline which studies situations of competition and cooperation between several involved parties, and it has many applications in broad areas such as strategic warfares, economic or social problems, animal behaviours, political voting systems. It is accepted that game theory starts with the von Neumann’s study on zero-sum games (see [11]), in which he proved the famous minimax theorem for zero-sum games. It was also basis for [12].The simplest game is finite, two-person, zero-sum game. There are only two players, playerI and player II, and it can be denoted by a matrix. Thus, such a game is called matrix game. More formally, a matrix game is an m×n matrix G of real numbers.A (mixed) strategy of playerI is a probability distribution x over the rows of G, that is, an element of the set (1.18)Xm={x=(x1,…,xm)∈Rm:xi≥0,∑i=1mxi=1}.
Similarly, a strategy of player II is a probability distribution y over the columns of G, that is, an element of the set (1.19)Yn={y=(y1,…,yn)∈Rn:yi≥0,∑i=1nyi=1}.A strategyx of player I is called pure if it does not involve probability, that is, xi=1 for some i=1,…,m, and it is denoted by Ii. Similarly, pure strategies of player II is denoted by IIj for j=1,…,n.If playerI plays row i (i.e., pure strategy x=(0,0,…,xi=1,0,…,0) and player II plays column j (i.e., pure strategy y=(0,0,…,yj=1,0,…,0), then player I receives payoff gij, and player II pays gij, where gij is the entry in row i and column j of matrix G.If playerI plays strategy x and player II plays strategy y, then player I receives the expected payoff (1.20)g(x,y)=xTGy,
where xT denotes the transpose of x.A strategyx* is called maximin strategy of player I in matrix game G if (1.21)min⁡{(x*)TGy,y∈Yn}≥min⁡{xTGy,y∈Yn},
for all x∈Xm and a strategy y* is called minimax strategy of player II in matrix game G if (1.22)max⁡{xTGy*,x∈Xm}≤max⁡{xTGy,x∈Xm},
for all y∈Yn.Therefore, a maximin strategy of playerI maximizes the minimal payoff of player I, and a minimax strategy of player II minimizes the maximum that player II has to pay to player I.Neumann proved that for every matrix gameG, there is a real number ν with the following properties.(1)
A strategyx of player I guarantees a payoff of at least ν to player I (i.e., xTGy≥ν for all strategies y of player II) if and only if x is a maximin strategy.(2)
A strategyy of player II guarantees a payment of at most ν by player II to player I (i.e., xTGy≤ν for all strategies x of player I) if and only if y is a minimax strategy.Hence, playerI can obtain a payoff at least ν by playing maximin strategy, and player II can guarantee to pay not more than ν by playing minimax strategy. For these reasons, the number ν is also called the value of the game G.A position(i,j) is called saddle point if gij≥gkj for all k=1,…,m and gij≤gil for all l=1,…,n, that is, if gij is maximal in its column j and minimal in its row i. Evidently, if (i,j) is a saddle point, then gij must be the value of the game.


### 1.4. Interval Matrix Games

Interval matrix game is the interval generation of classical matrix games, and it is the special case of fuzzy games.Here, we consider a nonzero sum interval matrix game with two players, and we assume that playerI is maximizing or optimistic player and player II is minimizing or pessimistic player. We assume that player I will try to make maximum profit and player II will try to minimize the loss.The two person interval matrix game is defined bym×n matrix G whose entries are interval numbers.LetG be an interval matrix game (1.23)G=II1II2⋯IInI1I2⋮Im(g11g21⋮gm1g12g22⋮gm2⋯⋯⋱⋯g1ng2n⋮gmn),andx∈Xm, y∈Yn; that is, x and y are strategies for players I and II. Then, the expected payoff for player I is defined by (1.24)g(x,y)=xTGy=∑i∑jxiyjgij.
Here,∑ denotes the Minkowski’s sum of intervals.Example 1.5.
Let(1.25)G=II1II2II3II4I1I2I3([-10,1][-9,8][-3,-2][-8,7][-1,7][-1,5][-8,-7][3,8][-2,2][-6,7][8,9][-3,7])
be interval matrix game.
For this game, if playerI plays second row (x=(0,1,0)) and player II plays third column (y=(0,0,1,0)), then player I receives, and correspondingly, player II pays a payoff g(I2,II3)∈[3,8].
On the other hand, for pair of strategiesx=(1/2,1/2,0) and y=(0,1/3,1/3,1/3), the expected payoff for player I belongs to g(x,y)=[-2,31/6].Now, define(1.26)νL=⋁x∈Xm⋀y∈Yng(x,y),νU=⋀y∈Yn⋁x∈Xmg(x,y),
to be lower and upper value of interval matrix game.It is naturally clear that𝒜(νL≺νU)≥0.In addition, ifνL=νU=ν, then ν is called the value of interval matrix game.Theorem 1.6 (Fundamental Theorem).
LetG be an interval matrix game. Then,  ⋁x∈Xm⋀y∈Yng(x,y) and  ⋀y∈Yn⋁x∈Xmg(x,y) both exist and are equal.Letν be the value of game. Then, the (x*,y*,ν)∈Xm×Yn×𝕀ℝ is called the solution of interval matrix game if (1.27)⋀y∈Yng(x*,y)=⋁x∈Xm⋀y∈Yng(x,y)=ν,(1.28)⋁x∈Xmg(x,y*)=⋀y∈Yn⋁x∈Xmg(x,y)=ν.
Furthermore, the strategies x* and y* are called optimal strategies for players.In view of Theorem1.6, we can conclude that every two person interval matrix game has a solution.The value of the interval matrix game(1.29)G=II1II2II3II4I1I2I3([-10,1][-9,8][-3,-2][-8,7][-1,7][-1,5][-8,-7][3,8][-2,2][-6,7][8,9][-3,7])
is [-9,8]. On the other hand, if we consider the left and right endpoints of the entries of interval matrix G as two different matrix games, that is, (1.30)G-=II1II2II3II4I1I2I3(-10-9-3-8-1-1-83-2-68-3),G+=II1II2II3II4I1I2I3(18-2775-782797),
then value of these matrix games are −3 and 7, respectively. Hence, there is no trivial relation between the value of interval matrix game and the value of endpoint matrix games.


## 1.1. Interval Numbers

An extensive research and wide coverage on interval arithmetic and its applications can be found in [7]. Here, we only define interval numbers and some necessary operations on interval numbers.An interval number is a subset of real line of the form(1.1)a=[a-,a+]={x∈R:a-≤x≤a+},
where a-,a+∈ℝ and a-≤a+. If a-=a+, then a=[a,a] is a real number.Mid-pointm(a) and radius r(a) of interval number a is defined as (1.2)m(a)=a-+a+2,r(a)=a+-a-2,
respectively.Elementary arithmetic operation⋆∈{+,-,×,÷} between two interval numbers a and b is given by (1.3)a⋆b={a⋆b:a∈a,b∈b}.
For division operator, it is assumed that 0∉b. For any scalar number α, αa is defined as (1.4)αa={[αa-,αa+],forα≥0,[αa+,αa-],forα<0.


## 1.2. Comparison of Interval Numbers

To compare strategies and payoffs for an interval matrix game, we need a notion of an interval ordering relation that corresponds to the intuitive notion of a better possible outcome or payoff.A brief comparison on different interval orders is given in [8, 9] on the basis of decision maker’s opinion.


### 1.2.1. Disjoint Intervals

Leta=[a-,a+] and b=[b-,b+] be two disjoint interval numbers. Then, it is not difficult to define transitive order relation over these intervals, as a is strictly less than b if and only if a+<b-. This is denoted by a<b, and it is an extension of “<” on the real line.


### 1.2.2. Nested Intervals

Leta=[a-,a+] and b=[b-,b+] be two interval numbers such that a-≤b-<b+≤a+. Then, b⊆a. Here, the set inclusion only describes the condition that b is nested in a, but it cannot order a and b in terms of value.Leta and b be two cost intervals, and the minimum cost interval is to be chosen.  (i)
If the decision maker (DM) is optimistic, then he/she will prefer the interval with maximum width along with the risk of more uncertainty giving less importance.(ii)
If DM is pessimistic, then he/she will pay more attention on more uncertainty. That is, on the right hand points of the intervals, and he/she will choose the interval with minimum width.The case will be reverse whena and b represent profit intervals. Therefore, we can define the ranking order of a and b as (1.5)a⋁b={a,iftheDMisoptimistic,b,iftheDMispessimistic.
Here, the notation “⋁” denotes the maximum among the interval numbers a and b. Similarly, we can write (1.6)a⋀b={b,iftheDMisoptimistic,a,iftheDMispessimistic.
Likewise, the notation “⋀” denotes the minimum among the interval numbers a and b.


### 1.2.3. Partially Overlapping Intervals

The above-mentioned order relations cannot explain ranking between two overlapping closed intervals.Here, we use the acceptability index idea suggested by [8, 10]. This comparison method is mainly based on the mid-points of the intervals.Let𝕀ℝ be the set of all interval numbers. The function (1.7)A:IR×IR⟶R,A(a≺b)=m(b)-m(a)r(a)+r(b),r(a)+r(b)≠0 is called acceptability function.Form(b)≥m(a), the number 𝒜(a≺b) is called the grade of acceptability of the interval number a to be inferior to the second interval number b.By the definition of𝒜, for any interval numbers a and b, we have  (i)
𝒜(a≺b)≥1 for m(b)>m(a) and a+≤b-,(ii)
𝒜(a≺b)∈(0,1) for m(b)>m(a) and b-≤a+,(iii)
𝒜(a≺b)=0 for m(b)=m(a). In this case, if r(a)=r(b), then a is identical with b. If r(a)≠r(b), then the intervals a and b are noninferior to each other. In this case, the acceptability index becomes insignificant, so DM has to negotiate with the widths of a and b.Leta and b be two cost intervals, and minimum cost interval is to be chosen. If the DM is optimistic, then he/she will prefer the interval with maximum width along with the risk of more uncertainty giving less importance. Similarly, if the DM is pessimistic, then he/she will pay more attention on more uncertainty, that is, on the right end points of the intervals, and will choose the interval with minimum width. The case will be reverse when a and b represent profit intervals.Example 1.1.
Leta=[-5,-3] and b=[2,6] be two intervals. Then,
(1.8)A(a≺b)=4-(-4)1+2=83>1.
Thus, the DM accept the decision that a is less than b with full satisfaction.Example 1.2.
Leta=[2,8] and b=[1,15] be two intervals. Then,
(1.9)A(a≺b)=8-53+7=0.3∈(0,1).
Hence, the DM accept the decision that a is less than b with grade of satisfaction 0.3.Example 1.3.
Leta=[2,18] and b=[5,15] be two intervals. Then, 𝒜(a≺b)=0.Here, both of the intervals are noninferior to each other. In this case, the DM has to negotiate with the widths of a and b as listed inTable 1.
These can be written explicitly as(1.10)a⋁b={b,ifA(a≺b)>0,a,ifA(a≺b)=0,r(a)<r(b),DMispessimistic,b,ifA(a≺b)=0,r(a)<r(b),DMisoptimistic,
where, a⋁b denotes the maximum of the interval numbers a and b. Similarly,
(1.11)a⋀b={b,ifA(b≺a)>0,a,ifA(b≺a)=0,r(a)>r(b),DMisoptimistic,b,ifA(b≺a)=0,r(a)>r(b),DMispessimistic.
Here, the notation a⋀b represents the minimum of the interval numbers a and b.Table 1Optimistic outlookPessimistic outlookProfit intervalsDM will prefer the intervala instead of b, because DM will pay more attention on the highest possible profit of 18 unit ignoring the risk of minimum profit of 2 unit.DM will prefer the intervalb, because his/her attention will be drawn to the fact that the minimum profit of 5 unit will never be decreased.Cost intervalsDM will pay more attention on the minimum cost of 2 unit, that is, the left hand points both of the cost intervalsa and b, and select a instead of b.DM will again prefer the intervalb, because DM will pay more attention on the maximum cost of 15 unit will never be increased.Proposition 1.4.
The interval ordering by the acceptability index defines a partial order relation on𝕀ℝ.Proof.
(i) If𝒜(a≺b)=0 and r(a)=r(b), then a≡b, and we say that a and b are noninferior to each other. Hence, it is reflexive.
(ii) For any interval numbera and b, 𝒜(a≺b)>0, and 𝒜(b≺a)>0 implies a=b. Therefore, 𝒜 is antisymmetric.
(iii) For any interval numbersa,b,c∈𝕀ℝ if
(1.12)A(a≺b)=m(b)-m(a)r(b)+r(a)≥0,A(b≺c)=m(c)-m(b)r(c)+r(b)≥0,
then m(c)-m(a)=[m(c)-m(b)]+[m(b)-m(a)]≥0. Hence,
(1.13)A(a≺c)=m(c)-m(a)r(c)+r(a)≥0.
Thus, 𝒜 is transitive.On the other hand, acceptability index must not interpreted as difference operator of real analysis. Indeed, while𝒜(a≺b)≥0 and 𝒜(b≺c)≥0, the inequality (1.14)A(a≺c)≥max⁡{A(a≺b),A(b≺c)}
may not hold.Actually, leta=[-2,2],b=[-1,21/20]andc=[-1/2,3/4], then(1.15)A(a≺b)=1121,A(b≺c)=233,
but(1.16)A(a≺c)=121<233.For any two interval numbersa and b from 𝕀ℝ, either 𝒜(a≺b)>0, or 𝒜(a≺b)=𝒜(b≺a)=0, or 𝒜(b≺a)>0. Also, 𝒜(a≺b)<0 can be interpreted as the interval number b is inferior to the interval number a, since 𝒜(b≺a)>0.Additionally, for any interval numbersa, b, c, and d, the following properties of acceptability index is obvious. (1.17)IfA(a≺b)≥0,A(c≺d)≥0⟹A(a+c≺b+d)≥0,A(a≺b)≥0⟹A(a+c≺b+c)≥0,A(a≺b)≥0⟹A(-1⋅b≺-1⋅a)≥0.


## 1.2.1. Disjoint Intervals

Leta=[a-,a+] and b=[b-,b+] be two disjoint interval numbers. Then, it is not difficult to define transitive order relation over these intervals, as a is strictly less than b if and only if a+<b-. This is denoted by a<b, and it is an extension of “<” on the real line.


## 1.2.2. Nested Intervals

Leta=[a-,a+] and b=[b-,b+] be two interval numbers such that a-≤b-<b+≤a+. Then, b⊆a. Here, the set inclusion only describes the condition that b is nested in a, but it cannot order a and b in terms of value.Leta and b be two cost intervals, and the minimum cost interval is to be chosen.  (i)
If the decision maker (DM) is optimistic, then he/she will prefer the interval with maximum width along with the risk of more uncertainty giving less importance.(ii)
If DM is pessimistic, then he/she will pay more attention on more uncertainty. That is, on the right hand points of the intervals, and he/she will choose the interval with minimum width.The case will be reverse whena and b represent profit intervals. Therefore, we can define the ranking order of a and b as (1.5)a⋁b={a,iftheDMisoptimistic,b,iftheDMispessimistic.
Here, the notation “⋁” denotes the maximum among the interval numbers a and b. Similarly, we can write (1.6)a⋀b={b,iftheDMisoptimistic,a,iftheDMispessimistic.
Likewise, the notation “⋀” denotes the minimum among the interval numbers a and b.


## 1.2.3. Partially Overlapping Intervals

The above-mentioned order relations cannot explain ranking between two overlapping closed intervals.Here, we use the acceptability index idea suggested by [8, 10]. This comparison method is mainly based on the mid-points of the intervals.Let𝕀ℝ be the set of all interval numbers. The function (1.7)A:IR×IR⟶R,A(a≺b)=m(b)-m(a)r(a)+r(b),r(a)+r(b)≠0 is called acceptability function.Form(b)≥m(a), the number 𝒜(a≺b) is called the grade of acceptability of the interval number a to be inferior to the second interval number b.By the definition of𝒜, for any interval numbers a and b, we have  (i)
𝒜(a≺b)≥1 for m(b)>m(a) and a+≤b-,(ii)
𝒜(a≺b)∈(0,1) for m(b)>m(a) and b-≤a+,(iii)
𝒜(a≺b)=0 for m(b)=m(a). In this case, if r(a)=r(b), then a is identical with b. If r(a)≠r(b), then the intervals a and b are noninferior to each other. In this case, the acceptability index becomes insignificant, so DM has to negotiate with the widths of a and b.Leta and b be two cost intervals, and minimum cost interval is to be chosen. If the DM is optimistic, then he/she will prefer the interval with maximum width along with the risk of more uncertainty giving less importance. Similarly, if the DM is pessimistic, then he/she will pay more attention on more uncertainty, that is, on the right end points of the intervals, and will choose the interval with minimum width. The case will be reverse when a and b represent profit intervals.Example 1.1.
Leta=[-5,-3] and b=[2,6] be two intervals. Then,
(1.8)A(a≺b)=4-(-4)1+2=83>1.
Thus, the DM accept the decision that a is less than b with full satisfaction.Example 1.2.
Leta=[2,8] and b=[1,15] be two intervals. Then,
(1.9)A(a≺b)=8-53+7=0.3∈(0,1).
Hence, the DM accept the decision that a is less than b with grade of satisfaction 0.3.Example 1.3.
Leta=[2,18] and b=[5,15] be two intervals. Then, 𝒜(a≺b)=0.Here, both of the intervals are noninferior to each other. In this case, the DM has to negotiate with the widths of a and b as listed inTable 1.
These can be written explicitly as(1.10)a⋁b={b,ifA(a≺b)>0,a,ifA(a≺b)=0,r(a)<r(b),DMispessimistic,b,ifA(a≺b)=0,r(a)<r(b),DMisoptimistic,
where, a⋁b denotes the maximum of the interval numbers a and b. Similarly,
(1.11)a⋀b={b,ifA(b≺a)>0,a,ifA(b≺a)=0,r(a)>r(b),DMisoptimistic,b,ifA(b≺a)=0,r(a)>r(b),DMispessimistic.
Here, the notation a⋀b represents the minimum of the interval numbers a and b.Table 1Optimistic outlookPessimistic outlookProfit intervalsDM will prefer the intervala instead of b, because DM will pay more attention on the highest possible profit of 18 unit ignoring the risk of minimum profit of 2 unit.DM will prefer the intervalb, because his/her attention will be drawn to the fact that the minimum profit of 5 unit will never be decreased.Cost intervalsDM will pay more attention on the minimum cost of 2 unit, that is, the left hand points both of the cost intervalsa and b, and select a instead of b.DM will again prefer the intervalb, because DM will pay more attention on the maximum cost of 15 unit will never be increased.Proposition 1.4.
The interval ordering by the acceptability index defines a partial order relation on𝕀ℝ.Proof.
(i) If𝒜(a≺b)=0 and r(a)=r(b), then a≡b, and we say that a and b are noninferior to each other. Hence, it is reflexive.
(ii) For any interval numbera and b, 𝒜(a≺b)>0, and 𝒜(b≺a)>0 implies a=b. Therefore, 𝒜 is antisymmetric.
(iii) For any interval numbersa,b,c∈𝕀ℝ if
(1.12)A(a≺b)=m(b)-m(a)r(b)+r(a)≥0,A(b≺c)=m(c)-m(b)r(c)+r(b)≥0,
then m(c)-m(a)=[m(c)-m(b)]+[m(b)-m(a)]≥0. Hence,
(1.13)A(a≺c)=m(c)-m(a)r(c)+r(a)≥0.
Thus, 𝒜 is transitive.On the other hand, acceptability index must not interpreted as difference operator of real analysis. Indeed, while𝒜(a≺b)≥0 and 𝒜(b≺c)≥0, the inequality (1.14)A(a≺c)≥max⁡{A(a≺b),A(b≺c)}
may not hold.Actually, leta=[-2,2],b=[-1,21/20]andc=[-1/2,3/4], then(1.15)A(a≺b)=1121,A(b≺c)=233,
but(1.16)A(a≺c)=121<233.For any two interval numbersa and b from 𝕀ℝ, either 𝒜(a≺b)>0, or 𝒜(a≺b)=𝒜(b≺a)=0, or 𝒜(b≺a)>0. Also, 𝒜(a≺b)<0 can be interpreted as the interval number b is inferior to the interval number a, since 𝒜(b≺a)>0.Additionally, for any interval numbersa, b, c, and d, the following properties of acceptability index is obvious. (1.17)IfA(a≺b)≥0,A(c≺d)≥0⟹A(a+c≺b+d)≥0,A(a≺b)≥0⟹A(a+c≺b+c)≥0,A(a≺b)≥0⟹A(-1⋅b≺-1⋅a)≥0.


## 1.3. Matrix Games

Game theory is a mathematical discipline which studies situations of competition and cooperation between several involved parties, and it has many applications in broad areas such as strategic warfares, economic or social problems, animal behaviours, political voting systems. It is accepted that game theory starts with the von Neumann’s study on zero-sum games (see [11]), in which he proved the famous minimax theorem for zero-sum games. It was also basis for [12].The simplest game is finite, two-person, zero-sum game. There are only two players, playerI and player II, and it can be denoted by a matrix. Thus, such a game is called matrix game. More formally, a matrix game is an m×n matrix G of real numbers.A (mixed) strategy of playerI is a probability distribution x over the rows of G, that is, an element of the set (1.18)Xm={x=(x1,…,xm)∈Rm:xi≥0,∑i=1mxi=1}.
Similarly, a strategy of player II is a probability distribution y over the columns of G, that is, an element of the set (1.19)Yn={y=(y1,…,yn)∈Rn:yi≥0,∑i=1nyi=1}.A strategyx of player I is called pure if it does not involve probability, that is, xi=1 for some i=1,…,m, and it is denoted by Ii. Similarly, pure strategies of player II is denoted by IIj for j=1,…,n.If playerI plays row i (i.e., pure strategy x=(0,0,…,xi=1,0,…,0) and player II plays column j (i.e., pure strategy y=(0,0,…,yj=1,0,…,0), then player I receives payoff gij, and player II pays gij, where gij is the entry in row i and column j of matrix G.If playerI plays strategy x and player II plays strategy y, then player I receives the expected payoff (1.20)g(x,y)=xTGy,
where xT denotes the transpose of x.A strategyx* is called maximin strategy of player I in matrix game G if (1.21)min⁡{(x*)TGy,y∈Yn}≥min⁡{xTGy,y∈Yn},
for all x∈Xm and a strategy y* is called minimax strategy of player II in matrix game G if (1.22)max⁡{xTGy*,x∈Xm}≤max⁡{xTGy,x∈Xm},
for all y∈Yn.Therefore, a maximin strategy of playerI maximizes the minimal payoff of player I, and a minimax strategy of player II minimizes the maximum that player II has to pay to player I.Neumann proved that for every matrix gameG, there is a real number ν with the following properties.(1)
A strategyx of player I guarantees a payoff of at least ν to player I (i.e., xTGy≥ν for all strategies y of player II) if and only if x is a maximin strategy.(2)
A strategyy of player II guarantees a payment of at most ν by player II to player I (i.e., xTGy≤ν for all strategies x of player I) if and only if y is a minimax strategy.Hence, playerI can obtain a payoff at least ν by playing maximin strategy, and player II can guarantee to pay not more than ν by playing minimax strategy. For these reasons, the number ν is also called the value of the game G.A position(i,j) is called saddle point if gij≥gkj for all k=1,…,m and gij≤gil for all l=1,…,n, that is, if gij is maximal in its column j and minimal in its row i. Evidently, if (i,j) is a saddle point, then gij must be the value of the game.


## 1.4. Interval Matrix Games

Interval matrix game is the interval generation of classical matrix games, and it is the special case of fuzzy games.Here, we consider a nonzero sum interval matrix game with two players, and we assume that playerI is maximizing or optimistic player and player II is minimizing or pessimistic player. We assume that player I will try to make maximum profit and player II will try to minimize the loss.The two person interval matrix game is defined bym×n matrix G whose entries are interval numbers.LetG be an interval matrix game (1.23)G=II1II2⋯IInI1I2⋮Im(g11g21⋮gm1g12g22⋮gm2⋯⋯⋱⋯g1ng2n⋮gmn),andx∈Xm, y∈Yn; that is, x and y are strategies for players I and II. Then, the expected payoff for player I is defined by (1.24)g(x,y)=xTGy=∑i∑jxiyjgij.
Here,∑ denotes the Minkowski’s sum of intervals.Example 1.5.
Let(1.25)G=II1II2II3II4I1I2I3([-10,1][-9,8][-3,-2][-8,7][-1,7][-1,5][-8,-7][3,8][-2,2][-6,7][8,9][-3,7])
be interval matrix game.
For this game, if playerI plays second row (x=(0,1,0)) and player II plays third column (y=(0,0,1,0)), then player I receives, and correspondingly, player II pays a payoff g(I2,II3)∈[3,8].
On the other hand, for pair of strategiesx=(1/2,1/2,0) and y=(0,1/3,1/3,1/3), the expected payoff for player I belongs to g(x,y)=[-2,31/6].Now, define(1.26)νL=⋁x∈Xm⋀y∈Yng(x,y),νU=⋀y∈Yn⋁x∈Xmg(x,y),
to be lower and upper value of interval matrix game.It is naturally clear that𝒜(νL≺νU)≥0.In addition, ifνL=νU=ν, then ν is called the value of interval matrix game.Theorem 1.6 (Fundamental Theorem).
LetG be an interval matrix game. Then,  ⋁x∈Xm⋀y∈Yng(x,y) and  ⋀y∈Yn⋁x∈Xmg(x,y) both exist and are equal.Letν be the value of game. Then, the (x*,y*,ν)∈Xm×Yn×𝕀ℝ is called the solution of interval matrix game if (1.27)⋀y∈Yng(x*,y)=⋁x∈Xm⋀y∈Yng(x,y)=ν,(1.28)⋁x∈Xmg(x,y*)=⋀y∈Yn⋁x∈Xmg(x,y)=ν.
Furthermore, the strategies x* and y* are called optimal strategies for players.In view of Theorem1.6, we can conclude that every two person interval matrix game has a solution.The value of the interval matrix game(1.29)G=II1II2II3II4I1I2I3([-10,1][-9,8][-3,-2][-8,7][-1,7][-1,5][-8,-7][3,8][-2,2][-6,7][8,9][-3,7])
is [-9,8]. On the other hand, if we consider the left and right endpoints of the entries of interval matrix G as two different matrix games, that is, (1.30)G-=II1II2II3II4I1I2I3(-10-9-3-8-1-1-83-2-68-3),G+=II1II2II3II4I1I2I3(18-2775-782797),
then value of these matrix games are −3 and 7, respectively. Hence, there is no trivial relation between the value of interval matrix game and the value of endpoint matrix games.


## 2. A Graphical Method for Solving Interval Matrix Games

Let(2.1)G=II1II2⋯IInI1I2⋮Im(g11g21⋮gm1g12g22⋮gm2⋯⋯⋱⋯g1ng2n⋮gmn)
be an interval matrix game.Letν be value of m×n interval matrix game G. In general, the width of ν can vary. To normalize the width of ν in order to investigate a method for solving such games, from now on, we will assume that all entries of G are of same length; that is, gij+=gij-+λ for some λ>0 and i=1,2,…,m, j=1,2,…,n.The solution methods of interval matrix games are studied by many authors. Most of solution techniques are based on linear programming methods for interval numbers (see [1–4, 6]).A useful idea in solving2×n interval matrix games is that of worthwhile strategies. A worthwhile strategy is a pure strategy which appears with positive probability in an optimal strategy.The following proposition is the important property about such strategies.Proposition 2.1.
When a worthwhile strategy plays an optimal strategy, the payoff is the value of the game.It means that if(x*,y*,ν)∈Xm×Yn×𝕀ℝ is the solution of interval matrix game (2.1) and the pure strategies Ii* and IIj* are worthwhile strategies, then the equalities (2.2)g(x*,y*)=g(Ii*,y*)=ν,(2.3)g(x*,y*)=g(x*,IIj*)=ν
hold.Proof.
We assume without loss of generality that playerI has an optimal strategy x*=(x1,x2,…,xk,0,…,0). Here, xi>0, i=1,2,…,k and ∑i=1kxi=1. We also assume that player II has an optimal strategy y* and value of the game is ν. Hence, g(x*,y*)=ν.
Furthermore, for any pure strategyIi (1≤i≤k) of player I, we have
(2.4)A(g(Ii,y*)≺ν)≥0,
since player II playing optimal strategy y*.
We setg(Ii,y*)=νi. Then, using following equality:
(2.5)ν=g(x*,y*)=∑i=1kxig(Ii,y*)=∑i=1kxiνi,
and (2.4) we find
(2.6)A(ν=∑i=1kxiνi≺∑i=1kxiν=ν)≥0.
Thus, acceptability index must be 0, and so νi=ν for all i=1,2,…,k. Therefore, playing the worthwhile strategy Ii against optimal strategy y* gives a payoff that is the value of the game.
The proof of (2.3) is similar.Theorem 2.2.
Ifν is value of  m×n interval matrix game (2.1), then the equalities
(2.7)⋁x∈Xm⋀y∈Yng(x,y)=⋁x∈Xm⋀j=1,2,…,ng(x,IIj)=ν,(2.8)⋀y∈Yn⋁x∈Xmg(x,y)=⋀y∈Yn⋁i=1,2,…,mg(Ii,y)=ν
hold.Proof.
By Theorem1.6, we know that interval matrix game (2.1) has a solution. Let us denote the solution of (2.1) by (x*,y*,ν). Then, we have
(2.9)⋁x∈Xm⋀y∈Yng(x,y)=⋀y∈Yn⋁x∈Xmg(x,y)=ν,(2.10)A(ν≺g(x*,y))≥0,∀y∈Yn,(2.11)A(g(x,y*)≺ν)≥0,∀x∈Xm.
Since IIj∈Yn for all j=1,2,…,n, then using (2.10), we get
(2.12)A(ν≺g(x*,IIj))≥0,
for all j=1,2,…,n. Therefore, it follows that
(2.13)A(ν≺⋀j=1,2,…,n{g(x*,IIj)})≥0.
Using (2.13), we find
(2.14)A(ν≺⋁x∈Xm⋀j=1,2,…,n{g(x*,IIj)})≥0.
Now, let us show that
(2.15)A(ν≺⋁x∈Xm⋀j=1,2,…,n{g(x*,IIj)})=0.
Suppose, contrary to what we wish to show, that
(2.16)A(ν≺⋁x∈Xm⋀j=1,2,…,n{g(x*,IIj)})>0.
For notational simplicity, we assume that
(2.17)ν*=⋁x∈Xm⋀j=1,2,…,n{g(x*,IIj)}.
Then, there exists x̃=(x̃1,…,x̃m)∈Xm such that
(2.18)ν*=⋀j=1,2,…,n{g(x̃,IIj)}.
Since 𝒜(ν*≺g(x̃,IIj))≥0 and acceptability index is transitive, then we obtain
(2.19)A(ν≺g(x̃,IIj))>0,
for all j=1,2,…,n.
Additionally, for ally=(y1,…,yn)∈Yn we can write
(2.20)g(x̃,y)=∑j=1n∑i=1mx̃gijyj=∑j=1n(∑i=1mx̃gij)yj=∑j=1ng(x̃,IIj)yj.
Therefore, we have
(2.21)A(ν*≺g(x̃,y))≥0,
for all y∈Yn. Since 𝒜(ν≺ν*)>0, we get from (2.11) that
(2.22)A(g(x,y*)≺ν*)≥0,
for all x∈Xm.
Using (1.28), (2.21), and (2.22), we conclude that (x̃,y*,ν*) is also a solution of (2.1), contradicting the fact that value of the game is unique. This concludes that (2.15) holds. Hence, from (2.9) and (2.15), we obtain the validity of (2.7).
By completely analogous arguments, we can also obtain (2.8).Now, using Theorem2.2, we can show how to solve interval matrix games, where at least one of the players has two pure strategies.Let us consider(2.23)G=II1II2⋯IInI1I2(g11g21g12g22⋯⋯g1ng2n),2×n interval matrix game.We denote the value ofG by the symbol ν*.Since playerI has only two strategies, for any x=(x1,x2)∈X2, we can write x=(t,1-t), t∈[0,1]. Then, we obtain (2.24)g(x,IIj)=tg1j+(1-t)g2j,
for t∈[0,1]. Setting (2.25)ϕj(t)=g(x,IIj),j=1,…,n,
we get (2.26)ϕj(t)=tg1j+(1-t)g2j,j=1,…,n.
Using Theorem 2.2, we have (2.27)ν*=⋁x∈X2⋀j=1,…,ng(x,IIj)=⋁t∈[0,1]⋀j=1,…,nϕj(t).
Therefore, the following algorithm can be used to find solution of 2×n interval matrix games.Algorithm 2.3.
Step 1.
Plotϕj:[0,1]→𝕀ℝ for all j=1,…,n on the plane.Step 2.
Draw the functionψ:[0,1]→𝕀ℝ by setting
(2.28)ψ(t)=⋀j=1,…,n{ϕj(t)},
(see Figure 1).Step 3.
By means of definition ofψ calculate the ⋁{ψ(t)} on [0,1]; that is, find
(2.29)ν*=⋁t∈[0,1]{ψ(t)}.Step 4.
Using definition ofψ, calculate the t*∈[0,1], where ψ attains its maximum. Thus, x*=(t*,1-t*), and the optimal strategy of player I is obtained.Step 5.
Using the property of worthwhile strategies, find the optimal strategy of playerII.Step1 and Step 2 of Algorithm 2.3.
(a)(b)To see how this works, let us solve a game.


## 3. Numerical Example

Example 3.1.
Consider the2×5 interval matrix game
(3.1)G=II1II2II3II4II5I1I2([-2,0][1,3][-1,1][0,2][0,2][-1,1][5,7][-3,-1][-4,-2][4,6]).
In this game, no player has a dominant strategy; that is, there is no strategy which is always better than any other strategy, for any profile of other players' actions. Additionally, since
(3.2)⋁i=1,2⋀j=1,2,…,5g(Ii,IIj)=⋁{[-4,-2],[-3,-1]}=[-3,-1],⋀j=1,2,…,5⋁i=1,2g(Ii,IIj)=⋀{[1,3],[0,2],[0,2],[5,7],[4,6]}=[0,2],G has no saddle point.If playerI's optimal strategy is x=(t,1-t), t∈[0,1], then for j=1,2,…,5, we get (3.3)ϕj(t)=g(x,IIj)=tg1j+(1-t)g2j.
Hence, (3.4)ϕ1(t)=[1-3t,3-3t],ϕ2(t)=[-t,2-t],ϕ3(t)=[-1+t,1+t],ϕ4(t)=[-3+8t,-1+8t],ϕ5(t)=[4-8t,6-8t].
We can show this graphically, plotting each payoff as a function of t (see Figure 2). Then, we get (3.5)ψ:[0,1]⟶IR,ψ(t)=⋀{ϕ1(t),ϕ2(t),ϕ3(t),ϕ4(t),ϕ5(t)}={ϕ4(t),t∈[0,27),ϕ3(t),t∈[27,12),ϕ1(t),t∈[12,35),ϕ5(t),t∈[35,1].
see Figure 3.Figure 2
Graph ofϕj(t), j=1,…,n.Figure 3
Graph ofψ(t).Now, we can calculate the⋁{ψ(t)} on [0,1]; that is, we can find the value of the game (3.6)ν*=⋁t∈[0,1]{ψ(t)}.Since, the functionψ(t) attains its maximum at t*=1/2, we obtain (3.7)ν*=⋁t∈[0,1]ψ(t)=ϕ1(12)=[-12,32].Furthermore, the optimal strategy of playerI is x*=(t*,1-t*)=(1/2,1/2).On the other hand,(3.8)g(x*,II1)=[-12,32]=ν*,g(x*,II2)=[-12,32]=ν*,g(x*,II3)=[-12,32]=ν*,g(x*,II4)=[1,3]≠ν*,g(x*,II5)=[0,2]≠ν*.Therefore, using the property of worthwhile strategies, we obtain that only pure strategiesII1, II2, and II3 are worthwhile strategies of player II.Ify*=(y1,y2,y3,0,0)∈Y5 is optimal strategy of player II, then the systems (3.9){y1+y2+y3=1,g(I1,y*)=ν*,g(I2,y*)=ν*,y1>0,y2>0,y3>0⟹{y1+y2+y3=1,[-2y1-y2,y2+2y3]=[-12,32],[y1-y3,3y1+2y2+y3]=[-12,32],y1>0,y2>0,y3>0
are valid. Thus, (3.10)y*=(-12+s,32-2s,s,0,0),12<s<34
is optimal strategy of player II.As a consequence, we obtain(3.11)((12,12),(-12+s,32-2s,s,0,0),[-12,32]),12<s<34,
as the solution of the game (3.1).


## 4. Conclusion

In this paper, we have adapted graphical method for matrix games to interval matrix games by means of acceptability index notion. It is showed that by means of this method, solution of2×n or m×2 interval matrix games can be easily calculated. Since the method can be easily programmed, it is very useful for interval matrix games even though players have at most two pure strategies after domination.



---

*Source: 260490-2011-07-10.xml*