Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2011

AUTHORS

George Christodoulou , Kurt Mehlhorn , Evangelia Pyrga

ABSTRACT

We reconsider the well-studied Selfish Routing game with affine latency functions. The Price of Anarchy for this class of games takes maximum value 4/3; this maximum is attained already for a simple network of two parallel links, known as Pigou’s network. We improve upon the value 4/3 by means of Coordination Mechanisms.We increase the latency functions of the edges in the network, i.e., if ℓe(x) is the latency function of an edge e, we replace it by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\hat{\ell}_e(x)$\end{document} with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\ell_e(x) \le \hat{\ell}_e(x)$\end{document} for all x. Then an adversary fixes a demand rate as input. The engineered Price of Anarchy of the mechanism is defined as the worst-case ratio of the Nash social cost in the modified network over the optimal social cost in the original network. Formally, if \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\hat{C}_N(r)$\end{document} denotes the cost of the worst Nash flow in the modified network for rate r and Copt(r) denotes the cost of the optimal flow in the original network for the same rate then \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ \mathit{ePoA} = \max_{r \ge 0} \frac{\hat{C}_N(r)}{C_{\mathit{opt}}(r)}.$$\end{document}We first exhibit a simple coordination mechanism that achieves for any network of parallel links an engineered Price of Anarchy strictly less than 4/3. For the case of two parallel links our basic mechanism gives 5/4 = 1.25. Then, for the case of two parallel links, we describe an optimal mechanism; its engineered Price of Anarchy lies between 1.191 and 1.192. More... »

PAGES

119-130

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-23719-5_11

DOI

http://dx.doi.org/10.1007/978-3-642-23719-5_11

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1035402197


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/10", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Technology", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1005", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Communications Technologies", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Liverpool, United Kingdom", 
          "id": "http://www.grid.ac/institutes/grid.10025.36", 
          "name": [
            "University of Liverpool, United Kingdom"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Christodoulou", 
        "givenName": "George", 
        "id": "sg:person.015372025055.44", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015372025055.44"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mehlhorn", 
        "givenName": "Kurt", 
        "id": "sg:person.011757371347.43", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Technische Universit\u00e4t M\u00fcnchen, Germany", 
          "id": "http://www.grid.ac/institutes/grid.6936.a", 
          "name": [
            "Technische Universit\u00e4t M\u00fcnchen, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Pyrga", 
        "givenName": "Evangelia", 
        "id": "sg:person.016052023445.47", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016052023445.47"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2011", 
    "datePublishedReg": "2011-01-01", 
    "description": "We reconsider the well-studied Selfish Routing game with affine latency functions. The Price of Anarchy for this class of games takes maximum value 4/3; this maximum is attained already for a simple network of two parallel links, known as Pigou\u2019s network. We improve upon the value 4/3 by means of Coordination Mechanisms.We increase the latency functions of the edges in the network, i.e., if \u2113e(x) is the latency function of an edge e, we replace it by \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\hat{\\ell}_e(x)$\\end{document} with \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\ell_e(x) \\le \\hat{\\ell}_e(x)$\\end{document} for all x. Then an adversary fixes a demand rate as input. The engineered Price of Anarchy of the mechanism is defined as the worst-case ratio of the Nash social cost in the modified network over the optimal social cost in the original network. Formally, if \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\hat{C}_N(r)$\\end{document} denotes the cost of the worst Nash flow in the modified network for rate r and Copt(r) denotes the cost of the optimal flow in the original network for the same rate then \n\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$ \\mathit{ePoA} = \\max_{r \\ge 0} \\frac{\\hat{C}_N(r)}{C_{\\mathit{opt}}(r)}.$$\\end{document}We first exhibit a simple coordination mechanism that achieves for any network of parallel links an engineered Price of Anarchy strictly less than 4/3. For the case of two parallel links our basic mechanism gives 5/4 = 1.25. Then, for the case of two parallel links, we describe an optimal mechanism; its engineered Price of Anarchy lies between 1.191 and 1.192.", 
    "editor": [
      {
        "familyName": "Demetrescu", 
        "givenName": "Camil", 
        "type": "Person"
      }, 
      {
        "familyName": "Halld\u00f3rsson", 
        "givenName": "Magn\u00fas M.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-23719-5_11", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-23718-8", 
        "978-3-642-23719-5"
      ], 
      "name": "Algorithms \u2013 ESA 2011", 
      "type": "Book"
    }, 
    "keywords": [
      "parallel links", 
      "modified network", 
      "simple coordination mechanism", 
      "network", 
      "original network", 
      "affine latency functions", 
      "routing", 
      "simple network", 
      "link", 
      "price of anarchy", 
      "selfish routing", 
      "routing games", 
      "cost", 
      "Nash flow", 
      "social costs", 
      "latency functions", 
      "coordination mechanism", 
      "adversary", 
      "selfish routing game", 
      "optimal social cost", 
      "class of games", 
      "exhibit", 
      "prices", 
      "demand rate", 
      "optimal mechanism", 
      "mechanism", 
      "edge", 
      "anarchy", 
      "rate", 
      "ratio", 
      "basic mechanisms", 
      "worst-case ratio", 
      "rate R", 
      "first exhibit", 
      "game", 
      "function", 
      "maximum", 
      "means", 
      "optimal flow", 
      "same rate", 
      "flow", 
      "class", 
      "input", 
      "lies", 
      "cases", 
      "value 4/3", 
      "edge e"
    ], 
    "name": "Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms", 
    "pagination": "119-130", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1035402197"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-23719-5_11"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-23719-5_11", 
      "https://app.dimensions.ai/details/publication/pub.1035402197"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-10-01T06:56", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/chapter/chapter_30.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-23719-5_11"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-23719-5_11'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-23719-5_11'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-23719-5_11'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-23719-5_11'


 

This table displays all metadata directly associated to this object as RDF triples.

131 TRIPLES      22 PREDICATES      72 URIs      65 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-23719-5_11 schema:about anzsrc-for:10
2 anzsrc-for:1005
3 schema:author Nca10581a81da412ea4e6e8f45f5d903c
4 schema:datePublished 2011
5 schema:datePublishedReg 2011-01-01
6 schema:description We reconsider the well-studied Selfish Routing game with affine latency functions. The Price of Anarchy for this class of games takes maximum value 4/3; this maximum is attained already for a simple network of two parallel links, known as Pigou’s network. We improve upon the value 4/3 by means of Coordination Mechanisms.We increase the latency functions of the edges in the network, i.e., if ℓe(x) is the latency function of an edge e, we replace it by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\hat{\ell}_e(x)$\end{document} with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\ell_e(x) \le \hat{\ell}_e(x)$\end{document} for all x. Then an adversary fixes a demand rate as input. The engineered Price of Anarchy of the mechanism is defined as the worst-case ratio of the Nash social cost in the modified network over the optimal social cost in the original network. Formally, if \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\hat{C}_N(r)$\end{document} denotes the cost of the worst Nash flow in the modified network for rate r and Copt(r) denotes the cost of the optimal flow in the original network for the same rate then \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ \mathit{ePoA} = \max_{r \ge 0} \frac{\hat{C}_N(r)}{C_{\mathit{opt}}(r)}.$$\end{document}We first exhibit a simple coordination mechanism that achieves for any network of parallel links an engineered Price of Anarchy strictly less than 4/3. For the case of two parallel links our basic mechanism gives 5/4 = 1.25. Then, for the case of two parallel links, we describe an optimal mechanism; its engineered Price of Anarchy lies between 1.191 and 1.192.
7 schema:editor N2f21672c3d9a4f4595879ae8befc71af
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf Nebc362ffedbf4abfba6aa946053e1bde
11 schema:keywords Nash flow
12 adversary
13 affine latency functions
14 anarchy
15 basic mechanisms
16 cases
17 class
18 class of games
19 coordination mechanism
20 cost
21 demand rate
22 edge
23 edge e
24 exhibit
25 first exhibit
26 flow
27 function
28 game
29 input
30 latency functions
31 lies
32 link
33 maximum
34 means
35 mechanism
36 modified network
37 network
38 optimal flow
39 optimal mechanism
40 optimal social cost
41 original network
42 parallel links
43 price of anarchy
44 prices
45 rate
46 rate R
47 ratio
48 routing
49 routing games
50 same rate
51 selfish routing
52 selfish routing game
53 simple coordination mechanism
54 simple network
55 social costs
56 value 4/3
57 worst-case ratio
58 schema:name Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms
59 schema:pagination 119-130
60 schema:productId N0776f51a810c401c82c6cfa70089f449
61 N306107b397f442ca9d9068ad8559dde1
62 schema:publisher N791590eb791845f1aa9e545f98cf1f10
63 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035402197
64 https://doi.org/10.1007/978-3-642-23719-5_11
65 schema:sdDatePublished 2022-10-01T06:56
66 schema:sdLicense https://scigraph.springernature.com/explorer/license/
67 schema:sdPublisher Ne5cd6daa221e44a8885a05db2cc84da5
68 schema:url https://doi.org/10.1007/978-3-642-23719-5_11
69 sgo:license sg:explorer/license/
70 sgo:sdDataset chapters
71 rdf:type schema:Chapter
72 N0776f51a810c401c82c6cfa70089f449 schema:name dimensions_id
73 schema:value pub.1035402197
74 rdf:type schema:PropertyValue
75 N10430ac50cd343238fabeaa309f9967a rdf:first N7b676b41a7534f319ff835fbd1473982
76 rdf:rest rdf:nil
77 N2f21672c3d9a4f4595879ae8befc71af rdf:first N7d50dcc8b82648b5b63355b2973190fc
78 rdf:rest N10430ac50cd343238fabeaa309f9967a
79 N306107b397f442ca9d9068ad8559dde1 schema:name doi
80 schema:value 10.1007/978-3-642-23719-5_11
81 rdf:type schema:PropertyValue
82 N791590eb791845f1aa9e545f98cf1f10 schema:name Springer Nature
83 rdf:type schema:Organisation
84 N7a31316dc28443158c26abc606ae0e82 rdf:first sg:person.016052023445.47
85 rdf:rest rdf:nil
86 N7b676b41a7534f319ff835fbd1473982 schema:familyName Halldórsson
87 schema:givenName Magnús M.
88 rdf:type schema:Person
89 N7d50dcc8b82648b5b63355b2973190fc schema:familyName Demetrescu
90 schema:givenName Camil
91 rdf:type schema:Person
92 Nbd1829ddbdfc442293ef6bb20c4736cb rdf:first sg:person.011757371347.43
93 rdf:rest N7a31316dc28443158c26abc606ae0e82
94 Nca10581a81da412ea4e6e8f45f5d903c rdf:first sg:person.015372025055.44
95 rdf:rest Nbd1829ddbdfc442293ef6bb20c4736cb
96 Ne5cd6daa221e44a8885a05db2cc84da5 schema:name Springer Nature - SN SciGraph project
97 rdf:type schema:Organization
98 Nebc362ffedbf4abfba6aa946053e1bde schema:isbn 978-3-642-23718-8
99 978-3-642-23719-5
100 schema:name Algorithms – ESA 2011
101 rdf:type schema:Book
102 anzsrc-for:10 schema:inDefinedTermSet anzsrc-for:
103 schema:name Technology
104 rdf:type schema:DefinedTerm
105 anzsrc-for:1005 schema:inDefinedTermSet anzsrc-for:
106 schema:name Communications Technologies
107 rdf:type schema:DefinedTerm
108 sg:person.011757371347.43 schema:affiliation grid-institutes:grid.419528.3
109 schema:familyName Mehlhorn
110 schema:givenName Kurt
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43
112 rdf:type schema:Person
113 sg:person.015372025055.44 schema:affiliation grid-institutes:grid.10025.36
114 schema:familyName Christodoulou
115 schema:givenName George
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015372025055.44
117 rdf:type schema:Person
118 sg:person.016052023445.47 schema:affiliation grid-institutes:grid.6936.a
119 schema:familyName Pyrga
120 schema:givenName Evangelia
121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016052023445.47
122 rdf:type schema:Person
123 grid-institutes:grid.10025.36 schema:alternateName University of Liverpool, United Kingdom
124 schema:name University of Liverpool, United Kingdom
125 rdf:type schema:Organization
126 grid-institutes:grid.419528.3 schema:alternateName Max-Planck-Institut für Informatik, Saarbrücken, Germany
127 schema:name Max-Planck-Institut für Informatik, Saarbrücken, Germany
128 rdf:type schema:Organization
129 grid-institutes:grid.6936.a schema:alternateName Technische Universität München, Germany
130 schema:name Technische Universität München, Germany
131 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...