Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14434
For citation please use:
Main Title: Online Cooperative Cost Sharing
Author(s): Brenner, Janina
Schäfer, Guido
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15661
http://dx.doi.org/10.14279/depositonce-14434
License: http://rightsstatements.org/vocab/InC/1.0/
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 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.
Subject(s): cooperative game theory
mechanism design
cost sharing mechanisms
cost sharing
games
Issue Date: 2009
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2009, 19
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Report-019-2009.pdf
Format: Adobe PDF | Size: 169.94 kB
DownloadShow Preview
Thumbnail

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.