Prospect Theoretic Analysis on Weighted Vertex Cover of Networks
作者单位：College of Physics and Electronic EngineeringZhejiang Normal University Adaptive Networks and Control LabDepartment of Electronic EngineeringFudan University
会议名称：《第40届中国控制会议》
会议日期：2021年
学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 081104[工学-模式识别与智能系统] 08[工学] 070105[理学-运筹学与控制论] 0835[工学-软件工程] 0701[理学-数学] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）]
关 键 词：Weighted vertex cover(WVC) Game theory Prospect theory Nash equilibrium Fictitious play
摘 要：Weighted vertex cover（WVC） is a classical combinatorial optimization problem, which has rich practice ***, the existing WVC studies based on game theory has introduced the traditional expected utility theory（EUT）, where each vertex is treated as a rational player. However, the uncertainty caused by the weight factor is neglected. So how does this uncertainty affect players’ behaviour? In this paper, the complete theoretical analysis is shown. Specifically, we model the WVC problem as an non-cooperative game on weighted networks and respectively establish EUT-based and prospect theory-based utility functions. Then, we prove the existence of mixed NE on this weighted game. Further, by designing a state function,we find that the vertices’ state under mixed NE satisfies weighted vertex cover state of the network. Finally, a fictitious play algorithm is proposed to get a NE of the game. Our findings will pave the way for the future numerical simulation, which can demonstrate the impact of the prospect theory on weighted vertex cover.