On Stackelberg Strategies in Affine Congestion Games View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2018-12-13

AUTHORS

Vittorio Bilò, Cosimo Vinci

ABSTRACT

We investigate the efficiency of some Stackelberg strategies in congestion games with affine latency functions. A Stackelberg strategy is an algorithm that chooses a subset of players and assigns them a prescribed strategy with the purpose of mitigating the detrimental effect that the selfish behavior of the remaining uncoordinated players may cause to the overall performance of the system. The efficiency of a Stackelberg strategy is measured in terms of the price of anarchy of the pure Nash equilibria they induce. Three Stackelberg strategies, namely Largest Latency First, Cover and Scale, were already considered in the literature and non-tight upper and lower bounds on their price of anarchy were given. We reconsider these strategies and provide the exact bound on the price of anarchy of both Largest Latency First and Cover and a better upper bound on the price of anarchy of Scale. More... »

PAGES

1-22

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00224-018-9902-1

DOI

http://dx.doi.org/10.1007/s00224-018-9902-1

DIMENSIONS

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


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/1402", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Economics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/14", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Economics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Salento", 
          "id": "https://www.grid.ac/institutes/grid.9906.6", 
          "name": [
            "Department of Mathematics and Physics \u201cEnnio De Giorgi\u201d, University of Salento, Provinciale Lecce-Arnesano, P.O. Box 193, 73100, Lecce, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bil\u00f2", 
        "givenName": "Vittorio", 
        "id": "sg:person.012652036261.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012652036261.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Gran Sasso Science Institute", 
          "id": "https://www.grid.ac/institutes/grid.466750.6", 
          "name": [
            "Gran Sasso Science Institute, L\u2019Aquila, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vinci", 
        "givenName": "Cosimo", 
        "id": "sg:person.012770274011.86", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012770274011.86"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/1868237.1868251", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012378343"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2008.06.045", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013590738"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-010-9427-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016706126", 
          "https://doi.org/10.1007/s00453-010-9427-8"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2344422.2344426", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017791470"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-006-1211-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022756805", 
          "https://doi.org/10.1007/s00453-006-1211-4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2209249.2209274", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1029940041"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2629666", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031469011"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2940716.2940750", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032682251"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-007-9018-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033706914", 
          "https://doi.org/10.1007/s00453-007-9018-5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-007-9018-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033706914", 
          "https://doi.org/10.1007/s00453-007-9018-5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.cosrev.2009.04.003", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035244584"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2009.01.005", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038819075"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.jcss.2008.07.001", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042525379"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00224-008-9152-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042669741", 
          "https://doi.org/10.1007/s00224-008-9152-8"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00224-008-9152-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042669741", 
          "https://doi.org/10.1007/s00224-008-9152-8"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01737559", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044775936", 
          "https://doi.org/10.1007/bf01737559"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1060590.1060600", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050456256"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/070680096", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062850841"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/090748986", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062855983"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0097539701397059", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062879332"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00224-017-9826-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093123382", 
          "https://doi.org/10.1007/s00224-017-9826-1"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2018-12-13", 
    "datePublishedReg": "2018-12-13", 
    "description": "We investigate the efficiency of some Stackelberg strategies in congestion games with affine latency functions. A Stackelberg strategy is an algorithm that chooses a subset of players and assigns them a prescribed strategy with the purpose of mitigating the detrimental effect that the selfish behavior of the remaining uncoordinated players may cause to the overall performance of the system. The efficiency of a Stackelberg strategy is measured in terms of the price of anarchy of the pure Nash equilibria they induce. Three Stackelberg strategies, namely Largest Latency First, Cover and Scale, were already considered in the literature and non-tight upper and lower bounds on their price of anarchy were given. We reconsider these strategies and provide the exact bound on the price of anarchy of both Largest Latency First and Cover and a better upper bound on the price of anarchy of Scale.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00224-018-9902-1", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1052098", 
        "issn": [
          "1432-4350", 
          "1433-0490"
        ], 
        "name": "Theory of Computing Systems", 
        "type": "Periodical"
      }
    ], 
    "name": "On Stackelberg Strategies in Affine Congestion Games", 
    "pagination": "1-22", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "fd8a4cf440796ff3498c5fe7235f286f7dfb92d141f3bd09ad367fb712997c74"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00224-018-9902-1"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1110555728"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00224-018-9902-1", 
      "https://app.dimensions.ai/details/publication/pub.1110555728"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T08:23", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000293_0000000293/records_12014_00000000.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs00224-018-9902-1"
  }
]
 

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/s00224-018-9902-1'

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/s00224-018-9902-1'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00224-018-9902-1'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00224-018-9902-1'


 

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

128 TRIPLES      21 PREDICATES      43 URIs      16 LITERALS      5 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00224-018-9902-1 schema:about anzsrc-for:14
2 anzsrc-for:1402
3 schema:author N8d0aeeea22e449afb3944b051be93eab
4 schema:citation sg:pub.10.1007/bf01737559
5 sg:pub.10.1007/s00224-008-9152-8
6 sg:pub.10.1007/s00224-017-9826-1
7 sg:pub.10.1007/s00453-006-1211-4
8 sg:pub.10.1007/s00453-007-9018-5
9 sg:pub.10.1007/s00453-010-9427-8
10 https://doi.org/10.1016/j.cosrev.2009.04.003
11 https://doi.org/10.1016/j.jcss.2008.07.001
12 https://doi.org/10.1016/j.tcs.2008.06.045
13 https://doi.org/10.1016/j.tcs.2009.01.005
14 https://doi.org/10.1137/070680096
15 https://doi.org/10.1137/090748986
16 https://doi.org/10.1137/s0097539701397059
17 https://doi.org/10.1145/1060590.1060600
18 https://doi.org/10.1145/1868237.1868251
19 https://doi.org/10.1145/2209249.2209274
20 https://doi.org/10.1145/2344422.2344426
21 https://doi.org/10.1145/2629666
22 https://doi.org/10.1145/2940716.2940750
23 schema:datePublished 2018-12-13
24 schema:datePublishedReg 2018-12-13
25 schema:description We investigate the efficiency of some Stackelberg strategies in congestion games with affine latency functions. A Stackelberg strategy is an algorithm that chooses a subset of players and assigns them a prescribed strategy with the purpose of mitigating the detrimental effect that the selfish behavior of the remaining uncoordinated players may cause to the overall performance of the system. The efficiency of a Stackelberg strategy is measured in terms of the price of anarchy of the pure Nash equilibria they induce. Three Stackelberg strategies, namely Largest Latency First, Cover and Scale, were already considered in the literature and non-tight upper and lower bounds on their price of anarchy were given. We reconsider these strategies and provide the exact bound on the price of anarchy of both Largest Latency First and Cover and a better upper bound on the price of anarchy of Scale.
26 schema:genre research_article
27 schema:inLanguage en
28 schema:isAccessibleForFree false
29 schema:isPartOf sg:journal.1052098
30 schema:name On Stackelberg Strategies in Affine Congestion Games
31 schema:pagination 1-22
32 schema:productId N31346debb2464860bd49b3080ff1e6e6
33 Ncbfea7b8c0ef4fa394f3ef92d24a73bd
34 Ne256e370e3a6415a914ffd81f1588973
35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1110555728
36 https://doi.org/10.1007/s00224-018-9902-1
37 schema:sdDatePublished 2019-04-11T08:23
38 schema:sdLicense https://scigraph.springernature.com/explorer/license/
39 schema:sdPublisher N3bd2c1a170a6496e98a14e9a9cd8f496
40 schema:url https://link.springer.com/10.1007%2Fs00224-018-9902-1
41 sgo:license sg:explorer/license/
42 sgo:sdDataset articles
43 rdf:type schema:ScholarlyArticle
44 N31346debb2464860bd49b3080ff1e6e6 schema:name doi
45 schema:value 10.1007/s00224-018-9902-1
46 rdf:type schema:PropertyValue
47 N3bd2c1a170a6496e98a14e9a9cd8f496 schema:name Springer Nature - SN SciGraph project
48 rdf:type schema:Organization
49 N8d0aeeea22e449afb3944b051be93eab rdf:first sg:person.012652036261.27
50 rdf:rest Na6b41d5a6d6841f3a1e7f21181ee2fac
51 Na6b41d5a6d6841f3a1e7f21181ee2fac rdf:first sg:person.012770274011.86
52 rdf:rest rdf:nil
53 Ncbfea7b8c0ef4fa394f3ef92d24a73bd schema:name dimensions_id
54 schema:value pub.1110555728
55 rdf:type schema:PropertyValue
56 Ne256e370e3a6415a914ffd81f1588973 schema:name readcube_id
57 schema:value fd8a4cf440796ff3498c5fe7235f286f7dfb92d141f3bd09ad367fb712997c74
58 rdf:type schema:PropertyValue
59 anzsrc-for:14 schema:inDefinedTermSet anzsrc-for:
60 schema:name Economics
61 rdf:type schema:DefinedTerm
62 anzsrc-for:1402 schema:inDefinedTermSet anzsrc-for:
63 schema:name Applied Economics
64 rdf:type schema:DefinedTerm
65 sg:journal.1052098 schema:issn 1432-4350
66 1433-0490
67 schema:name Theory of Computing Systems
68 rdf:type schema:Periodical
69 sg:person.012652036261.27 schema:affiliation https://www.grid.ac/institutes/grid.9906.6
70 schema:familyName Bilò
71 schema:givenName Vittorio
72 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012652036261.27
73 rdf:type schema:Person
74 sg:person.012770274011.86 schema:affiliation https://www.grid.ac/institutes/grid.466750.6
75 schema:familyName Vinci
76 schema:givenName Cosimo
77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012770274011.86
78 rdf:type schema:Person
79 sg:pub.10.1007/bf01737559 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044775936
80 https://doi.org/10.1007/bf01737559
81 rdf:type schema:CreativeWork
82 sg:pub.10.1007/s00224-008-9152-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042669741
83 https://doi.org/10.1007/s00224-008-9152-8
84 rdf:type schema:CreativeWork
85 sg:pub.10.1007/s00224-017-9826-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093123382
86 https://doi.org/10.1007/s00224-017-9826-1
87 rdf:type schema:CreativeWork
88 sg:pub.10.1007/s00453-006-1211-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022756805
89 https://doi.org/10.1007/s00453-006-1211-4
90 rdf:type schema:CreativeWork
91 sg:pub.10.1007/s00453-007-9018-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033706914
92 https://doi.org/10.1007/s00453-007-9018-5
93 rdf:type schema:CreativeWork
94 sg:pub.10.1007/s00453-010-9427-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016706126
95 https://doi.org/10.1007/s00453-010-9427-8
96 rdf:type schema:CreativeWork
97 https://doi.org/10.1016/j.cosrev.2009.04.003 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035244584
98 rdf:type schema:CreativeWork
99 https://doi.org/10.1016/j.jcss.2008.07.001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042525379
100 rdf:type schema:CreativeWork
101 https://doi.org/10.1016/j.tcs.2008.06.045 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013590738
102 rdf:type schema:CreativeWork
103 https://doi.org/10.1016/j.tcs.2009.01.005 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038819075
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1137/070680096 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062850841
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1137/090748986 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062855983
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1137/s0097539701397059 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879332
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1145/1060590.1060600 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050456256
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1145/1868237.1868251 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012378343
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1145/2209249.2209274 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029940041
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1145/2344422.2344426 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017791470
118 rdf:type schema:CreativeWork
119 https://doi.org/10.1145/2629666 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031469011
120 rdf:type schema:CreativeWork
121 https://doi.org/10.1145/2940716.2940750 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032682251
122 rdf:type schema:CreativeWork
123 https://www.grid.ac/institutes/grid.466750.6 schema:alternateName Gran Sasso Science Institute
124 schema:name Gran Sasso Science Institute, L’Aquila, Italy
125 rdf:type schema:Organization
126 https://www.grid.ac/institutes/grid.9906.6 schema:alternateName University of Salento
127 schema:name Department of Mathematics and Physics “Ennio De Giorgi”, University of Salento, Provinciale Lecce-Arnesano, P.O. Box 193, 73100, Lecce, Italy
128 rdf:type schema:Organization
 




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


...