title: Towards a snowdrift game optimization to vertex cover of networks.
abstract: To solve the vertex cover problem in an agent-based and distributed networking systems utilizing local information, we treat each vertex as an intelligent rational agent rather than an inanimate one and provide a spatial-snowdrift-game-based optimization framework to vertex cover of networks. We analyze the inherent relation between the snowdrift game and the vertex cover: Strict Nash equilibriums of the spatial snowdrift game are the intermediate states between vertex-covered and minimal-vertex-covered states. Such equilibriums are obtained by employing the memory-based best response update rule. We also find that a better approximate solution in terms of the minimal vertex cover will be achieved by increasing the individuals' memory length, because such a process optimizes the individuals' strategies and helps them convert from bad equilibriums into better ones. Our findings pave a new way to solve the vertex cover problem from the perspective of agent-based self-organized optimization.
authors.affiliation: Adaptive Networks and Control Laboratory, Department of Electronic Engineering, Fudan University, Shanghai 200433, China. 09110720020@fudan.edu.cn
authors.forename: Yang
authors.initials: Y
authors.lastname: Yang
authors.forename: Xiang
authors.initials: X
authors.lastname: Li
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D003198:Computer Simulation; D003661:Decision Support Techniques; D005716:Game Theory; D008962:Models, Theoretical; D010363:Pattern Recognition, Automated / Q000379:methods*