运筹学学报 >
2024 , Vol. 28 >Issue 2: 1 - 29
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2024.02.001
基于网络环境的若干组合优化博弈问题研究
收稿日期: 2024-01-09
网络出版日期: 2024-06-07
基金资助
国家自然科学基金(U20A2068)
版权
Survey on several combinatorial optimization games on networks
Received date: 2024-01-09
Online published: 2024-06-07
Copyright
随着互联网技术的飞速发展和社交网络的广泛普及, 大量现实问题可以模型化为基于网络环境的组合优化问题, 受到学术界和工业界的广泛关注。在这一过程中, 参与者通常受到个人利益的驱动, 采取策略性行动以实现自身效用的最大化。这种以“自利”为核心的行为模式, 不仅对其他参与者产生影响, 同时所有参与者的策略选择共同决定了社会福利整体目标的实现。在此背景下, 参与者之间的互动呈现出合作与竞争并存的复杂局面, 构成了组合优化博弈问题。本文旨在深入分析基于网络环境的三类具有挑战性的组合优化博弈问题: 网络上的公共品博弈、网络上的点覆盖博弈以及网络上的路由博弈。这三类问题不仅在组合优化和理论计算机科学领域占据着举足轻重的地位, 而且在管理科学与工程、经济学等多个交叉学科领域中也展现出广泛的应用前景。因此, 本文将系统性地介绍这三类组合优化博弈问题, 并对其最新的研究进展进行详细的梳理和深入的凝练, 以期为相关领域的研究者和实践者提供有价值的参考和启示。
程郁琨, 韩鑫, 陈修杨, 张昭 . 基于网络环境的若干组合优化博弈问题研究[J]. 运筹学学报, 2024 , 28(2) : 1 -29 . DOI: 10.15960/j.cnki.issn.1007-6093.2024.02.001
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.
| 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. |
| 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. |
| 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. |
| 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. |
| 8 | Nash J . Non-cooperative games[J]. Annals of Mathematics, 1951, 54 (2): 286- 295. |
| 9 | Koutsoupias E , Papadimitriou C . Worst-case equilibria[J]. Computer Science Review, 2009, 3 (2): 65- 69. |
| 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. |
| 13 | Conley T , Udry C . Learning about a new technology: Pineapple in Ghana[J]. American Economic Review, 2010, 100 (1): 35- 69. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
/
| 〈 |
|
〉 |
