Mechanism Design for Distributed Weighted Set Cover via Learning in Ordinal Potential Games
针对分布式加权集合覆盖问题，提出一种基于序数势博弈学习的纳什均衡选择算法，通过分类均衡并设计随机规则，保证有限时间收敛到高质量解，实验验证优于现有方法。
Aiming for efficient coordination mechanisms for the distributed weighted set cover problem, we study from ordinal potential game theoretic learning and propose a Nash equilibrium selection algorithm (NESA). An ordinal potential game model is established, where the local utility function is designed by incorporating a greedy heuristic. To distinguish Nash equilibria of different global fitness, we further classify them into the inferior Nash equilibrium (INE) and the superior Nash equilibrium (SNE), and show that the optimal solution must be an SNE. High-quality SNE solutions are obtained by assigning each player a local stochastic rule based on its category and a finite memory. By demonstrating the existence of a finite improvement path from each INE to an SNE, we prove finite-time convergence of the NESA. Numerical experiments are carried out and comparisons against representative methods are presented, which demonstrate the effectiveness as well as the superiority of our methodology to the state-of-the-art.