Non-cooperative facility location and covering games

AbstractWe consider a general class of non-cooperative games related to combinatorial covering and facility location problems. A game is based on an integer programming formulation of the corresponding optimization problem, and each of the k players wants to satisfy a subset of the constraints. For that purpose, resources available in integer units must be bought, and their cost can be shared arbitrarily between players. We consider the existence and cost of exact and approximate pure-strategy Nash equilibria. In general, the prices of anarchy and stability are in Θ(k) and deciding the existence of a pure Nash equilibrium is NP-hard. Under certain conditions, however, cheap Nash equilibria exist, in particular if the integrality gap of the underlying integer program is 1, or in the case of single constraint players. We also present algorithms that compute simultaneously near-stable and near-optimal approximate Nash equilibria in polynomial time