Page 77 - Innovations in Intelligent Machines

66 P.B. Sujit et al.
with increase in q and also increase in number of players. Hence, solving the
algebraic equations becomes computationally time consuming. In order to
reduce computational time we use the concept of domination [31].
Dominating Strategies : There are certain strategies for an agent which yield
less profit than other strategies. For instance, consider agent A i choosing path
k
l
P that has higher benefit than path P , for all possible combination of the
i
i
l
paths of the rest of the N −1 agents. Then, we can eliminate path P without
i
affecting the equilibrium solution. Since the objective of the searchers is to
maximize their benefits, we are eliminating a strategy with lower benefit. In
i
general, for A i , considering the search effectiveness function m , we say that
l
k
path P dominates path P ,if
i i
q
l
i
k
i
m (P 1 ,...,P ,...,P N ) ≥ m (P 1 ,...,P ,...,P N ), ∀ P j ∈P ,j = i (39)
j
i
i
and if, for at least one j, the strict inequality holds. Eliminating dominated
strategies will reduce the computational time required to compute the mixed
equilibrium strategy. The concept of dominating strategies in non-zero sum
games as formulated above is similar to the dominating strategies as formu-
lated for zero sum games [31]. The dominating strategies concept is applicable
only for noncooperative games and not for cooperative and security strategies.
Coalitional Nash Strategies
In this model, we assume that agent A i is playing against the coalition of
the rest of the N − 1 agents. The game is modelled as a bimatrix game
1,i
which consists of two search effectiveness matrices, M 1,i = {m } and M 2,i =
kl
2,i 1,i
{m }. The matrix M represents the benefit obtained by agent A i .Every
kl
ˆ
k ˆ
element m 1,i = V i (P , P), P = {(P 1 ,P 2 ,...,P N )|P j = P i ,j =1,...,N},
kl i q
represents the benefit obtained by agent A i choosing path P k ∈P while
i i
N q 2,i
the coalition chooses a strategy l, l =1, 2,... , | j=1 P |. The matrix M
j
j =i
2,i
represents the benefit obtained by the coalition and every element m =
kl
N k ˆ
j=1 V j (P , P). The agent A i assumes the coalition to be a single player.
i
j =i
The players (A i and the coalition) arrive at their decisions independently. In
such a situation the equilibrium solution can be stated as: A pair of strategies
∗
{row k , column l } is said to constitute a noncooperative (Nash) equilibrium
∗
solution to the bimatrix game, if the following pair of inequalities are satisfied,
q N q
∀ k =1, 2,... , |P | and ∀ l =1, 2,... , | j=1 P |
i j
j =i
1,i 1,i 2,i 2,i
m ∗ l ∗ ≥ m kl ∗, (40)
k m ∗ l ∗ ≥ m ∗ l
k
k
∗
The agent A i considers strategy k as its equilibrium strategy. Each agent
computes the two search effectiveness matrices and considers k as its equi-
∗
librium strategy. The dimension for the search effectiveness matrix is