算法博弈论视角下的策略替代型网络博弈

Network game, as a fundamental class of theoretical models of behavior and decision making on social networks, is a fairly state of art research topic that is typically interdisciplinary, resting on the intersection of game theory, combinatorial optimization, theoretical computer science, and theoretical economics. It has shown its promising application potential in economics and management science. This project will investigate a basic class of network games,namely network games with strategic substitutes, from the perspective of algorithmic game theory(this paradigm has been awarded the 2012 Godel prize). This class of games can model the congestion effect, negative network externality etc., and thus has its realworld importance. Yet, compared with network games with strategic complements, the analysis for network games with strategic substitutes is much more challenging (e.g.they may not have any pure Nash equilibrium, and the equilibrium set, even if nonempty, is in general not a lattice), and extant literature of it is rather insufficient. We shall focus on several special but famous and important models, namely network anti-coordination games, network public good games, and network pricing with negative externalities. In addition, we shall also study the equilibrium structure of general network games with strategic substitutes on bipartite graphs.

网络博弈，作为社会网络上的行为与决策研究中非常基本的一个理论模型，是博弈论、组合优化、理论计算机、理论经济学等多个学科领域交叉融合的一个前沿研究方向，已经在经济管理中初步显示出其广泛的应用前景。本项目将对网络博弈里的一类基本模型，策略替代型网络博弈，从算法博弈论的视角进行分析研究（这是一个获得了2012年哥德尔奖的较前沿的研究范式）。策略替代型网络博弈可以很好地刻画阻塞效应、网络负外部性等，具有重要的现实意义。然而跟策略互补型网络博弈相比，策略替代型网络博弈一般具有更大的理论分析难度（比如纯策略纳什均衡不一定存在，且均衡集一般不具有格结构），学术界对其研究还远不够充分。我们将重点研究几类特殊但是著名而重要的策略替代型网络博弈，即网络反协同博弈、网络公共物品博弈和带负外部性的网络定价问题。同时，我们还将对一般的策略替代型博弈研究其在二部图上的均衡结构。

超模博弈和策略互补博弈是博弈论中一个非常有用的一类博弈，在经济学和管理学很多领域都找到了广泛应用。本项目从网络博弈论和算法博弈论的视角研究了策略替代型网络博弈以及若干同时包含互补与替代的博弈模型。本项目研究发现，在一定的技术条件下，每个策略互补博弈都可以嵌入一个更大的策略替代博弈并保持均衡集合一定意义上不变；发现线性最优反应的情况下，策略替代博弈均衡求解问题为PPAD困难，而策略互补博弈均衡可以多项式时间求解；项目还研究了同时具有互补和替代的合作博弈，解决了诺贝尔经济学奖得主Shapley教授1955年提出的一个猜想；研究了同时具有策略互补和策略替代的离散型和连续型网络博弈。这些论文发表于Operations Research、Games and Economic Behavior和Journal of Mathematical Economics等重要期刊以及ACM Economics and Computation顶级会议。项目负责人因为这些成果获得了系统科学与系统工程青年科技奖、中国信息经济学理论贡献奖、中国决策科学青年科技奖和关肇直青年研究奖等。项目负责人还在《科学世界》和《知识分子》等媒体发表多篇科普文章。