
Discrete Mathematics and Optimization Seminar

Nov. 3, 2008
Covering Games: Approximation through NonCooperation
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 kcover 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 playerspecific
structural constraints. For covering an element, the players receive a payoff defined by
a utility sharing function which is nonincreasing 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 polynomialtime
approximation algorithms with approximation ratio arbitrary close to (1  1/e ). A hardness
result for max kcover (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 PLScomplete.
If time permits, I will also talk about other approaches to approximate the covering problem.



