Optimal cost sharing for capacitated facility location games

• We consider cost sharing in capacitated facility location games.
• Optimal cost sharing protocols (w.r.t. price of anarchy and price of stability) are introduced.
• Computational hardness and inapproximability of optimal cost shares are shown.
• We give a tractable protocol with performance matching the inapproximability bound.

We consider cost sharing for a class of facility location games, where the strategy space of each player consists of the bases of a player-specific matroid defined on the set of resources. We assume that resources have nondecreasing load-dependent costs and player-specific delays. Our model includes the important special case of capacitated facility location problems, where players have to jointly pay for opened facilities. The goal is to design cost sharing protocols so as to minimize the resulting price of anarchy and price of stability. We investigate two classes of protocols: basic protocols guarantee the existence of at least one pure Nash equilibrium and separable protocols additionally require that the resulting cost shares only depend on the set of players on a resource. We find optimal basic and separable protocols that guarantee the price of stability/price of anarchy to grow logarithmically/linearly in the number of players. These results extend our previous results (cf. von Falkenhausen & Harks, 2013), where optimal basic and separable protocols were given for the case of symmetric matroid games without delays.We finally study the complexity of computing optimal cost shares. We derive several hardness results showing that optimal cost shares cannot be approximated in polynomial time within a logarithmic factor in the number of players, unless P=NPP=NP. For a restricted class of problems that include the above hard instances, we devise an approximation algorithm matching the logarithmic bound.