Subscribe Now Subscribe Today
Short Communication
 

Honey Bees Foraging Optimization for Mixed Nash Equilibrium Estimation



Ramin Ayanzadeh, Azam S. Zavar Mousavi and Hamidreza Navidi
 
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail
ABSTRACT

Concept of solving games is to find a set of equilibrant strategies in which, players have no interest to refuse it. In static games, strategies intended by players are unspecified and a player’s pay-off is affected by other players’ strategies. Thus, analyzing opponent’s capabilities during decision making process is critical. It's clear that if the number of players or the cardinality of strategy sets increases, solving a game based on traditional approaches are impossible most of the times. Therefore, in this study a novel approach based on honey bees foraging optimization algorithms is proposed to solve static games with complete information to estimate pure and mixed Nash equilibrium. In proposed approach, equilibrium points of game are represented by food sources to be probed by honey bees in optimization process. To verify and validate method, several simulations are performed on some study cases. Simulation results prove that suggested approach generates more desirable solutions in precision and stability than other metaheuristics.

Services
Related Articles in ASCI
Search in Google Scholar
View Citation
Report Citation

 
  How to cite this article:

Ramin Ayanzadeh, Azam S. Zavar Mousavi and Hamidreza Navidi, 2011. Honey Bees Foraging Optimization for Mixed Nash Equilibrium Estimation. Trends in Applied Sciences Research, 6: 1352-1359.

DOI: 10.3923/tasr.2011.1352.1359

URL: https://scialert.net/abstract/?doi=tasr.2011.1352.1359
 
Received: April 07, 2011; Accepted: July 15, 2011; Published: September 28, 2011



INTRODUCTION

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 al., 2011).

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, 2008).

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 player’s 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).

Image for - Honey Bees Foraging Optimization for Mixed Nash Equilibrium Estimation
(1)

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,…) (Cheheltani 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:

Image for - Honey Bees Foraging Optimization for Mixed Nash Equilibrium Estimation
(2)

In such a condition, the mixed strategy Image for - Honey Bees Foraging Optimization for Mixed Nash Equilibrium Estimation will be the best response for first player against the best strategy of second player, if and only if, Eq. 3 is valid.

Image for - Honey Bees Foraging Optimization for Mixed Nash Equilibrium Estimation
(3)

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 Image for - Honey Bees Foraging Optimization for Mixed Nash Equilibrium Estimation. 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., 2009).

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 Image for - Honey Bees Foraging Optimization for Mixed Nash Equilibrium Estimation 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 consisted of:

Image for - Honey Bees Foraging Optimization for Mixed Nash Equilibrium Estimation

floating numbers. Initial values of food sources are generated randomly with uniform distribution.

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, Image for - Honey Bees Foraging Optimization for Mixed Nash Equilibrium Estimation 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 Image for - Honey Bees Foraging Optimization for Mixed Nash Equilibrium Estimation. 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.

EXPERIMENTAL RESULTS

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.

Image for - Honey Bees Foraging Optimization for Mixed Nash Equilibrium Estimation
(4)

Image for - Honey Bees Foraging Optimization for Mixed Nash Equilibrium Estimation
(5)

Table 1: Statistical indicators in solving numerical problem
Image for - Honey Bees Foraging Optimization for Mixed Nash Equilibrium Estimation

Table 2: Expected pay-off in coin flip
Image for - Honey Bees Foraging Optimization for Mixed Nash Equilibrium Estimation

Table 3: Statistical indicators in solving coin flip game
Image for - Honey Bees Foraging Optimization for Mixed Nash Equilibrium Estimation

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.

CONCLUSION

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.

REFERENCES

1:  Afshar, A., O.B. Haddad, M.A. Marino and B.J. Adams, 2007. Honey-bee mating optimization (HBMO) algorithm for optimal reservoir operation. J. Franklin Inst., 344: 452-462.
CrossRef  |  

2:  Attar, H., 2010. Product innovation and the games of uncertainty and risk. J. Applied Sci., 10: 801-812.
CrossRef  |  Direct Link  |  

3:  Ayanzadeh, R. and H. Navidi, 2011. Solving static games with complete information using honey bees foraging optimizations. Proceedings of 2nd International Conference on Contemporary Issues in Computer and Information Sciences (CICIS 11), Zanjan, Iran.

4:  Ayanzadeh, R. and S. Setayeshi, 2009. Using cellular learning automata as imitation operator in cellular memetic optimization algorithms. Proceedings of the 3rd Joint Congress on Fuzzy and Intelligent Systems, Yazd, Iran.

5:  Ayanzadeh, R., E. Shahamatnia and S. Setayeshi, 2009. Determining optimum queue length in computer networks by using memetic algorithms. J. Applied Sci., 9: 2847-2851.
CrossRef  |  Direct Link  |  

6:  Ayanzadeh, R., E. Shahamatnia, S. Setayeshi and M. Teshnehlab, 2008. A novel optimization algorithm based on cellular automata and particle swarm optimization. Proceedings of 2nd Joint Congress on Fuzzy and Intelligent Systems. Tehran, Iran.

7:  Billard, E.A., 1997. Chaotic behavior of learning automata in multi-level games under delayed information. Syst. Man Cybern., 2: 1412-1417.
CrossRef  |  

8:  Cheheltani, S.H. and S.M. Ebadzadeh, 2010. Immune based approach to find mixed Nash equilibrium in normal form games. J. Applied Sci., 10: 487-493.
CrossRef  |  Direct Link  |  

9:  Darooei, A. and M.R. Khayyambashi, 2010. Design and implementation of an agent-based trading mechanism. Inform. Technol. J., 9: 224-235.
CrossRef  |  Direct Link  |  

10:  Haddad, B. and A. Afshar, 2004. MBO (Marriage Bees Optimization), A new heuristic approach in hydro systems design and operation. Proceedings of 1st International Conference on Managing Rivers in the 21st Century: Issues and Challenges, September 21-23, 2004, Penang, Malaysia, pp: 499-504

11:  Lo, C.Y., 2008. Multi-agent conflict coordination using game bargain. Inform. Technol. J., 7: 234-244.
CrossRef  |  Direct Link  |  

12:  Moghaddas, Y., R. Ayanzadeh and A.T. Hagigat, 2008. A new algorithm for improving the uniformity of random number generators based on calculation with monte carlo method. Proceedings of the of 2nd Joint Congress on Fuzzy and Intelligent Systems, (FIS'08), Tehran, Iran.

13:  Naderi, F., A. Heidarie, L. Bouron and P. Asgari, 2010. The efficacy of play therapy on ADHD, anxiety and social maturity in 8 to 12 years aged clientele children of ahwaz metropolitan counseling clinics. J. Applied Sci., 10: 189-195.
CrossRef  |  Direct Link  |  

14:  Navidi, H., S. Ketabchi and M.M. Bidgoli, 2011. An Introductuin to Game Theory. University of Shahed Publication, Iran

15:  Poznyak, A.S. and K. Najim, 2002. Learning through reinforcement for N-person repeated constrained games. IEEE Trans. Syst. Man Cybern. Part B: Cybernetics, 32: 759-771.
CrossRef  |  

16:  Rahmatizadeh, S., H. Shah-Hosseini and H. Torkaman, 2009. The ant-bee routing algorithm: A new agent based nature-inspired routing algorithm. J. Applied Sci., 9: 983-987.
CrossRef  |  Direct Link  |  

17:  Rasmusen, E., 2007. Games and Information: An Introduction to Game Theory. Wiley-Blackwell, USA, ISBN: 9781405136662, Pages: 528

18:  Saguan, M., S. Plumel, P. Dessante, J.M. Glachant and P. Bastard, 2004. Genetic algorithm associated to game theory in congestion management. Proceedings of the International Coonference on Probabilistic Methods Applied to Power Systems, Sept. 12-16, Iowa, USA, pp: 415-420

19:  Schifi, J.L., 2008. Cellular Automata: A Discrete View of the World. Wiley-Interscience, USA., ISBN-13: 9780470168790, Pages: 252

20:  Lijun, Y., Z. Li and X. Yuan, 2009. Study on method of robust multidisciplinary collaborative decision for product design. Inform. Technol. J., 8: 441-452.
CrossRef  |  Direct Link  |  

21:  Zadeh, H.M., A. Ghaheri and L. Karp, 2009. A model of non-cooperative dynamic game to conflict resolution among common natural resource operators. J. Applied Sci., 9: 2156-2161.
CrossRef  |  Direct Link  |  

©  2021 Science Alert. All Rights Reserved