基于网络环境的若干组合优化博弈问题研究  

Survey on several combinatorial optimization games on networks

作　　者：程郁琨 韩鑫[2] 陈修杨 张昭[3] Yukun CHENG;Xin HAN;Xiuyang CHEN;Zhao ZHANG(School of Business,Jiangnan University,Wuxi 214122,Jiangsu,China;School of Software Technology,Dalian University of Technology,Dalian 116024,Liaoning,China;School of Mathematical Sciences,Zhejiang Normal University,Jinhua 321004,Zhejiang,China)

机构地区：[1]江南大学商学院,江苏无锡214122 [2]大连理工大学软件学院,辽宁大连116024 [3]浙江师范大学数学科学学院,浙江金华321004

出　　处：《运筹学学报（中英文）》2024年第2期1-29,共29页Operations Research Transactions

基　　金：国家自然科学基金(No.U20A2068)。

摘　　要：随着互联网技术的飞速发展和社交网络的广泛普及,大量现实问题可以模型化为基于网络环境的组合优化问题,受到学术界和工业界的广泛关注。在这一过程中,参与者通常受到个人利益的驱动,采取策略性行动以实现自身效用的最大化。这种以“自利”为核心的行为模式,不仅对其他参与者产生影响,同时所有参与者的策略选择共同决定了社会福利整体目标的实现。在此背景下,参与者之间的互动呈现出合作与竞争并存的复杂局面,构成了组合优化博弈问题。本文旨在深入分析基于网络环境的三类具有挑战性的组合优化博弈问题:网络上的公共品博弈、网络上的点覆盖博弈以及网络上的路由博弈。这三类问题不仅在组合优化和理论计算机科学领域占据着举足轻重的地位,而且在管理科学与工程、经济学等多个交叉学科领域中也展现出广泛的应用前景。因此,本文将系统性地介绍这三类组合优化博弈问题,并对其最新的研究进展进行详细的梳理和深入的凝练,以期为相关领域的研究者和实践者提供有价值的参考和启示。With the advancement of Internet technology and social network,a multitude of real-world issues can be modeled as combinatorial optimization problems on networks,attracting widespread attention.In the optimization process,agents often engage in strategic behavior driven by personal interests to maximize their utilities.This"selfish"behavior can,on one hand,affect other participants,while on the other hand,the strategies of all agents directly determine the achievement of societal objectives.Therefore,cooperation and competition coexist among participants,giving rise to combinatorial optimization games.This paper aims to delve into three challenging combinatorial optimization games on networks:public goods games,vertex cover games,and routing games.These three categories of games not only hold significant positions in the fields of combinatorial optimization and theoretical computer science,but also have extensive applications across multiple interdisciplinary areas including management science and engineering,economics,and more.To this end,we will provide a systematic introduction to these three types of combinatorial optimization games and thoroughly review their recent research progress and breakthroughs.

关 键 词：网络 组合优化 公共品博弈 点覆盖博弈 路由博弈 

分 类 号：O221.2[理学—运筹学与控制论]