社会网络环境下非次模函数优化问题与合作博弈算法研究

Internet has changed the public’s lifestyle, which encourages the formation of a huge social network. Currently, study on influence maximization in social networks has been a hot topic in the field of international research. This project researches on algorithms for optimization problems with non-submodular objective functions and related cooperative games in social networks. Try to make some progresses in the following three aspects. (1) Research on the computation complexities and approximate algorithms of optimization problems with non-submodular objective functions and constraints for a class of independent systems; (2) Study the computation complexities and approximate algorithms for influence maximization problems with non-submodular objective functions in social network; (3) Explore the optimal coalitions in related cooperative games, analyze the computation complexities and design reasonable algorithms for finding the corresponding game solution. This project tries to make some breakthroughs in the design and analysis of algorithms for optimization with non-submodular objective functions, and apply related results to the influence maximization problems and related interest distribution problems in social networks. Break through the bottleneck that the research in this field are mainly limited to studying problems with submodular objective functions. This project belongs to the cross field of combinatorial optimization, game theory and algorithm theory. The expected results of it will provide some new ideas, research methods and theoretical results for combinatorial optimization and cooperative game theories, and have broad prospects in the future.

互联网改变了人们的生活方式，形成了庞大的社会网络，社会网络影响最大化问题的研究是当前国际上研究的热点。本项目将围绕社会网络环境下非次模函数优化问题和相关合作博弈的算法开展研究，目标是在以下三方面取得进展：一是目标函数为非次模函数、约束为某类独立系统的优化问题的计算复杂性和近似算法；二是目标函数为非次模函数的社会网络影响最大化问题的计算复杂性和近似算法；三是社会网络环境下的合作博弈的最优联盟形成及相关博弈解的计算复杂性和求解算法。本项目争取在非次模函数的优化问题的算法设计与分析上有所突破，并将相关结果应用于社会网络影响最大化以及相应的利益分配问题，突破当前该领域的研究大多仅局限于目标函数为次模函数的瓶颈。本项目属于组合最优化、博弈论和算法理论的交叉领域。项目的预期成果将为组合优化、合作博弈提供一些新的思想、研究方法和理论结果，并具有广泛的前景。

互联网影响了人类生活的方方面面，网络结构上的优化与博弈问题持续成为国际上研究的热点。本项目始于网络环境下次模与非次模函数优化问题的近似算法研究，将相关理论结果应用于社会网络中影响或利润最大化问题；进而研究相关的组合合作博弈的凸性刻画及博弈解的性质刻画和求解算法，探讨基于组合优化模型的非合作博弈的均衡性及机制设计方法。经过团队的共同努力，项目获得了一些新思想、新研究方法并取得了若干创新的理论结果。重要研究成果如下：. 1.针对拟阵约束、次模率为的非次模函数最大化问题，利用连续贪婪算法和创新的CR-Schemes设计出新的算法；针对整数格上无约束弱次模函数最大化问题“未解”的近似度问题，设计出达到最优近似度的算法；对拟阵约束下DR-次模整数格函数最大化问题也设计出多个更为有效的算法。. 2.针对多种不同网络环境下影响或利润最大化问题，通过研究目标函数的次模性质，引入鞅等统计工具、RIS方法等，设计出高效的随机近似算法，降低了算法时间复杂度、提高了算法的有效性。. 3.针对建立在网络独立集、覆盖与匹配等优化问题上合作博弈，研究博弈模型的凸性，提出了合作博弈存在群体单调分配方案的充要条件，设计了有效的判定算法。. 4.针对装箱问题和设施选址问题，开展机制设计研究。针对自私装箱问题设计了两个机制，其无政府代价值PoA均优于已有研究结果或达到最优；针对自私设施选址模型，引入“嫉妒比”作为公平准则并设置为社会目标，设计出多个具有激励相容性且达到较好PoA的机制。. 本项目发表高水平研究论文24篇（SCI期刊论文22篇）；举办国际学术会议1次、国内专题研讨班2次，邀请专家访问、报告20余人次；指导硕士生15名、博士生6名；项目组成员在本项目研究过程中获得了4项新的国家自然科学基金资助。总之，本项目对于组合优化和算法博弈领域的研究起到了积极推动作用，项目成果具有很好的理论价值与应用前景。