Learning automata-based solutions to the Goore Game and its applications
The Goore Game1 (GG) introduced in  has the fascinating property that it can be resolved in a completely distributed manner with no inter-communication between the players. The game has recently found applications2 in many domains, including the field of sensor networks and Quality-of-Service (QoS) routing. In actual implementations of the solution, the players are typically replaced by Learning Automata (LA). In this Chapter, we shall first briefly survey the field of LA and report the LAbased solutions to the GG. The problem with the existing reported approaches is that the accuracy of the solution achieved is intricately related to the number of players participating in the game - which, in turn, determines the resolution. In other words, an arbitrary accuracy can be obtained only if the game has an infinite number of players, which renders a practical solution infeasible. Thus, we shall describe some of the recent advances, and show how we can attain an unbounded accuracy for the GG by utilizing no more than three stochastic learning machines, and by recursively pruning the solution space to guarantee that the retained domain contains the solution to the game with a probability as close to unity as desired. The Chapter contains the formal algorithms, the proofs of the respective convergence results, and simulation results demonstrating its power. It also conjectures on how the solution can be applied to some of the application domains.
|Keywords||Goore games, Intelligent game playing, Learning automata, Sensor networks and quality-of-service routing|
Oommen, J, & Granmo, O.-C. (Ole-Christoffer). (2009). Learning automata-based solutions to the Goore Game and its applications. In Game Theory: Strategies, Equilibra and Theorems (pp. 183–216).