网络时尚博弈：均衡求解、分析与机制设计

网络博弈，作为社会网络上的行为与决策研究中非常基本的一个理论模型，是博弈论、组合优化、物理学、生物学等多个学科领域大交叉大融合的一个国际热点研究方向，并已经初步在经济管理中显示出其广泛的应用前景。网络时尚博弈由美国科学院院士Jackson最早提出,是网络博弈中一个十分简洁却内涵足够丰富解释力足够强的模型,目前尚未得到学界的足够关注。该模型与著名的硬币匹配博弈在网络上的推广密切相关,既具有相当的现实基础和又有重要的理论意义,并已经在股票市场和金融传染研究中发挥了作用。对该模型已有的少量研究，大多是用演化博弈和统计物理学的方法，借助于计算机仿真模拟进行分析,而且并未注意到所研究的模型与时尚或硬币匹配博弈的关联。对于这一几乎全新的模型，本项目将主要从算法博弈论的角度对网络时尚博弈的均衡存在性判别、均衡求解、均衡逼近、均衡效率分析、机制设计等进行严格的理论分析,并辅之以计算机仿真研究。

项目启动以来，共发表和录用论文14篇，SCI检索论文13篇(其中8篇同时被SSCI检索)。按照基金委的要求，所有文章都进行了基金号标注。这些论文多数发表在Social Choice and Welfare, Mathematical Social Sciences, Theoretical Computer Science, Journal of Combinatorial Optimization, PLoS ONE，Asia-Pacific Journal of Operational Research以及Physica A等算法博弈论和网络博弈论相关领域的国际知名期刊。若干研究成果得到了审稿人的高度评价，还有一些已经产生了一定的学术影响（比如得到了网络博弈论学界领军学者、哈佛大学Martin Nowak教授等的正面引用，被EC和SAGT等算法博弈论领域的权威会议引用），得到了国内外同行的初步肯定。比照项目计划书的预期，课题组出色地完成了研究任务。..下面是主要研究成果概述。（1）我们研究了网络硬币匹配博弈。该模型可以很好地刻画时尚这一重要而有趣的现象。对于均衡求解，我们得到很多算法和复杂性方面的结论。（2）研究了社会网络上的时尚品促销问题，证明了两个相关优化问题的NP困难性，给出了好的近似算法，并设计出了regret-proof的算法。（3）解决了Hart和Mas-Colell提出的两个讨价还价方面的问题。（4）从博弈论的视角研究了互补与替代型合作，得到很多不同于经典模型的有趣结论。