cross-monotonic cost-sharing methods for connected facility location games
We devise cost sharing methods for connected facility location games that are cross-monotonic, competitive and recover a constant fraction of the optimal cost.The novelty of this work is that we use randomized algorithms and that we share the expected cost among the participating users. We also provide a primal-dual cost sharing method for the connected facility location game with opening costs.
connected facility location cost sharing mechanism design