Cost Sharing and Approximation

Abstract

Central to this thesis are problems in which a group of users can benefit from building and jointly using some kind of infrastructure, be it a set of supply depots, service stations, or a communication or transportation network. We study two important questions related to these kinds of scenarios: (1) how to build the shared facility that satisfies the needs of a given set of users in a cost-effective way, and (2) how to split the cost of the shared facility among the participating users in a fair and reasonable way.

In the first part of the thesis, we seek to design cost sharing functions with desirable game-theoretic properties. We are looking for cost sharing functions that are fair, and encourage cooperation among users. This is captured in the notion of cross-monotonicity: it says that a cost share of any user should never increase as more people join the system, and never decrease when players leave. Towards this end, we develop a new technique to generate such cross-monotonic cost shares using a primal-dual type process, and use it to design cross-monotonic cost shares for several NP-hard optimization problems.

In the second part we proceed in a slightly different direction, applying cost sharing to the design of approximation algorithms. We consider a class of two-stage stochastic problems with recourse. In these problems, we can buy building blocks (edges, facilities, vertices..) in two stages. In the first stage, the elements are relatively inexpensive, but we do not know the requirements of users we will have to serve (we only have a probabilistic forecast of their demands). In the second stage, the actual demands are revealed, and we must buy enough elements (now at a higher price) to satisfy all user demands.

We show that whenever the underlying deterministic problem admits a certain type of cost sharing, an extremely simple strategy gives us good approximation guarantees: in the first stage, take several samples from the forecasted distribution, and build a solution that covers all the sampled clients at the low price. When the real users materialize, augment the first stage solution to cover the actual demands. In this way we obtain constant approximation algorithms for stochastic versions of problems like Uncapacitated Facility Location, Steiner tree, Steiner Forest or Vertex Cover.