UsingStochastic AlTechniques toAchieve Unbounded Resolution inFinite Player Goore GamesanditsApplications
Ole‐Christoffer Granmo · 2007
TheGooreGame(GG)introduced byM. L. Tsetlin in1973hasthefascinating property thatitcanbe resolved ina completely distributed mannerwithnointer- communication between theplayers. Thegamehasrecently foundapplications inmanydomains, including thefield of sensor networks andQuality-of-Service (QoS) routing. Inactual implementations ofthesolution, theplayers aretypically replaced byLearning Automata (LA).Theproblem withthe existing reported approaches isthattheaccuracy ofthesolution achieved isintricately related tothenumberofplayers partici- pating inthegame-which, inturn, determines theresolution. Inotherwords, anarbitrary accuracy canbeobtained onlyif thegamehasaninfinite numberofplayers. Inthis paper, we showhowwe canattain anunbounded accuracy fortheGG byutilizing nomorethanthree stochastic learning machines, andbyrecursively pruning thesolution spacetoguarantee thattheretained domaincontains thesolution tothegame withaprobability asclose tounity asdesired. Thepaperalso conjectures onhowthesolution canbeapplied tosomeofthe application domains.