Type of Publication:  Contribution to a conference 
Author:  Hoefer, Martin; Souza, Alexander 
Year of publication:  2008 
Published in:  Algorithmic Game Theory / Monien, Burkhard; Schroeder, UlfPeter (ed.).  Berlin, Heidelberg : Springer Berlin Heidelberg, 2008.  (Lecture Notes in Computer Science).  pp. 2232.  ISSN 03029743.  eISSN 16113349.  ISBN 9783540793083 
DOI (citable link):  https://dx.doi.org/10.1007/9783540793090_4 
Summary: 
In this paper we consider the influence of link restrictions on the price of anarchy for several social cost functions in the following model of selfish routing. Each of n players in a network game seeks to send a message with a certain length by choosing one of m parallel links. Each player is restricted to transmit over a certain subset of links and desires to minimize his own transmissiontime (latency). We study Nash equilibria of the game, in which no player can decrease his latency by unilaterally changing his link. Our analysis of this game captures two important aspects of network traffic: the dependency of the overall network performance on the total traffic t and fluctuations in the length of the respective messagelengths. For the latter we use a probabilistic model in which message lengths are random variables. We evaluate the (expected) price of anarchy of the game for two social cost functions. For total latency cost, we show the tight result that the price of anarchy is essentially Θ(n √ m/t). Hence, even for congested networks, when the traffic is linear in the number of players, Nash equilibria approximate the social optimum only by a factor of Θ ( √ m). This efficiency loss is caused by link restrictions and remains stable even under message fluctuations, which contrasts the unrestricted case where Nash equilibria achieve a constant factor approximation. For maximum latency the price of anarchy is at most 1+m2/t. In this case Nash equilibria can be (almost) optimal solutions for congested networks depending on the values for m and t. In addition, our analyses yield averagecase analyses of a polynomial time algorithm for computing Nash equilibria in this model.

Subject (DDC):  004 Computer Science 
Files  Size  Format  View 

There are no files associated with this item. 
HOEFER, Martin, Alexander SOUZA, 2008. The Influence of Link Restriction on (Random) Selfish Routing. In: MONIEN, Burkhard, ed., UlfPeter SCHROEDER, ed.. Algorithmic Game Theory. Berlin, Heidelberg:Springer Berlin Heidelberg, pp. 2232. ISSN 03029743. eISSN 16113349. ISBN 9783540793083. Available under: doi: 10.1007/9783540793090_4
@inproceedings{Hoefer2008Influ3001, title={The Influence of Link Restriction on (Random) Selfish Routing}, year={2008}, doi={10.1007/9783540793090_4}, isbn={9783540793083}, issn={03029743}, address={Berlin, Heidelberg}, publisher={Springer Berlin Heidelberg}, series={Lecture Notes in Computer Science}, booktitle={Algorithmic Game Theory}, pages={2232}, editor={Monien, Burkhard and Schroeder, UlfPeter}, author={Hoefer, Martin and Souza, Alexander} }
<rdf:RDF xmlns:dcterms="http://purl.org/dc/terms/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:rdf="http://www.w3.org/1999/02/22rdfsyntaxns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dspace="http://digitalrepositories.org/ontologies/dspace/0.1.0#" xmlns:foaf="http://xmlns.com/foaf/0.1/" xmlns:void="http://rdfs.org/ns/void#" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.unikonstanz.de/rdf/resource/123456789/3001"> <dc:creator>Souza, Alexander</dc:creator> <bibo:uri rdf:resource="http://kops.unikonstanz.de/handle/123456789/3001"/> <dcterms:abstract xml:lang="eng">In this paper we consider the influence of link restrictions on the price of anarchy for several social cost functions in the following model of selfish routing. Each of n players in a network game seeks to send a message with a certain length by choosing one of m parallel links. Each player is restricted to transmit over a certain subset of links and desires to minimize his own transmissiontime (latency). We study Nash equilibria of the game, in which no player can decrease his latency by unilaterally changing his link. Our analysis of this game captures two important aspects of network traffic: the dependency of the overall network performance on the total traffic t and fluctuations in the length of the respective messagelengths. For the latter we use a probabilistic model in which message lengths are random variables. We evaluate the (expected) price of anarchy of the game for two social cost functions. For total latency cost, we show the tight result that the price of anarchy is essentially Θ(n √ m/t). Hence, even for congested networks, when the traffic is linear in the number of players, Nash equilibria approximate the social optimum only by a factor of Θ ( √ m). This efficiency loss is caused by link restrictions and remains stable even under message fluctuations, which contrasts the unrestricted case where Nash equilibria achieve a constant factor approximation. For maximum latency the price of anarchy is at most 1+m2/t. In this case Nash equilibria can be (almost) optimal solutions for congested networks depending on the values for m and t. In addition, our analyses yield averagecase analyses of a polynomial time algorithm for computing Nash equilibria in this model.</dcterms:abstract> <dcterms:isPartOf rdf:resource="https://kops.unikonstanz.de/rdf/resource/123456789/36"/> <dc:language>eng</dc:language> <dcterms:issued>2008</dcterms:issued> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">20110323T10:15:43Z</dc:date> <dcterms:rights rdf:resource="https://kops.unikonstanz.de/page/termsofuse"/> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">20110323T10:15:43Z</dcterms:available> <dcterms:bibliographicCitation>Publ. in: Algorithmic Game Theory: First International Symposium, SAGT 2008, Paderborn, Germany, April 30  May 2, 2008, Proceedings / Burkhard Monien ... (eds.). Berlin, Heidelberg: Springer, 2008, pp. 2232.  (= LNCS ; 4997)</dcterms:bibliographicCitation> <dc:contributor>Hoefer, Martin</dc:contributor> <dcterms:title>The Influence of Link Restriction on (Random) Selfish Routing</dcterms:title> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:contributor>Souza, Alexander</dc:contributor> <dspace:isPartOfCollection rdf:resource="https://kops.unikonstanz.de/rdf/resource/123456789/36"/> <dc:rights>termsofuse</dc:rights> <dc:creator>Hoefer, Martin</dc:creator> </rdf:Description> </rdf:RDF>