Self-organized Set Cover via Nash Equilibrium Learning and Selection

This paper focuses on the weighted set cover problem in networking systems and presents a fully distributed algorithm from the perspective of Nash equilibrium learning and selection. By viewing each set as an agent, we recast the problem as a networked ordinal potential game and classify the resulting Nash equilibrium into two categories. We show that each inferior Nash equilibrium (INE) could always be improved via local action exchange and better approximations could be achieved via self-organized selection among superior Nash equilibria (SNEs). By showing the existence of an improvement path that leads any action profile to an SNE, we prove that our algorithm converges in finite time to a conventional Nash equilibrium, where the joint action is a selected SNE. Comparison experiments with typical methods demonstrate the superiority to the state of the art.