TU Berlin

FG Kombinatorische Optimierung und Graphenalgorithmen2009

COGA 5-Wheel


zur Navigation

Preprints 2009

Online Cooperative Cost Sharing
Zitatschlüssel Report-019-2009
Autor Janina Brenner and Guido Schäfer
Jahr 2009
Nummer 019
Monat jul
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung 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 perfect 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.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe