License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.09261.27
URN: urn:nbn:de:0030-drops-21702
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/2170/
|
Go to the corresponding Portal |
Schulz, Andreas S. ;
Uhan, Nelson A.
Sharing Supermodular Costs
Abstract
We apply ideas from cooperative game theory to study situations in which a set of agents face supermodular costs. These situations appear in a variety of scheduling contexts, as well as in some settings related to facility location and network design. Intuitively, cooperation amongst rational agents who face supermodular costs is unlikely. However, in circumstances where the failure to cooperate may lead to negative externalities, one might be interested in methods of encouraging cooperation. The least core value of a cooperative game is the minimum penalty we need to charge a coalition for acting independently that encourages cooperation by ensuring the existence of an efficient and stable cost allocation. The set of all such cost allocations is called the least core. In this work, we study the computational complexity and approximability of computing the least core value of supermodular cost cooperative games. We show that computing the least core value of supermodular cost cooperative games is strongly NP-hard, and build a framework to approximate the least core value of these games using oracles that approximately determine maximally violated constraints. This framework yields a $(3+epsilon)$-approximation algorithm for computing the least core value of supermodular cost cooperative games. As a by-product, we show how to compute accompanying approximate least core cost allocations for these games. We also apply our approximation framework to obtain better results for two particular classes of supermodular cost cooperative games that arise from scheduling and matroid optimization.
BibTeX - Entry
@InProceedings{schulz_et_al:DagSemProc.09261.27,
author = {Schulz, Andreas S. and Uhan, Nelson A.},
title = {{Sharing Supermodular Costs}},
booktitle = {Models and Algorithms for Optimization in Logistics},
pages = {1--5},
series = {Dagstuhl Seminar Proceedings (DagSemProc)},
ISSN = {1862-4405},
year = {2009},
volume = {9261},
editor = {Cynthia Barnhart and Uwe Clausen and Ulrich Lauther and Rolf H. M\"{o}hring},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2009/2170},
URN = {urn:nbn:de:0030-drops-21702},
doi = {10.4230/DagSemProc.09261.27},
annote = {Keywords: Cooperative games, approximation algorithms, algorithmic game theory}
}
|
Keywords: |
|
Cooperative games, approximation algorithms, algorithmic game theory |
|
Collection: |
|
09261 - Models and Algorithms for Optimization in Logistics |
|
Issue Date: |
|
2009 |
|
Date of publication: |
|
02.10.2009 |
