Bayesian Game for Distributed Weighted <i>K</i>-Path Vertex Cover of Dynamic Networks

The weighted <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-path vertex cover (WVCP<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$_{k}$</tex-math></inline-formula>) problem is a main branch of covering problems on dynamic networks with many numerous instances in real-world complex systems. A pivotal challenge in distributed systems for network covering optimization is designing decentralized schemes for autonomous decision-making agents. This article focuses on the distributed optimization of the WVCP<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$_{k}$</tex-math></inline-formula> problem, where individual vertices, acting as rational agents, make decisions independently based on incomplete information. We formulate a Bayesian game model to capture the interactions among agents, who face the uncertainty to the statuses of their <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-path neighbors and rely on communications to enhance their individual beliefs on the actual cover state. Our analysis delves into the Bayesian Nash equilibrium and the ex-post Pareto optimal cover state (POCS) within this framework. In addition, a Bayesian game-based perturbation parallel algorithm (BGPPA) is developed and shown to converge to the ex-post POCS set, even when agents are restricted to using only estimated expected utility. A series of numerical simulations indicate that the BGPPA delivers superior performance with rapid convergence across various networks.