Achieving Unbounded Resolution in Finite Player Goore Games Using Stochastic Automata, and Its Applications
This article concerns the sequential solution to a distributed stochastic optimization problem using learning automata and the Goore game (also referred to as the Gur game in the related literature). The amazing thing about our solution is that, unlike traditional methods, which need N automata (where N determines the degree of accuracy), in this article, we show that we can obtain arbitrary accuracy by recursively using only three automata. To be more specific, the Goore game (GG) introduced in Tsetlin (1973) 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 applications in many domains, including the field of sensor networks and quality-of-service (QoS) routing, and a brief survey of these applications is included in the article. In actual implementations of the solution, the players are typically replaced by learning automata (LA). The problem with the existing reported approaches is that, as mentioned above, 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. In this article, we 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 article 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, Quality-of-service routing, Sensor networks|
Granmo, O.-C. (Ole-Christoffer), Oommen, J, & Pedersen, A. (Asle). (2012). Achieving Unbounded Resolution in Finite Player Goore Games Using Stochastic Automata, and Its Applications. Sequential Analysis, 31(2), 190–218. doi:10.1080/07474946.2012.665685