Abstract
The problem of sharing the cost of a common infrastructure among a set of strategic and cooperating players has been the subject of intensive research in recent years. However, most of these studies consider cooperative cost sharing games in an offline setting, i.e., the mechanism knows all players and their respective input data in advance. In this paper, we consider cooperative cost sharing games in an online setting: Upon the arrival of a new player, the mechanism has to take instantaneous and irreversible decisions without any knowledge about players that arrive in the future. We propose an online model for general demand cost sharing games and give a complete characterization of both weakly group-strategyproof and group-strategyproof online cost sharing mechanisms for this model. Moreover, we present a simple method to derive incremental online cost sharing mechanisms from online algorithms such that the competitive ratio is preserved. Based on our general results, we develop online cost sharing mechanisms for several binary demand and general demand cost sharing games.
This work was supported by the DFG Research Center Matheon “Mathematics for key technologies”.
This is a preview of subscription content, log in via an institution.
Buying options
Tax calculation will be finalised at checkout
Purchases are for personal use only
Learn about institutional subscriptionsPreview
Unable to display preview. Download preview PDF.
References
Bleischwitz, Y., Schoppmann, F.: Group-strategyproof cost sharing for metric fault tolerant facility location. In: Monien, B., Schroeder, U.-P. (eds.) SAGT 2008. LNCS, vol. 4997, pp. 350–361. Springer, Heidelberg (2008)
Borodin, A., El-Yaniv, R.: Online computation and competitive analysis. Cambridge University Press, New York (1998)
Brenner, J., Schäfer, G.: Singleton acyclic mechanisms and their applications to scheduling problems. In: Monien, B., Schroeder, U.-P. (eds.) SAGT 2008. LNCS, vol. 4997, pp. 315–326. Springer, Heidelberg (2008)
Devanur, N., Mihail, M., Vazirani, V.: Strategyproof cost-sharing mechanisms for set cover and facility location games. Decision Support. Syst. 39(1), 11–22 (2005)
Du, J., Leung, J.Y.T., Young, G.H.: Minimizing mean flow time with release time constraint. Theoretical Computer Sci. 75(3), 347–355 (1990)
Gupta, A., Hajiaghayi, M., Räcke, H.: Oblivious network design. In: Proc. of the 17th ACM-SIAM Sympos. on Discrete Algorithms, pp. 970–979 (2006)
Harks, T., Heinz, S., Pfetsch, M.: Competitive online multicommodity routing. Theory of Computing Systems (2008)
Imase, M., Waxman, B.: Dynamic Steiner tree problems. SIAM J. Disc. Math. 4(3), 369–384 (1991)
Immorlica, N., Mahdian, M., Mirrokni, V.S.: Limitations of cross-monotonic cost-sharing schemes. ACM Trans. Algorithms 4(2), 1–25 (2008)
Juarez, R.: Group strategyproof cost sharing (2008) (unpublished)
Mehta, A., Roughgarden, T., Sundararajan, M.: Beyond Moulin mechanisms. In: Proc. of the ACM Conference on Electronic Commerce (2007)
Moulin, H.: Incremental cost sharing: Characterization by coalition strategy-proofness. Soc. Choice Welfare 16, 279–320 (1999)
Schrage, L.: A proof of the optimality of the shortest remaining processing time discipline. Operations Res. 16, 687–690 (1968)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brenner, J., Schäfer, G. (2010). Online Cooperative Cost Sharing . In: Calamoneri, T., Diaz, J. (eds) Algorithms and Complexity. CIAC 2010. Lecture Notes in Computer Science, vol 6078. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13073-1_23
Download citation
DOI: https://doi.org/10.1007/978-3-642-13073-1_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-13072-4
Online ISBN: 978-3-642-13073-1
eBook Packages: Computer ScienceComputer Science (R0)