A computationally efficient implementation of fictitious play in a distributed setting
A computationally efficient implementation of fictitious play in a distributed setting
复制标题
分布式环境中虚拟游戏的高效计算实现
DOI：
10.1109/eusipco.2015.7362542
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
J. Xavier
中科院分区：
文献类型：
--
作者：
Brian Swenson;S. Kar;J. Xavier
本文研究了多人博弈中纳什均衡的分布式学习问题。经典的虚拟游戏（FP）算法是不切实际的大型游戏，由于苛刻的通信要求和高计算复杂度。FP的一个变体，旨在减轻这两个问题。通过使用计算效率高的基于蒙特-卡罗的最佳响应规则来减轻复杂性。通过在基于网络的分布式设置中实现该算法来缓解苛刻的通信问题，其中玩家对玩家的通信被限制在由（可能是稀疏的，但连接的）预先分配的通信图确定的相邻玩家的局部子集。通过一个仿真例子证明了结果。
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.