A distributed algorithm for a set cover game.

In this paper, we propose a set cover game and show that any Nash equilibrium is a minimal set cover, and also a Pareto optimal solution. Then we present a distributed algorithm to realize the game. The algorithm is self-organizing in the sense that all players can make decisions by themselves simultaneously. It is local in the sense that each player makes his decision based only on information in his neighborhood. It is efficient in the sense that it converges to a minimal set cover in polynomial time when c max / c min is upper bounded by a polynomial of the input size, where c max and c min are the maximum cost and the minimum cost of sets, respectively. [ABSTRACT FROM AUTHOR]