Cross-monotonic cost-sharing methods for connected facility location games

ABSTRACT

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.

REFERENCES

• 1: Nikhil R. Devanur , Milena Mihail , Vijay V. Vazirani, Strategyproof cost-sharing mechanisms for set cover and facility location games, Proceedings of the 4th ACM conference on Electronic commerce, p.108-114, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779942]
• 2: Anupam Gupta , Amit Kumar , Tim Roughgarden, Simpler and better approximation algorithms for network design, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780597]
• 3: A. Gupta, A. Srinivasan and E. Tardos. Personal communication, 2003.
• 4: Kamal Jain , Vijay Vazirani, Applications of approximation algorithms to cooperative games, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.364-372, July 2001, Hersonissos, Greece [doi>10.1145/380752.380825]
• 5: H. Moulin and S. Shenker. Strategyproof sharing of submodular costs: budget balance versus efficiency. http://www.aciri.org/shenker/cost.ps, 1997.
• 6: Martin Pál , Éva Tardo, Group Strategyproof Mechanisms via Primal-Dual Algorithms, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.584, October 11-14, 2003

INDEX TERMS

General Terms:
Algorithms, Design, Theory

Keywords:
connected facility location, cost sharing, mechanism design