Probability Weighting Effect in Vertex Cover of Networks Via Prospect-Theoretic Learning

Ke Xu, Ke Wu, and Rongpei Zhou


Abstract : Game-theoretic learning methods for the vertex cover problem have been investigated in this paper. In the traditional game theory, the establishment of the game model is based on the complete objectivity of the players, and the existing game models describe the vertex cover problem mainly along this path. In contrast, this paper considers the impact of players’ subjectivity on decision-making results. First, we present a covering game model, where the utility function of the player is established under the prospect theory. Then, by presenting a rounding function, the states of all vertices under Nash equilibrium satisfies vertex cover state of a general network. After then, we present a fictitious play distributed algorithm, which can guarantee that the states of all vertices converge a Nash equilibrium. Finally, the simulation results are presented to assess the impact of players’ subjectivity on the overall cover results of networks.​

Index terms : Nash equilibrium, prospect theory, simulation results, subjectivity of players, vertex cover.