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

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

CLC Number:

O221.2

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.

Figures/Tables 4

References 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]	Shiyu HUANG, Liang CHEN, Caixia KOU. A polyhedral study of piecewise linear unsplittable flow arc set [J]. Operations Research Transactions, 2024, 28(4): 101-110.
[2]	Xiaomin HU, Shurong ZHANG, Jie CAO, Weihua YANG. Subnetwork reliability analysis of Cayley graphs generated by complete graphs [J]. Operations Research Transactions, 2024, 28(4): 135-142.
[3]	Qing ZHANG, Liang CHEN, Wenbao AI, Caixia KOU. A nonlinear bound strengthing method for the steady-state operation optimization model of gas pipeline networks [J]. Operations Research Transactions, 2024, 28(1): 101-111.
[4]	Yonghong LIU, Congying HAN, Tiande GUO. Fingerprint orientation field estimation algorithm based on deep learning [J]. Operations Research Transactions, 2023, 27(4): 1-19.
[5]	Shengxue HE. Transit vehicle scheduling model and 3M evolutionary algorithm based on super spatiotemporal network [J]. Operations Research Transactions, 2023, 27(3): 68-82.
[6]	Jianxiu HAO. Some remarks about dominating number of network [J]. Operations Research Transactions, 2023, 27(3): 185-190.
[7]	He WEI, Haofei LIU, Dandan XU, Xuehua HAN, Liang WANG, Xiaodong ZHANG. A systematic review of researches and applications of bi-level programming in the context of urban transport [J]. Operations Research Transactions, 2023, 27(2): 1-26.
[8]	Jianping LI, Lijian CAI, Junran LICHEN, Pengxiang PAN. The constrained multi-sources eccentricity augmentation problems [J]. Operations Research Transactions, 2022, 26(1): 60-68.
[9]	HU Jianqiang, DAI Weimin. Taylor expansion method for queueing systems [J]. Operations Research Transactions, 2021, 25(3): 147-159.
[10]	LIU Zhiping. Some advances in gene regulatory network inference [J]. Operations Research Transactions, 2021, 25(3): 173-182.
[11]	XUAN Hongwei, LI Zhendong, SHENG Zhoushan, LIU Lindong. Cost allocation for multiple pairs of shortest paths recovery game on disrupted networks [J]. Operations Research Transactions, 2021, 25(3): 183-199.
[12]	GUO Xiaoling, ZHUANG Yuanxin, LIU Yifan. Research on the quadratic programming model and solution algorithm of critical nodes in metro network [J]. Operations Research Transactions, 2020, 24(4): 51-62.
[13]	CHEN Lei, WANG Yingming. A structural heterogeneity DEA method with containment relationship for efficiency evaluation [J]. Operations Research Transactions, 2019, 23(4): 34-44.
[14]	LI Siwen, ZHAO Jiagui, SHAN Erfang. A characterization of the position value for hypernetwork situations [J]. Operations Research Transactions, 2019, 23(4): 165-174.
[15]	ZHANG Guochuan, CHEN Lin. The load balancing problem [J]. Operations Research Transactions, 2019, 23(3): 1-14.

Survey on several combinatorial optimization games on networks

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 4

References 76

Related Articles 15

Recommended Articles

Metrics

Comments