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

doi:10.15960/j.cnki.issn.1007-6093.2024.02.001

摘要/Abstract

摘要：

随着互联网技术的飞速发展和社交网络的广泛普及, 大量现实问题可以模型化为基于网络环境的组合优化问题, 受到学术界和工业界的广泛关注。在这一过程中, 参与者通常受到个人利益的驱动, 采取策略性行动以实现自身效用的最大化。这种以“自利”为核心的行为模式, 不仅对其他参与者产生影响, 同时所有参与者的策略选择共同决定了社会福利整体目标的实现。在此背景下, 参与者之间的互动呈现出合作与竞争并存的复杂局面, 构成了组合优化博弈问题。本文旨在深入分析基于网络环境的三类具有挑战性的组合优化博弈问题: 网络上的公共品博弈、网络上的点覆盖博弈以及网络上的路由博弈。这三类问题不仅在组合优化和理论计算机科学领域占据着举足轻重的地位, 而且在管理科学与工程、经济学等多个交叉学科领域中也展现出广泛的应用前景。因此, 本文将系统性地介绍这三类组合优化博弈问题, 并对其最新的研究进展进行详细的梳理和深入的凝练, 以期为相关领域的研究者和实践者提供有价值的参考和启示。

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

Abstract:

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.

Key words: network, combinatorial optimization, public goods game, vertex cover game, routing game

中图分类号:

O221.2

程郁琨, 韩鑫, 陈修杨, 张昭. 基于网络环境的若干组合优化博弈问题研究[J]. 运筹学学报（中英文）, 2024, 28(2): 1-29.

Yukun CHENG, Xin HAN, Xiuyang CHEN, Zhao ZHANG. Survey on several combinatorial optimization games on networks[J]. Operations Research Transactions, 2024, 28(2): 1-29.

图/表 4

表1

图1

图2

图3

参考文献 76

1	Karp R M . Reducibility among Combinatorial Problems[M]. Berlin: Springer Heidelberg, 2010.
2	Ford L R , Fulkerson D R . Maximal flow through a network[J]. Canadian Journal of Mathematics, 1956, 8, 399- 404. doi: 10.4153/CJM-1956-045-5
3	Nisan N , Roughgarden T , Tardos E , et al. Algorithmic Game Theory[M]. Cambridge: Cambridge University Press, 2007.
4	Cramton P , Shoham Y , Steinberg R . Combinatorial Auctions[M]. Cambridge: MIT Press, 2006.
5	De Vries S , Vohra R V . Combinatorial auctions: A survey[J]. INFORMS Journal on Computing, 2003, 15 (3): 284- 309. doi: 10.1287/ijoc.15.3.284.16077
6	Edelman B , Ostrovsky M , Schwarz M . Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords[J]. The American Economic Review, 2007, 97 (1): 242- 259. doi: 10.1257/aer.97.1.242
7	Edelman B , Schwarz M . Optimal auction design and equilibrium selection in sponsored search auctions[J]. The American Economic Review, 2010, 100 (2): 597- 602. doi: 10.1257/aer.100.2.597
8	Nash J . Non-cooperative games[J]. Annals of Mathematics, 1951, 54 (2): 286- 295. doi: 10.2307/1969529
9	Koutsoupias E , Papadimitriou C . Worst-case equilibria[J]. Computer Science Review, 2009, 3 (2): 65- 69. doi: 10.1016/j.cosrev.2009.04.003
10	Roughgarden T . Selfish Routing and the Price of Anarchy[M]. Cambridge: MIT press, 2005.
11	Nisan N, Ronen A. Algorithmic mechanism design[C]//Proceedings of the 31st Annual ACM Symposium on Theory of Computing, 1999: 129-140.
12	Burt R . Social contagion and innovation: Cohesion versus structural equivalence[J]. American Journal of Sociology, 1987, 92 (6): 1287- 1335. doi: 10.1086/228667
13	Conley T , Udry C . Learning about a new technology: Pineapple in Ghana[J]. American Economic Review, 2010, 100 (1): 35- 69. doi: 10.1257/aer.100.1.35
14	Cowan R . Network models of innovation and knowledge diffusion[J]. Clusters, Networks and Innovation, 2005, 29- 53.
15	Valente T . Network models and methods for studying the diffusion of innovations[J]. Models and Methods in Social Network Analysis, 2005, 28, 98- 116.
16	Samuelson A . The pure theory of public expenditure[J]. Review of Economics and Statistics, 1954, 36 (4): 387- 389. doi: 10.2307/1925895
17	Olson M . The Logic of Collective Action: Public Goods and the Theory of Groups[M]. Cambridge: Harvard University Press, 1971.
18	Bramoullé Y , Kranton R . Public goods in networks[J]. Journal of Economic Theory, 2007, 135 (1): 478- 494. doi: 10.1016/j.jet.2006.06.006
19	Papadimitriou C, Peng B. Public goods games in directed networks[C]//Proceedings of the 22nd ACM Conference on Economics and Computation, 2021: 745-762.
20	Gilboa M, Nisan N. Complexity of public goods games on graphs[C]//Proceedings of the 15th International Symposium on Algorithmic Game Theory, 2022: 151-168
21	Elkind E, Goldberg L, Goldberg P. Nash equilibria in graphical games on trees revisited[C]//Proceedings of the 7th ACM Conference on Electronic Commerce, 2006: 100-109.
22	Daskalakis C , Goldberg P , Papadimitriou C . The complexity of computing a Nash equilibrium[J]. SIAM Journal on Computing, 2009, 39 (1): 195- 259. doi: 10.1137/070699652
23	Galeotti A , Goyal S , Jackson M , et al. Network games[J]. The Review of Economic Studies, 2010, 77 (1): 218- 244.
24	Pandit P , Kulkarni A . Refinement of the equilibrium of public goods games over networks: Efficiency and effort of specialized equilibria[J]. Journal of Mathematical Economics, 2018, 79, 125- 139. doi: 10.1016/j.jmateco.2018.04.002
25	Morgan R, Truman J. Criminal victimization, 2017[R]. Bureau of Justice Statistics, 2018: 1-30.
26	Yu S, Zhou K, Brantingham P, et al. Computing equilibria in binary networked public goods games[C]//Proceedings of the 34th AAAI Conference on Artificial Intelligence, 2020: 2310-2317.
27	Yang Y, Wang J. A refined study of the complexity of binary networked public goods games[EB/OL]. (2020-12-05)[2024-01-02]. arXiv: 2012.02916.
28	Maiti A , Dey P . On parameterized complexity of binary networked public goods game[J]. Algorithmica, 2023, 1- 27.
29	Dallasta L , Pin P , Ramezanpour A . Optimal equilibria of the best shot game[J]. Journal of Public Economic Theory, 2011, 13 (6): 885- 901.
30	Klimm M, Stahlberg M J. Complexity of equilibria in binary public goods games on undirected graphs[EB/OL]. (2023-05-19)[2024-01-02]. arXiv: 2301.11849.
31	Kempe D, Yu S, Vorobeychik Y. Inducing equilibria in networked public goods games through network structure modification[EB/OL]. (2021-09-02)[2024-01-02]. arXiv: 2002.10627.
32	Fehr E , Schmidt K M . The economics of fairness, reciprocity and altruism-experimental evidence and new theories[J]. Handbook of the Economics of Giving, Altruism and Reciprocity, 2006, 1, 615- 691.
33	Cardenas J C , Carpenter J . Behavioural development economics: Lessons from field labs in the developing world[J]. The Journal of Development Studies, 2008, 44 (3): 311- 338.
34	陈叶烽, 叶航, 汪丁丁. 超越经济人的社会偏好理论: 一个基于实验经济学的综述[J]. 南开经济研究, 2012, 1, 63- 100.
35	Meier D, Oswald Y A, Schmid S, et al. On the windfall of friendship: Inoculation strategies on social networks[C]//Proceedings of the 9th ACM Conference on Electronic Commerce, 2008: 294-301.
36	Yu S, Kempe D, Vorobeychik Y. Altruism design in networked public goods games[EB/OL]. (2021-05-02)[2024-01-02]. arXiv: 2105.00505.
37	Karp Richard M. Reducibility among combinatorial problems[C]//Proceedings of a Symposium on the Complexity of Computer Computations, 1972: 85-103.
38	Wu L, Du H, Wu W, et al. Approximations for minimum connected sensor cover[C]//Proceedings of IEEE INFOCOM, 2013: 1187-1194.
39	Christoph A , Monaldo M . Single machine precedence constrained scheduling is a vertex cover problem[J]. Algorithmica, 2009, 53, 488- 503.
40	Petra S , Gerhard J W . Polynomial time approximation algorithms for machine scheduling: Ten open problems[J]. Journal of Scheduling, 1999, 2 (5): 203- 213.
41	Bar-Yehuda R , Even S . A linear-time approximation algorithm for the weighted vertex cover problem[J]. Journal of Algorithms, 1981, 2 (2): 198- 203.
42	Khot S , Regev O . Vertex cover might be hard to approximate to within 2-"[J]. Journal of Computer and System Sciences, 2008, 74 (3): 335- 349.
43	Bar-Yehuda R , Even S . A local-ratio theorem for approximating the weighted vertex cover problem[J]. North-Holland Mathematics Studies, 1985, 109, 27- 45.
44	Karci A , Arslan A . Bidirectional evolutionary heuristic for the minimum vertex-cover problem[J]. Computers and Electrical Engineering, 2003, 29 (1): 111- 120.
45	Kettani O , Ramdani F , Tadili B . A heuristic approach for the vertex cover problem[J]. International Journal of Computer Applications, 2013, 82, 9- 11.
46	Quan C , Guo P . A local search method based on edge age strategy for minimum vertex cover problem in massive graphs[J]. Expert Systems with Applications, 2021, 182, 115185.
47	Yakut S , Öztemiz F , Karci A . A new robust approach to solve minimum vertex cover problem: Malatya vertex-cover algorithm[J]. The Journal of Supercomputing, 2023, 79 (17): 197746- 19769.
48	Wang Y , LYU Z P , Punnen A P . A fast and robust heuristic algorithm for the minimum weight vertex cover problem[J]. IEEE Access, 2021, 9, 31932- 31945.
49	Wu W , Zhang Z , Lee W , et al. Optimal Coverage in Wireless Sensor Networks[M]. Cham: Springer, 2020.
50	Hochbaum Dorit S . Approximation algorithms for the set covering and vertex cover problems[J]. SIAM Journal on Computing, 1982, 11 (3): 555- 556.
51	Hochbaum Dorit S . Efficient bounds for the stable set, vertex cover and set packing problems[J]. Discrete Applied Mathematics, 1983, 6 (3): 243- 254.
52	Halperin E . Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs[J]. SIAM Journal on Computing, 2002, 31 (5): 1608- 1623.
53	Karakostas G . A better approximation ratio for the vertex cover problem[J]. ACM Transactions on Algorithms, 2009, 5 (4): 1- 8.
54	Alon N , Awerbuch B , Azar Y , et al. The online set cover problem[J]. SIAM Journal on Computing, 2009, 39 (2): 361- 370.
55	Azar Y, Buchbinder N, Chan Hubert T-H, et al. Online algorithms for covering and packing problems with convex objectives[C]//Proceedings of the 57th Annual Symposium on Foundations of Computer Science, 2016: 148-157.
56	Im S , Sviridenko M , Zwaan van der R . Preemptive and non-preemptive generalized min sum set cover[J]. Mathematical Programming, 2014, 145 (1): 377- 401.
57	Varadarajan K. Weighted geometric set cover via quasi-uniform sampling[C]//Proceedings of the 42nd Annual ACM Symposium on Theory of Computing, 2010: 641-648.
58	Yang Y , Li X . Towards a snowdrift game optimization to vertex cover of networks[J]. IEEE Transactions on Cybernetics, 2013, 43 (3): 948- 956.
59	Chen J , Luo K , Tang C , et al. Optimizing polynomial-time solutions to a network weighted vertex cover game[J]. IEEE/CAA Journal of Automatica Sinica, 2023, 10 (2): 512- 523.
60	Sun C , Sun W , Wang X , et al. Potential game theoretic learning for the minimal weighted vertex cover in distributed networking systems[J]. IEEE Transactions on Cybernetics, 2019, 49 (5): 1968- 1978.
61	Zhu C , Huang X , Zhang Z . A distributed algorithm for a set cover game[J]. Discrete Mathematics, Algorithms and Applications, 2022, 14 (3): 2150127.
62	Piliouras G , Valla T , Végh , et al. LP-based covering games with low price of anarchy[J]. Theory of Computing Systems, 2015, 57, 238- 260.
63	Monderer D , Shapley Lloyd S . Potential games[J]. Games and Economic Behavior, 1996, 14 (1): 124- 143.
64	Chen J , Li X . Toward the minimum vertex cover of complex networks using distributed potential games[J]. Science China Information Sciences, 2023, 66, 112205.
65	Sun C , Qiu H , Sun W , et al. Better approximation for distributed weighted vertex cover via game-theoretic learning[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2022, 52 (8): 5308- 5319.
66	Sun C, Wang X, Qiu H, et al. Distributed optimization for weighted vertex cover via heuristic game theoretic learning[C]//Proceedings of the 59th IEEE Conference on Decision and Control, 2020: 325-330.
67	Wradrop G. Some theoretical aspects of road traffic research[C]//Proceedings of the Institute of Civil Engineers, 1952: 325-378.
68	Altman E , Basar T , Srikant R . Nash equilibria for combined flow control and routing in networks: Asymptotic behavior for a large number of users[J]. IEEE Transactions on Automatic Control, 2002, 47 (6): 917- 930.
69	Orda A , Rom R , Shimkin N . Competitive routing in multiuser communication networks[J]. IEEE/ACM Transactions on Networking, 1993, 1 (5): 510- 521.
70	Rosenthal W . A class of games possessing pure-strategy Nash equilibria[J]. International Journal of Game Theory, 1973, 2, 65- 67.
71	Beckmann J , McGuire B , Winsten C . Studies in the Economics of Transportation[M]. New Haven: Yale University Press, 1956.
72	Roughgarden T . The price of anarchy is independent of the network topology[J]. Journal of Computer and System Sciences, 2003, 67 (2): 341- 364.
73	Awerbuch B, Azar Y, Epstein A. The price of routing unsplittable flow[C]//Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005: 57-66.
74	Christodoulou G, Koutsoupias E. The price of anarchy in finite congestion games[C]//Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005: 67-73.
75	Hao B, Michini C. Inefficiency of pure Nash equilibria in series-parallel network congestion games[C]//Proceedings of the 18th Conference on Web and Internet Economics, 2022: 3-20.
76	Meyers C. Network flow problems and congestion games: Complexity and approximation results[D]. Cambridge: Massachusetts Institute of Technology, 2006.

符号	符号解释
$ \Gamma $	点覆盖博弈
$ n $	顶点个数
$ i $	顶点
$ w_i $	在顶点$ i $处安置传感器的成本
$ V $	顶点集合$ V=1, 2, \cdots, n $
$ E $	边集
$ S_i $	$ S_i=0, 1 $为参与者$ i $的策略集合, 其中策略1表示参与者
$ \Sigma $	$ \Sigma=S_1\times \cdots \times S_n $是策略空间
$ C $	$ C=(c_1, c_2, \cdots, c_n)\in\Sigma $是策略组合, 其中$ c_i\in S_i $
\	在不引起歧义下, $ C=i: c_i=1 $也是点子集
$ C_{-i} $	$ C_{-i}=(c_1, \cdots, c_{i-1}, c_{i+1}, \cdots, c_n) $是不包括$ c_i $的一个策略组合
$ D $	$ D=(d_1, d_2, \cdots, d_n) $是需求策略组合
$ u_i(C, D) $	给定所有参与者策略组合$ C $与需求策略组合时, $ i $的效用函数
$ N_i $	$ N_i=j\in V \colon (i, j)\in E $表示$ i $的邻集

[1]	黄诗语, 陈亮, 寇彩霞. 分段线性的不可分流弧集多面体研究[J]. 运筹学学报（中英文）, 2024, 28(4): 101-110.
[2]	王滔. 基于消费者行为定价下制造商的网络渠道构建策略选择研究[J]. 运筹学学报（中英文）, 2024, 28(2): 30-46.
[3]	刘永鸿, 韩丛英, 郭田德. 基于深度学习的指纹方向场提取算法[J]. 运筹学学报, 2023, 27(4): 1-19.
[4]	何胜学. 基于超级时空网络的公交车辆调度模型及3M进化算法[J]. 运筹学学报, 2023, 27(3): 68-82.
[5]	郝建修. 关于网络的控制数的几点注记[J]. 运筹学学报, 2023, 27(3): 185-190.
[6]	魏贺, 刘昊飞, 许丹丹, 韩雪华, 王良, 张晓东. 双层规划在城市交通领域研究与应用的系统综述[J]. 运筹学学报, 2023, 27(2): 1-26.
[7]	赵伟良, 齐林明. 基于电网络技巧计数一类平面自相似图的生成树数目[J]. 运筹学学报, 2022, 26(4): 119-126.
[8]	李建平, 蔡力健, 李陈筠然, 潘鹏翔. 限制性多源点偏心距增广问题[J]. 运筹学学报, 2022, 26(1): 60-68.
[9]	胡建强, 戴伟民. 排队系统中的泰勒展开方法[J]. 运筹学学报, 2021, 25(3): 147-159.
[10]	刘治平. 基因调控网络推断研究进展[J]. 运筹学学报, 2021, 25(3): 173-182.
[11]	宣洪伟, 李振东, 盛舟山, 刘林冬. 灾后运输网络中的最短路修复合作博弈[J]. 运筹学学报, 2021, 25(3): 183-199.
[12]	郭晓玲, 庄远鑫, 刘轶凡. 地铁网络关键节点二次规划模型与求解算法研究[J]. 运筹学学报, 2020, 24(4): 51-62.
[13]	陈磊, 王应明. 具有包容关系的结构异质DEA效率评价方法[J]. 运筹学学报, 2019, 23(4): 34-44.
[14]	李思文, 赵加贵, 单而芳. 超网络博弈的位置值的公理化刻画[J]. 运筹学学报, 2019, 23(4): 165-174.
[15]	张国川, 陈林. 负载均衡问题[J]. 运筹学学报, 2019, 23(3): 1-14.