License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2015.365
URN: urn:nbn:de:0030-drops-56358
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5635/
Avni, Guy ;
Kupferman, Orna ;
Tamir, Tami
Congestion Games with Multisets of Resources and Applications in Synthesis
Abstract
In classical congestion games, players' strategies are subsets of resources. We introduce and study multiset congestion games, where players' strategies are multisets of resources. Thus, in each strategy a player may need to use each resource a different number of times, and his cost for using the resource depends on the load that he and the other players generate on the resource.
Beyond the theoretical interest in examining the effect of a repeated use of resources, our study enables better understanding of non-cooperative systems and environments whose behavior is not covered by previously studied models. Indeed, congestion games with multiset-strategies arise, for example, in production planing
and network formation with tasks that are more involved than reachability. We study in detail the application of synthesis from component libraries: different users synthesize systems by gluing together components from a component library. A component may be used in several systems and may be used several times in a system. The performance of a component and hence the system's quality depends on the load on it.
Our results reveal how the richer setting of multisets congestion games affects the stability and equilibrium efficiency compared to standard congestion games. In particular, while we present very simple instances with no pure Nash equilibrium and prove tighter and simpler lower bounds for equilibrium inefficiency, we are also able to show that some of the positive results known for affine and weighted congestion games apply to the richer setting of multisets.
BibTeX - Entry
@InProceedings{avni_et_al:LIPIcs:2015:5635,
author = {Guy Avni and Orna Kupferman and Tami Tamir},
title = {{Congestion Games with Multisets of Resources and Applications in Synthesis}},
booktitle = {35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
pages = {365--379},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-97-2},
ISSN = {1868-8969},
year = {2015},
volume = {45},
editor = {Prahladh Harsha and G. Ramalingam},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5635},
URN = {urn:nbn:de:0030-drops-56358},
doi = {10.4230/LIPIcs.FSTTCS.2015.365},
annote = {Keywords: Congestion games, Multiset strategies, Equilibrium existence and computation, Equilibrium inefficiency}
}
|
Keywords: |
|
Congestion games, Multiset strategies, Equilibrium existence and computation, Equilibrium inefficiency |
|
Collection: |
|
35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015) |
|
Issue Date: |
|
2015 |
|
Date of publication: |
|
14.12.2015 |
