Achieving Unbounded Resolution in Finite Player Goore Games Using Stochastic Automata, and Its Applications

Abstract

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

Subject Classifications:

• 60J10
• 60J20
• 68M15

ACKNOWLEDGMENTS

We would like to take this opportunity to record our gratitude to the Associate Editor and the anonymous referees of the original version of this article for their painstaking reviews. The changes that they requested certainly improved the quality of this article, and the earlier works where some of these results were reported (Oommen et al., 2006, 96; Oommen and Granmo, 2009). As is accepted in the field, the conference versions (Oommen et al., 2006, 99) were published when the research was at a preliminary stage in order to get a claim on the results. This occurred years before the final theoretical results, published here, were fully available. This work was partially supported by the Natural Sciences and Engineering Research Council of Canada.

Notes

Recommended by N. Mukhopadhyay