  In cost sharing games with delays, a set of agents jointly allocates a finite
subset of resources. Each resource has a fixed cost that has to be shared by
the players, and each agent has a nonshareable player-specific delay for each
resource. A prominent example is uncapacitated facility location (UFL), where
facilities need to be opened (at a shareable cost) and clients want to connect
to opened facilities. Each client pays a cost share and his non-shareable
physical connection cost. Given any profile of subsets allocated by the agents,
a separable cost sharing protocol determines cost shares that satisfy budget
balance on every resource and separability over the resources. Moreover, a
separable protocol guarantees existence of pure Nash equilibria in the induced
strategic game for the agents. In this paper, we study separable cost sharing
protocols in several general combinatorial domains. We provide black-box
reductions to reduce the design of a separable cost-sharing protocol to the
design of an approximation algorithm for the underlying cost minimization
problem. In this way, we obtain new separable cost-sharing protocols in games
based on arbitrary player-specific matroids, single-source connection games
without delays, and connection games on $n$-series-parallel graphs with delays.
All these reductions are efficiently computable - given an initial allocation
profile, we obtain a cheaper profile and separable cost shares turning the
profile into a pure Nash equilibrium. Hence, in these domains any approximation
algorithm can be used to obtain a separable cost sharing protocol with a price
of stability bounded by the approximation factor.
