Title :
A computationally efficient implementation of fictitious play in a distributed setting
Author :
Brian Swenson;Soummya Kar;João Xavier
Author_Institution :
Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA 15213, USA
Abstract :
The paper deals with distributed learning of Nash equilibria in games with a large number of players. The classical fictitious play (FP) algorithm is impractical in large games due to demanding communication requirements and high computational complexity. A variant of FP is presented that aims to mitigate both issues. Complexity is mitigated by use of a computationally efficient Monte-Carlo based best response rule. Demanding communication problems are mitigated by implementing the algorithm in a network-based distributed setting, in which player-to-player communication is restricted to local subsets of neighboring players as determined by a (possibly sparse, but connected) preassigned communication graph. Results are demonstrated via a simulation example.
Keywords :
"Games","Signal processing algorithms","Heuristic algorithms","Computational complexity","Europe","Signal processing"
Conference_Titel :
Signal Processing Conference (EUSIPCO), 2015 23rd European
Electronic_ISBN :
2076-1465
DOI :
10.1109/EUSIPCO.2015.7362542