社会网络环境下机制设计理论及关键技术研究

Influence maximization is a widely studied research topic in social network analysis. Existing social network propagation models and influence maximization algorithms have achieved considerable progress, but most of them assume a fully observable environment, which limits its use in real world scenarios. In recent years, some researchers consider uncertainty and strategic interactions between agents by modeling influence maximization as a mechanism design problem, which has become an effective way for this problem. However, most of these works only apply mechanism design in a na?ve manner. In fact, the social network is a distributed, dynamic and complex environment that contains a massive number of agents with bounded individual rationality. This brings new challenges to the traditional theory framework of mechanism design. Based on the online social network applications, the project models influence maximization as a mechanism design problem by considering user's private information. A problem-driven approach is taken to perform an in-depth study of mechanism design problems in the social network environment. This can not only provide a new way to influence maximization problem in social networks, but also offer new application areas for mechanism design research. Moreover, the project will also improve the theoretical framework of mechanism design and promote its development in the field of computer science.

影响最大化问题是社会网络分析领域一个广为研究的重要问题。现有的社会网络传播模型及影响最大化算法的研究取得了可观的进展，但是大多存在一个信息完全可观察的假定，从而限制了其对现实环境的建模能力。近年来一些相关工作考虑上述不确定性及节点之间的策略交互，将影响最大化问题建模成一个机制设计问题，成为解决这一问题的有效途径。但是这些工作大多流于机制设计的简单应用，实际上社会网络的应用环境是包含"海量个体"、"有限个体理性"、"分布性"和"动态性"的复杂环境，这给机制设计的传统理论框架带来了新的挑战。本项目立足于在线社会网络的具体应用领域，通过考虑用户的私有信息，把影响最大化问题建模成一个机制设计问题，并且以问题驱动的形式深入地研究社会网络环境中的机制设计问题。这不仅可以为解决社会网络中的影响最大化问题提供一种新思路，还可以开拓机制设计的应用领域，完善其理论框架，促进其在计算机科学领域的发展。

影响最大化问题是社会网络分析领域一个重要的研究问题。现有的社会网络传播模型及影响最大化算法的研究存在信息完全可观察的假定，限制了其对现实环境的建模能力。社会网络的应用环境是包含"海量个体"、"有限个体理性"、"分布性"和"动态性"的复杂环境。本项目立足于在线社会网络的具体应用领域，通过考虑用户的私有信息，把影响最大化问题建模成一个机制设计问题，并且以问题驱动的形式深入地研究社会网络环境中的机制设计问题。这主要涉及到如下三个基本的问题：一是，如何有效建模面向社会网络影响最大化的信息传播问题；二是，如何将社会网络中的信息传播问题建模为机制设计问题；三是，针对难计算的机制设计问题，如何近似求解。主要取得了如下进展：.1) 提出了一系列新的信息传播模型，包括：成本约束条件下的信息传播，异构在线社交网络中信息传播问题，信息传播过程中实体情绪的变化，信息传播问题中的异常检测问题，多元信息融合的信息传播问题。同时考虑社会网络的社团结构对每一类信息传播问题的影响，并在多个社会网络实验平台上进行了验证。 .2) 将信息传播问题建模为开放环境下的机制设计问题，并对开放环境下的模型修正展开了研究；同时研究了社交网络中的路径拍卖问题，提出了一种基于核选择的路径拍卖机制，大大降低了核约束的数量，并且通过理论证明其具有很好的激励性质，且可在多项式时间内计算出分配结果和agent的支付结果，相比VCG大大减少了所需的总支付。.3) 提出了计算可行的常数因子的近似机制，基于算法机制设计的框架，在网络节点agent的代价概率分布已知的假设下，将基于逻辑的社会法则优化的问题框架，加权Steiner tree等问题进一步扩展到策略场景下，并证明这些机制都是激励相容的，满足个体理性和多项式可计算的。