Distributed Weighted Vertex Cover: An Ordinal Potential Game Theoretic Learning Approach

Aiming for better approximation to the distributed minimum weighted vertex cover problem, we propose an ordinal potential game theoretic algorithm (OPGTA) via self-organized Nash equilibrium (NE) learning and refinement. Through incorporating heuristic information into the local utility, we formulate the problem as an ordinal potential game for the first time, where each NE constitutes a non-redundant vertex cover. After further classifying the NE into the advantage equilibrium (AE) and the inferior equilibrium (IE), we show that better approximations could be achieved through AEs. By proving the existence of a finite-length improvement path from any joint action to an AE, we prove the ability of the OPGTA to avoid being trapped by inefficient IEs and thus its convergence to better-off AEs in a finite number of iterations with probability 1. Finally, comparison experiments against the latest distributed algorithms verify the superiority to the state of the art, in terms of global fitness and computation speed.