Page 75 - Innovations in Intelligent Machines

64 P.B. Sujit et al.
(iv) Cooperative Strategy: The agents communicate with each other and
decide collectively (jointly) to take the best possible action. This is also the
centralized decision making case.
(v) Greedy Strategy: Agents do not communicate among themselves and use
greedy strategy. An agent does not consider the effect of the possible actions
of the others agent and selects an action that yields the maximum benefit to
itself. This strategy is used for comparison purposes only.
(vi) Globally Optimal Strategy: The game theoretical strategies are based on
local information up to q steps. Hence, the solution is optimal for these q steps
and not globally optimal. We can obtain a globally optimal solution by making
q equal to the largest possible number of steps in an agent’s search path.
This requires huge computational time and also increases the computational
complexity as the domain of the search effectiveness function increases. We
will not use this strategy but, for the interested researcher, some heuristic
algorithms to implement such strategies are discussed in [30].

Non-cooperative N-person Nash Equilibrium Strategy

We define a non-cooperative N-person game in normal form for N agents [31].
i
A N-person game consists of N search effectiveness functions m ,i =1,...,N.
N
1
The ordered N- tuple of real numbers (m (P 1 ,...,P N ),...,m (P 1 ,...,P N ))
denotes the payoff to each agent respectively. The players do not cooperate
with each other and arrive at their decisions independently. In such a sit-
uation the equilibrium solution can be stated as: An N-tuple of strategies
q
{P ,P ,...,P } with P ∈P is said to constitute a noncooperative (Nash)
∗
∗
∗
∗
1 2 N i i
equilibrium solution for an N-person nonzero-sum game, if the following N
q
inequalities are satisfied for all P i ∈P ,i ∈ N.
i
1
1
∗
∗
∗
∗
∗
m 1∗ m (P ,P ,P ,...,P ) ≥ m (P 1 ,P ,...,P N−1 ,P )
∗
∗
2
2
1
3
N
N
2
2
∗
∗
∗
∗
∗
∗
∗
m 2∗ m (P ,P ,...,P ) ≥ m (P ,P 2 ,P ,...,P N−1 ,P )
N
N
1
2
1
3
. . .
. . .
. . .
N
N
∗
∗
∗
∗
∗
∗
∗
m N∗ m (P ,P ,...,P ) ≥ m (P ,P ,P ,...,P N−1 ,P N ) (35)
2
1
1
3
2
N
2∗
The N-tuple (m ,m ,...,m N∗ ) is known as a noncooperative (Nash) equi-
1∗
librium outcome of the N-person game in normal form. The pure strategy
Nash equilibrium may not exist always. In this case we need to compute
mixed strategies which guarantee a solution to the noncooperative game.
Mixed Strategies : A mixed strategy for a player is a probability distribution
on the space of its pure strategies. An allowable strategy for A i is to choose
q
|P |
2
i
i
1
P with probability (w.p.) y , P , w.p. y ,..., P i i w.p. y i q , so that,
i
2
1
i
|P |
i
q
|P |
i
i i
y =1, and 0 ≤ y ≤1 (36)
k
k
k=1