2013/01/15 by Michalis Smyrnakis, Smyrnakis, Michalis · 1 citation
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Artificial Intelligence in Games #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Multiagent Systems (cs.MA) #Optimization and Control (math.OC) #Reinforcement Learning in Robotics
paper · pdf · doi:10.48550/arxiv.1301.3347
openalex publication_date 2013/01/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Decentralised optimisation tasks are important components of multi-agent systems. These tasks can be interpreted as n-player potential games: therefore game-theoretic learning algorithms can be used to solve decentralised optimisation tasks. Fictitious play is the canonical example of these algorithms. Nevertheless fictitious play implicitly assumes that players have stationary strategies. We present a novel variant of fictitious play where players predict their opponents' strategies using Extended Kalman filters and use their predictions to update their strategies. We show that in 2 by 2 games with at least one pure Nash equilibrium and in potential games where players have two available actions, the proposed algorithm converges to the pure Nash equilibrium. The performance of the proposed algorithm was empirically tested, in two strategic form games and an ad-hoc sensor network surveillance problem. The proposed algorithm performs better than the classic fictitious play algorithm in these games and therefore improves the performance of game-theoretical learning in decentralised optimisation.