Nash Equilibrium Seeking with Non-doubly Stochastic Communication Weight Matrix
Nash Equilibrium Seeking with Non-doubly Stochastic Communication Weight Matrix
复制标题
非双随机通信权重矩阵的纳什均衡寻求
DOI：
10.4108/eai.13-7-2018.158526
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Lacra Pavel
中科院分区：
文献类型：
--
作者：
Farzad Salehisadaghiani;Lacra Pavel
提出了一种网络博弈的分布式纳什均衡搜索算法。我们假设每个玩家都可以获得关于其他玩家行动的不完全信息。玩家通过强连接有向图进行通信，以根据八卦通信协议向/从其他本地玩家发送/接收对其他玩家的动作的估计。针对博弈双方信息交换不对称的特点，定义了非双(行)随机权重矩阵。我们证明，由于非双重随机性，不存在精确收敛。然后，我们给出了该算法几乎必然收敛于博弈的纳什均衡的证明。此外，我们将该算法推广到图对策中，其中所有玩家的代价函数仅依赖于干扰有向图上的局部相邻玩家。我们在通信有向图上设计了一个假设，使得玩家能够更新干扰其成本函数的玩家的所有估计。证明了通信有向图需要是干扰有向图的传递约简的超集。最后，通过对一个社交媒体行为案例的仿真，验证了算法的有效性。
A distributed Nash equilibrium seeking algorithm is presented for networked games. We assume an incomplete information available to each player about the other players’ actions. The players communicate over a strongly connected digraph to send/receive the estimates of the other players’ actions to/from the other local players according to a gossip communication protocol. Due to asymmetric information exchange between the players, a non-doubly (row) stochastic weight matrix is defined. We show that, due to the non-doubly stochastic property, there is no exact convergence. Then, we present an almost sure convergence proof of the algorithm to a Nash equilibrium of the game. Moreover, we extend the algorithm for graphical games in which all players’ cost functions are only dependent on the local neighboring players over an interference digraph. We design an assumption on the communication digraph such that the players are able to update all the estimates of the players who interfere with their cost functions. It is shown that the communication digraph needs to be a superset of a transitive reduction of the interference digraph. Finally, we verify the efficacy of the algorithm via a simulation on a social media behavioral case.