Empirical Centroid Fictitious Play: An Approach For Distributed Learning In Multi-Agent Games

Abstract

The paper is concerned with distributed learning in large-scale games. The well-known fictitious play (FP) algorithm is addressed, which, despite theoretical convergence results, might be impractical to implement in large-scale settings due to intense computation and communication requirements. An adaptation of the FP algorithm, designated as the empirical centroid fictitious play (ECFP), is presented. In ECFP players respond to the centroid of all players' actions rather than track and respond to the individual actions of every player. Convergence of the ECFP algorithm in terms of average empirical frequency (a notion made precise in the paper) to a subset of the Nash equilibria is proven under the assumption that the game is a potential game with permutation invariant potential function. A more general formulation of ECFP is then given (which subsumes FP as a special case) and convergence results are given for the class of potential games. Furthermore, a distributed formulation of the ECFP algorithm is presented, in which, players endowed with a (possibly sparse) preassigned communication graph, engage in local, non-strategic information exchange to eventually agree on a common equilibrium. Convergence results are proven for the distributed ECFP algorithm.

Submitted to the IEEE Transactions on Signal Processing

References in corpus (1)

• Graphical Models for Game Theory

Cited by in corpus (14)

• A Passivity-Based Approach to Nash Equilibrium Seeking over Networks
• Distributed Nash equilibrium seeking for aggregative games with coupled constraints
• A distributed primal-dual algorithm for computation of generalized Nash equilibria with shared affine coupling constraints via operator splitting methods
• Distributed Nash Equilibrium Seeking under Partial-Decision Information via the Alternating Direction Method of Multipliers
• Fast generalized Nash equilibrium seeking under partial-decision information
• Bayesian Quadratic Network Game Filters
• Robust Distributed Optimization With Randomly Corrupted Gradients
• Nash Equilibrium Seeking Over Directed Graphs
• Nash equilibrium seeking under partial-decision information over directed communication networks
• A Computationally Efficient Implementation of Fictitious Play for Large-Scale Games
• From Weak Learning to Strong Learning in Fictitious Play Type Algorithms
• Distributed Fictitious Play for Optimal Behavior of Multi-Agent Systems with Incomplete Information
• Decentralized Fictitious Play in Near-Potential Games with Time-Varying Communication Networks
• Smooth Fictitious Play in $N\times 2$ Potential Games