Empirical Verification of a Strategy for Unbounded Resolution in Finite Player Goore Games

摘要

This paper presents an experimental verification of a novel, fast and arbitrarily accurate solution to the Goore Game (GG). The latter game, 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 applications 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). 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, implying that arbitrary accuracy can be obtained only if the game has an infinite number of players. In this paper, we experimental demonstrate how we can attain an unbounded accuracy for the GG by utilizing no more than three stochastic learning machines, and by a recursive pruning of the solution space.