基于自旋玻璃理论的网络博弈纯策略纳什均衡计算和社会有效状态实现路径问题研究

Games on network have become of increasing interest in social, economic and physical disciplines in recent years. The relationship between network structure and Nash Equilibrium (NE), one of the most common used solutions to predict the strategic outcomes, is the problem of particular interest. The introduction of a network structure among agents complicates the computation of pure strategy NE. In addition, it is often the fact that the pure strategy NE do not reach the maximum possible total welfare. In fact, pure strategy NE of a network game do correspond to ground-state configurations of a spin glass model. In this proposal, we thus adapt the theory and methods of spin glass in statistical physics to study the computation of pure strategy NE and implementatiion of social efficency state in network games: completely characterize the structure of pure strategy NE space, propose a messge-passing algorithm to detect pure strategy NE; unveil the energy landscape of pure strategy NE, and design strategy evolution mechanism to drive the system to the optimum NE spontaneously; compute the social efficiency state, and propose the strategy evolution mechanism to approach the social efficiency state. The proposed research is of important social and academic significance which will provide new methods to deal with the computation of pure strategy NE in network games, and also enrich the findings in the implementatiion of social efficency state of network games.

网络博弈现已成为经济、社会、物理等诸多领域的热点问题。纳什均衡作为预测博弈结果的最常用对象之一，其如何受网络结构影响成为了关注焦点。参与人网络结构的引入使纯策略纳什均衡的计算成为了一个难题。此外，纯策略纳什均衡常常无法达到社会最大总收益。从统计物理角度看，网络博弈纯策略纳什均衡本质上是自旋玻璃模型的基态构型，为此，本项目应用统计物理自旋玻璃理论对四类网络博弈模型的纯策略纳什均衡计算和社会有效状态实现路径问题展开研究：刻画纯策略纳什均衡空间结构，建立基于消息传递的均衡求解算法；勾勒均衡的能量图景，设计驱使系统自发演化到最优均衡的策略演化规则；求解社会有效状态，提出逼近社会有效状态的策略演化规则。本项目的研究将为网络博弈纯策略纳什均衡的计算提供新的研究方法，丰富网络博弈社会有效状态实现路径的研究成果，具有重要理论意义和实践价值。

网络博弈现已成为经济、社会、物理等诸多领域的热点问题。纳什均衡作为预测博弈结果的最常用对象之一, 其如何受网络结构影响成为了关注焦点。参与人网络结构的引入使纯策略纳什均衡的计算成为了一个难题。此外,纯策略纳什均衡常常无法达到社会最大总收益。本项目应用统计物理自旋玻璃理论对网络博弈模型的纯策略纳什均衡计算和社会有效状态实现路径问题展开研究: 对公共品博弈问题提出了信息传递算法，去中心化的“局部一致”决策机制，并对贪心算法之一广义摘叶算法在一般网络上的效果进行了理论分析。本项目的研究将为网络博弈纯策略纳什均衡的计算提供新的研究方法,丰富网络博弈社会有效状态实现路径的研究成果,具有重要理论意义和实践价值。