DMO Seminar

Covering Games: Approximation through Non-Cooperation

Martin Gairing

ICSI Berkeley

In this talk, we consider a general covering problem from a game theoretic prospective. In the covering problem, we are given a universal set of weighted elements E and the task is to choose k subsets of the elements such that the total weight of their union is as large as possible. Each of the k subsets has to satisfy some structural constraints. In contrast to the well studied max k-cover problem, we allow these constraints to be different for each of the k subsets. Given such a covering problem, we define covering games with k rational players. Each player has a strategy set, which is a set of subsets of the elements E. Each subset satisfies the player-specific structural constraints. For covering an element, the players receive a payoff defined by a utility sharing function which is non-increasing in the number of players covering the element. This function defines the fraction that each covering player receives from the weight of the element.

As our main result, we construct a utility sharing function, such that every Nash equilibrium covers at least a (1 - 1/e )-fraction of the weight of the optimum solution. We also show that this is best possible, even for very restricted settings. For an important subclass of the covering problem, we provide a family of utility sharing functions such that the above fraction decreases only slightly but any sequence of unilateral improving steps is polynomially bounded. So, a pure Nash equilibrium can be computed in polynomial time. This gives rise to a family of polynomial-time approximation algorithms with approximation ratio arbitrary close to (1 - 1/e ). A hardness result for max k-cover (see [Feige, JACM 1998]) implies that this approximation ratio is essentially the best possible. For the general case, we show that computing a pure Nash equilibrium is PLS-complete. If time permits, I will also talk about other approaches to approximate the covering problem.