Game theory is a branch of applied mathematics which has grown in context of
economic science and took special place in various fields such as economy, biology,
psychology, computer science, industry, political science, social science, philosophy,
etc. Game theory has provided a framework for real world problems to be formulated
as a game. A game is consisted of players set who can choose their actions among
their strategy sets. The most important issue is that pay-off or result for
each player is totally dependent on both his strategies as well as other players
strategies (Rasmusen, 2007; Navidi et
Depending on whether players are aware of opponent choices or not; players
can play simultaneously or in turn; games are sorted out in to static and dynamic
categories. Also based on various types of knowledge sharing among players,
games can be classified in categories of games with complete information, games
with incomplete information, symmetric and asymmetric games. During last decades,
researchers have paid special attention to game theory that has led to introduce
variety of games such as iterative games, bargain and signal games (Rasmusen,
2007; Navidi et al., 2011).
In game theory, the purpose of solving games is to obtain strategies that none
of the players are willing to deviate from it (Darooei and
Khayyambashi, 2010; Lo, 2008; Zadeh
et al., 2009). Despite the fact that these strategies are not necessarily
the best choice of players, they are considered desirable regarding opponents
strategies. Such strategies are said equilibrium points of game. Objective of
solving games with more than one equilibrium points or no pure equilibrium point
is to find combinational selections from strategies sets based on a probability
function. This solution is called mixed Nash equilibrium (Naderi
et al., 2010; Navidi et al., 2011).
Game Theory serves significant functionality in various fields of science,
so several attempts have been done to provide methods of solving games and estimating
Nash equilibriums (Attar, 2010; Naderi
et al., 2010; Lijun et al., 2009).
First efforts were mostly analytical works which have tried to acquire equilibrium
points based on mathematical approaches, generally by solving equation systems
(Rasmusen, 2007; Navidi et al.,
2011). The main difficulty of solving games with analytical methods is that
the complexity of problem and dimensions of state space has exponential relationship
with the number of players and cardinality of strategies sets. This means, in
real world problems that number of players or cardinality of strategies sets
are large, so analytical approaches are not able to find the results in worthy
of time (Cheheltani and Ebadzadeh, 2010; Lo,
To overcome these constraints, several works have been performed during last
three decades. These efforts employ numerical methods of problem solving in
real world applications. Metaheuristics are successful scenarios which led some
intelligent tools; such as evolutionary algorithms; which are being applied
extensively for solving games (Ayanzadeh et al., 2008;
Saguan et al., 2004). In addition, advantages
in artificial intelligence during last decades have led to use cellular automata
(Schifi, 2008) and learning automata (Billard,
1997) as modeling and optimization techniques (Ayanzadeh
and Setayeshi, 2009).
Honey bees foraging optimization and honey bees mating optimization algorithms
are novel approaches that have attracted focus of many researchers. These algorithms
benefit from exploring the search space both locally and globally (Afshar
et al., 2007; Ayanzadeh and Navidi, 2011).
Accordingly, in this study a new approach based on honey bees foraging optimization
algorithm is proposed to solve static game with complete information and simulation
results prove the validity of suggested method.
Nash equilibrium in static games: Static games with complete information
are multi-player games that players choose their strategies from legal strategies
sets, without having any knowledge about opponents' strategies. The pay-off
for players depends both on players strategy and other players strategies.
In addition, knowledge of the game is shared among all players. However, in
games with incomplete information players have partial knowledge (Rasmusen,
2007; Navidi et al., 2011).
Regardless of representation or modeling types, objective of solving static
games with complete information is to obtain an equilibrium point which deviating
from that will not be in favor of any players. In other words, if the strategies
set of player i be Si and corresponding pay-off has been represented
by ui (s1, s2,....) then selected strategy
() will be an equilibrium point of game if and only if, for all players Eq.
1 is satisfied. Obviously in such circumstances, assuming rational behavior
by players, none of the players are willing to deviate from the Nash equilibrium
(Rasmusen, 2007; Navidi et al.,
2011; Cheheltani and Ebadzadeh, 2010).
In games with no or more than one Nash equilibrium, instead of having pure
Nash equilibrium there will be a mixed Nash equilibrium. In better words, if
there is no pure Nash equilibrium for a game, then player will choose his strategy
from a set of strategies based on probability functions Pi. In such
situations, if strategy set for player i is Si = (s1i,
s2i,....) the player might choose his strategy from this set with
the probability of Pi = (p1i, p2i,
and Ebadzadeh, 2010; Navidi et al., 2011).
For example, in a two players game, if first player chooses his strategy (s11, s21) based on P1 = (p11, p21) and second player chooses his strategy (s12, s22,
.) based on P2 = (p12, p22
) then expected pay-off for player i will be calculated by Eq. 2:
In such a condition, the mixed strategy
will be the best response for first player against the best strategy of second
player, if and only if, Eq. 3 is valid.
where, Δ (S1) is the partition of mixed or hybrid strategies
for first player. The best response for second player is analogous to first
player as well. Now if each player plays with his best mixed strategy, outcome
of the game will be mapped on mixed Nash equilibrium .
It is obvious that pure Nash equilibrium is a special kind of mixed Nash equilibrium
which one of the elements in Pi = (p1i, p2i,....)
is equal to one and others are zero (Cheheltani and Ebadzadeh,
2010; Navidi et al., 2011).
Honey bees foraging optimization: Honey bees are the most famous insects
from scientific and economical perspective. They are the only insects that have
been tamed by man kind in order to produce honey. Honey bees mostly construct
hives in forests, mountains, trunks of trees and cracks of rocks. Each hive
is constructed by vertical slots where each slot is made by beeswax. Each slot
has both levels and each of these levels is constructed from enormous hexagons
(Ayanzadeh and Navidi, 2011; Afshar
et al., 2007).
In a honey bee hive, ten thousands to hundred thousands of bees may live socially.
But, among them just the queen has fertility capability. Alongside the queen
bee, there exist tens or hundreds of male bees. Reset of population are worker
bees who are responsible for preparing food. Moreover, identifying the queen
and other bees for notifying danger, position of new food sources, etc., is
necessary for social life (Ayanzadeh and Navidi, 2011).
For this purpose, a group of worker bees are selected as scouts and begin to search the environment of hive. The basic points about the scout bees are that they have no initial knowledge for search. Scout bees track various flowers in their flight path, to evaluate the desirability of food sources based on parameters like distance from hive, quality of nectar, etc.
Scout bees collect the nectar and back to hive. Among scout bees, those who
have found better food sources inform worker bees about the position of food
sources. Then, some scout bees accompany a few worker bees to the food sources
they have found. Number of worker bees who accompany the scout bees is directly
related to the quality of food sources. In fact, scout bees who have found more
desirable food sources will be accompanied by more worker bees (Afshar
et al., 2007; Haddad and Afshar, 2004).
Worker bees who are selected to go along scout bees probe vicinity of food
source to exploit better food sources. Worker bees like scout bees inform other
bees of hive about the position and quality of new food sources (Ayanzadeh
and Navidi, 2011; Haddad and Afshar, 2004).
Message among honey bees has its own special formality. For this purpose, there
is a specific section in hive; dancing hall; in which bees inform others using
circular dance or moving their stomach. If distance from food source is less
than 500 m, bees dance circularly; otherwise they move their stomach like 8
shapes. Replication of dances indicates the abundant of food sources (Afshar
et al., 2007; Haddad and Afshar, 2004; Ayanzadeh
and Navidi, 2011).
Studies about social lives of bees show that these insects always exploit abundant food sources with minimal energy consumption. Honey bee foraging optimization algorithm is swarm intelligence type algorithms which is inspired by social lives of bees while finding food. In this approach, the solutions are represented in form of food sources in order to be applied by artificial bees to find their optimal point.
Honey bees foraging optimization algorithms initialize food sources with random;
uniform distribution; values. Then, food sources are sorted based on their desirability
and will be sorted out in two categories of desirable and undesirable. For instance,
first k best food sources are favorable and the rest are unfavorable (Poznyak
and Najim, 2002; Ayanzadeh and Navidi, 2011; Rahmatizadeh
et al., 2009).
Desirable food sources will be exploited by local search algorithms. On the
other hand, undesirable food sources will be explored by global search algorithms.
In fact, global search is a simulation of scout bees, while the local search
is a simulation of worker bees. Despite the fact that number of scout and worker
bees are fixed in general honey bees foraging optimization algorithms, they
can be calculated by nectar amount of food sources. Local and global searches
are employed in an iterative manner on food sources till terminate conditions
are met (Ayanzadeh and Navidi, 2011).
HBFO for estimating mixed nash equilibrium: Honey bees foraging optimization
algorithm is consisted of both global and local search to explore and exploit
search space, respectively. Obviously due to variety of local and global search
methods, several instances of honey bees foraging optimization algorithms could
be considered. Honey bees optimization algorithms are similar to memetic algorithms
in local and global search trade-off (Ayanzadeh et al.,
The proposed approach employs hill climbing algorithm as local exploitation and random search as global exploration algorithms. As the search space is continuous, hill climbing algorithm generates k neighbors of a solution randomly based on a continuous random variable with normal distribution. Furthermore, these k random neighbors take part in a tournament to be elected for replacing with current solution. This process continues until a termination condition is met, for example, when there is no neighbor better than the current solution. In this algorithm, parameter k is number of assigned worker bees for each desirable food source.
P*1i among new and current solutions, the best food source is returned as a result of global search. Parameter m specifies number of allocated scout bees for undesirable food sources.
In applied method, food sources represent potential responses of problem. In
other words, each food source specifies
that can be considered as mixed Nash equilibrium point. Therefore, in games
with N players, if the cardinalities of players' strategies sets are specified
by n1, n2,...., nN then food sources will be
floating numbers. Initial values of food sources are generated randomly with
Furthermore, in games with continuous values for elements of strategies sets; players choose floating numbers as their strategies; probabilities of mixed Nash equilibrium will be mapped on players' strategies. It is necessary to mention that summation of probabilities for each player must be equal to one. Thus, after local and global searches, food sources are normalized for mapping probabilities to the range of [0, 1]. On the other hand, normalization process will not be necessary in games with continuous strategies.
Evaluating nectar amount of food sources is the most important aspect of proposed
approach which assesses the quality of responses. In other words, nectar amount
serves functionality of fitness or cost function in traditional evolutionary
algorithms. Additionally, proposed nectar amount function is a benchmark to
compare the quality of food sources and is inspired from calculations with Monte
Carlo method (Moghaddas et al., 2008).
As mentioned in second section in which, mixed Nash equilibrium in static games
with complete information is discussed,
will be mixed Nash equilibrium if and only if Eq. 3 is satisfied
for all of the players. Evaluating solutions for satisfying Nash conditions
in continues state space is rather difficult. Therefore, proposed nectar amount
function is based on a numerical approach.
To overcome these difficulties, a novel method for evaluating resemblance of
food sources with mixed Nash Equilibrium is employed. For this purpose, t random
strategy for player i is generated. Then, each randomly generated strategy is
assumed to be mixed Nash strategy .
For each randomly generated strategy and opponents' strategies; which are represented
by food sources; satisfaction of Eq. 3 is considered. Finally,
percentage of valid randomly generated strategies of all players is calculated
to specify the rate of desirability of food sources.
Here, simulation results of applying honey bees foraging optimization algorithm for solving static games with complete information are presented to evaluate the performance, precision and stability of proposed method. As far as the suggested method is a stochastic approach, so running the algorithm once may not be a suitable benchmark for evaluation and validation purpose. Therefore, proposed algorithm is run several times and statistical indicators of simulation results; such as best, mean and variance; is computed. The best and mean of indicators are used for evaluation of precision. On the other hand, the variance is employed to evaluate the stability of proposed approach.
Experiment one: For this test a standard game which is a numerical example
is applied. The example is a two players game that strategies of players are
in range of [0, 7.5]. The pay-off for first and second players is computed by
Eq. 4 and 5, respectively. Analytical studies
have shown that equilibrium point of the game is (6.3, 6.8). For this simulation
food sources are assumed to be in two dimensional spaces R2.
|| Statistical indicators in solving numerical problem
||Expected pay-off in coin flip
||Statistical indicators in solving coin flip game
As the equilibrium point of game is known, Euclidian distance between equilibrium point and final simulation result is considered as system error. It is obvious that in real world problems equilibrium point is not available. Thus, these kind of standard benchmark problems are employed to make calculation of possible system error.
Table 1 presents statistical indicators of 30 times running the Genetic Algorithm (GA), Particle Swarm Optimization (PSO) and proposed Honey Bee Foraging Optimization (HBFO) in solving the mentioned problem. In order to make the comparisons more meaningful, the parameters of algorithms are considered similarly. As can be seen from the results, suggested method has better results in comparison with genetic algorithms and particle swarm optimization. The variance also proves that honey bees foraging optimization method is more stabile.
Experiment two: This experiment tries to evaluate performance of proposed method in solving a famous game of coin flip. Coin flip is two players game that each player chooses one side of the coin. Players have no information about opponent's choice or strategy. If players make same decision; coins are in same situation; second player will be known as winner. Otherwise, first player will be considered as winner. Table 2 illustrates expected pay-off for players in coin flip game. It is obvious that coin flip game has no pure Nash equilibrium. Thus, it must have a mixed Nash equilibrium point. Analytical studies have proved that (0.5, 0.5) is mixed Nash equilibrium of the game.
Table 3 expresses statistical indicators driven from 30 times running Genetic Algorithm (GA), Particle Swarm Optimization (PSO) and Honey Bees Foraging Optimization (HBFO) in solving coin flip game. Demonstrated indicators are computed based on Euclidian distance between final simulation result and actual mixed Nash equilibrium point.
In static games with complete information players make decision synchronously
in which, they have no information about opponents' strategies through the game.
Furthermore, knowledge of the game is shared among players. Thus, none of the
players have partial or incomplete knowledge about the game. To solve these
kind of games, an equilibrium point of players' strategies must be found that
refusing is not useful for any one. Games with no or more than one pure Nash
equilibrium always have a mixed Nash equilibrium strategy. Thus, players will
choose their strategies based on probability functions.
Solving static games with complete information serves an essential functionality in real world problem solving especially in economy. Therefore, several efforts have been performed to propose effective approaches for estimating mixed Nash equilibrium in static games with complete information. Traditional methods face vast variety of difficulties. For instance, complexity of search space has exponential relationship with number of players and cardinality of strategies sets. Consequently, large scale real world problems may be unsolvable by traditional techniques.
In this study, a novel approach based on honey bees foraging optimization algorithm; which is inspired by natural bees society; is proposed to estimate mixed Nash equilibrium in static games with complete information. For this purpose, potential solutions are represented by food sources and artificial bees try to look for optimum mixed Nash equilibrium with applying both local and global search heuristics. To evaluate nectar amount of food sources, an innovative method is employed that is based on calculations with Monte Carlo method.
To verify and validate proposed approach, several simulations was performed and applied on some standard benchmark problems. Simulation results proved that honey bees foraging optimization method generate more desirable results in comparison with genetic algorithms and particle swarm optimization. In addition, analytical studies showed that proposed method behaves more stable than other traditional methods.
Proposed honey bees foraging optimization algorithm is a numerical approach that employs both local and global search methods in an optimum manner. In the same way, other novel metaheuristics; such as artificial immune systems, invasive weed optimization and biogeography based optimization; could be enhanced and employed for similar applications.