IEEE Transactions on Systems Man and Cybernetics Systems · 2021 · 19 citations · 37 references
ComputingComputer ScienceAlgorithmsGame TheoryOptimizationApproximation AlgorithmsDistributed AlgorithmsDistributed ComputingDistributed CoordinationNash EquilibriumNetwork GamesDistributed Approximation AlgorithmsDistributed Graph LearningDistributed OptimizationFinite TimeGame-theoretic LearningMulti-agent LearningRefinementVertex Cover Approximation
Toward better approximation for the minimum-weighted vertex cover (MWVC) problem in multiagent systems, we present a distributed algorithm from the perspective of learning in games. For self-organized coordination and optimization, we see each vertex as a potential game player who makes decisions using local information of its own and the immediate neighbors. The resulting Nash equilibrium is classified into two categories, i.e., the inferior Nash equilibrium (INE) and the dominant Nash equilibrium (DNE). We show that the optimal solution must be a DNE. To achieve better approximation ratios, local rules of perturbation and weighted memory are designed, with the former destroying the stability of an INE and the latter facilitating the refinement of a DNE. By showing the existence of an improvement path from any INE to a DNE, we prove that when the memory length is larger than 1, our algorithm converges in finite time to DNEs, which could not be improved by exchanging the action of a selected node with all its unselected neighbors. Moreover, additional freedom for solution efficiency refinement is provided by increasing the memory length. Finally, intensive comparison experiments demonstrate the superiority of the presented methodology to the state of the art, both in solution efficiency and computation speed.
37
Emergence of Scaling in Random Networks
Albert-Ĺaszló Barabási, Réka Albert · Science · 1999 · 36.4K citations · Full text
Dov Monderer, Lloyd S. Shapley · Games and Economic Behavior · 1996 · 3.5K citations
Game theory: analysis of conflict
Roger B. Myerson · Choice Reviews Online · 1992 · 3.4K citations
A Greedy Heuristic for the Set-Covering Problem
Vašek Chvátal · Mathematics of Operations Research · 1979 · 2.6K citations