2011/12/11 by Michalis Smyrnakis, Smyrnakis, Michalis, David S. Leslie +1
Decision Sciences · Social Sciences · #Advanced Bandit Algorithms Research #Experimental Behavioral Economics Studies #FOS: Computer and information sciences #Game Theory and Applications #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Multiagent Systems (cs.MA)
paper · pdf · doi:10.48550/arxiv.1112.2315
openalex publication_date 2011/12/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
It is now well known that decentralised optimisation can be formulated as a potential game, and game-theoretical learning algorithms can be used to find an optimum. One of the most common learning techniques in game theory is fictitious play. However fictitious play is founded on an implicit assumption that opponents' strategies are stationary. We present a novel variation of fictitious play that allows the use of a more realistic model of opponent strategy. It uses a heuristic approach, from the online streaming data literature, to adaptively update the weights assigned to recently observed actions. We compare the results of the proposed algorithm with those of stochastic and geometric fictitious play in a simple strategic form game, a vehicle target assignment game and a disaster management problem. In all the tests the rate of convergence of the proposed algorithm was similar or better than the variations of fictitious play we compared it with. The new algorithm therefore improves the performance of game-theoretical learning in decentralised optimisation.