A Unifying Tool for Bounding the Quality of Non-Cooperative Solutions in Weighted Congestion Games View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2018-07

AUTHORS

Vittorio Bilò

ABSTRACT

We present a general technique, based on a primal-dual formulation, for analyzing the quality of self-emerging solutions in weighted congestion games. With respect to traditional combinatorial approaches, the primal-dual schema has at least three advantages: first, it provides an analytic tool which can always be used to prove tight upper bounds for all the cases in which we are able to characterize exactly the polyhedron of the solutions under analysis; secondly, in each such a case, the complementary slackness conditions give us a hint on how to construct matching lower bounding instances; thirdly, proofs become simpler and easy to check. For the sake of exposition, we first apply our technique to the problems of bounding the price of anarchy and stability of exact and approximate pure Nash equilibria, as well as the approximation ratio of the strategy profiles achieved after a one-round walk starting from the empty state, in the case of affine latency functions and we show how all the known upper bounds for these measures (and some of their generalizations) can be easily reobtained under a unified approach. Then, we use the technique to attack the more challenging setting of polynomial latency functions. In particular, we obtain the first known upper bounds on the price of stability of pure Nash equilibria and on the approximation ratio of the strategy profiles achieved after a one-round walk starting from the empty state for unweighted players in the cases of quadratic and cubic latency functions. More... »

PAGES

1288-1317

References to SciGraph publications

  • 2011-11. Tight Bounds for Selfish and Greedy Load Balancing in ALGORITHMICA
  • 1973-12. A class of games possessing pure-strategy Nash equilibria in INTERNATIONAL JOURNAL OF GAME THEORY
  • 2010. The Impact of Altruism on the Efficiency of Atomic Congestion Games in TRUSTWORTHLY GLOBAL COMPUTING
  • 2012. On Bidimensional Congestion Games in STRUCTURAL INFORMATION AND COMMUNICATION COMPLEXITY
  • 2014. On Linear Congestion Games with Altruistic Social Context in COMPUTING AND COMBINATORICS
  • 2004. Convergence Issues in Competitive Games in APPROXIMATION, RANDOMIZATION, AND COMBINATORIAL OPTIMIZATION. ALGORITHMS AND TECHNIQUES
  • 2006. Symmetry in Network Congestion Games: Pure Equilibria and Anarchy Cost in APPROXIMATION AND ONLINE ALGORITHMS
  • 2005. On the Price of Anarchy and Stability of Correlated Equilibria of Linear Congestion Games,, in ALGORITHMS – ESA 2005
  • 2015-01. Some Anomalies of Farsighted Strategic Behavior in THEORY OF COMPUTING SYSTEMS
  • 2010-07. Stackelberg Strategies for Atomic Congestion Games in THEORY OF COMPUTING SYSTEMS
  • 2007-01. Selfish Load Balancing and Atomic Congestion Games in ALGORITHMICA
  • 2010. The Limits of Smoothness: A Primal-Dual Framework for Price of Anarchy Bounds in INTERNET AND NETWORK ECONOMICS
  • 2015. On Stackelberg Strategies in Affine Congestion Games in WEB AND INTERNET ECONOMICS
  • 2011-07. Characterizing the Existence of Potential Functions in Weighted Congestion Games in THEORY OF COMPUTING SYSTEMS
  • 2009. Strong and Pareto Price of Anarchy in Congestion Games in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 2015-02. Oblivious Algorithms for the Maximum Directed Cut Problem in ALGORITHMICA
  • 2012. A Theoretical Examination of Practical Game Playing: Lookahead Search in ALGORITHMIC GAME THEORY
  • 2016. On the Robustness of the Approximate Price of Anarchy in Generalized Congestion Games in ALGORITHMIC GAME THEORY
  • 2009-10. Analysis of Approximation Algorithms for k-Set Cover Using Factor-Revealing Linear Programs in THEORY OF COMPUTING SYSTEMS
  • 2011-07. Performance of One-Round Walks in Linear Congestion Games in THEORY OF COMPUTING SYSTEMS
  • 2016-11. On the performance of mildly greedy players in cut games in JOURNAL OF COMBINATORIAL OPTIMIZATION
  • 2002-04-12. Worst-Case Equilibria in STACS 99
  • 2011-09. On the Performance of Approximate Equilibria in Congestion Games in ALGORITHMICA
  • Journal

    TITLE

    Theory of Computing Systems

    ISSUE

    5

    VOLUME

    62

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00224-017-9826-1

    DOI

    http://dx.doi.org/10.1007/s00224-017-9826-1

    DIMENSIONS

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


    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/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "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"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1145/950620.950621", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000944981"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-49116-3_38", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002207134", 
              "https://doi.org/10.1007/3-540-49116-3_38"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-49116-3_38", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002207134", 
              "https://doi.org/10.1007/3-540-49116-3_38"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-27821-4_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003507443", 
              "https://doi.org/10.1007/978-3-540-27821-4_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-27821-4_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003507443", 
              "https://doi.org/10.1007/978-3-540-27821-4_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1993636.1993716", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007979705"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-53354-3_8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011215800", 
              "https://doi.org/10.1007/978-3-662-53354-3_8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1868237.1868251", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012378343"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-02927-1_24", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014032202", 
              "https://doi.org/10.1007/978-3-642-02927-1_24"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-02927-1_24", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014032202", 
              "https://doi.org/10.1007/978-3-642-02927-1_24"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10878-015-9898-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015171432", 
              "https://doi.org/10.1007/s10878-015-9898-2"
            ], 
            "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": "sg:pub.10.1007/978-3-642-15640-3_12", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017021240", 
              "https://doi.org/10.1007/978-3-642-15640-3_12"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-15640-3_12", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017021240", 
              "https://doi.org/10.1007/978-3-642-15640-3_12"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2012.02.033", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018901539"
            ], 
            "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/1187436.1216584", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025772968"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-33996-7_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026445824", 
              "https://doi.org/10.1007/978-3-642-33996-7_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00453-010-9449-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027923807", 
              "https://doi.org/10.1007/s00453-010-9449-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-008-9112-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029504498", 
              "https://doi.org/10.1007/s00224-008-9112-3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-008-9112-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029504498", 
              "https://doi.org/10.1007/s00224-008-9112-3"
            ], 
            "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/2841229", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030920497"
            ], 
            "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/978-3-642-31104-8_13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036296323", 
              "https://doi.org/10.1007/978-3-642-31104-8_13"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00453-013-9806-z", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036677546", 
              "https://doi.org/10.1007/s00453-013-9806-z"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-010-9309-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040895760", 
              "https://doi.org/10.1007/s00224-010-9309-0"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-17572-5_26", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041684511", 
              "https://doi.org/10.1007/978-3-642-17572-5_26"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-17572-5_26", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041684511", 
              "https://doi.org/10.1007/978-3-642-17572-5_26"
            ], 
            "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/978-3-319-08783-2_47", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044149470", 
              "https://doi.org/10.1007/978-3-319-08783-2_47"
            ], 
            "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": "sg:pub.10.1007/s00224-011-9315-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046753659", 
              "https://doi.org/10.1007/s00224-011-9315-x"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-013-9529-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047944956", 
              "https://doi.org/10.1007/s00224-013-9529-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11561071_8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049866450", 
              "https://doi.org/10.1007/11561071_8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11561071_8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049866450", 
              "https://doi.org/10.1007/11561071_8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11561071_8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049866450", 
              "https://doi.org/10.1007/11561071_8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1060590.1060600", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050456256"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-48995-6_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053291738", 
              "https://doi.org/10.1007/978-3-662-48995-6_10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11671411_13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053385843", 
              "https://doi.org/10.1007/11671411_13"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11671411_13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053385843", 
              "https://doi.org/10.1007/11671411_13"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/s0960129515000079", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1054905039"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/06067660x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062849940"
            ], 
            "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.1287/moor.1120.0543", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064723231"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2018-07", 
        "datePublishedReg": "2018-07-01", 
        "description": "We present a general technique, based on a primal-dual formulation, for analyzing the quality of self-emerging solutions in weighted congestion games. With respect to traditional combinatorial approaches, the primal-dual schema has at least three advantages: first, it provides an analytic tool which can always be used to prove tight upper bounds for all the cases in which we are able to characterize exactly the polyhedron of the solutions under analysis; secondly, in each such a case, the complementary slackness conditions give us a hint on how to construct matching lower bounding instances; thirdly, proofs become simpler and easy to check. For the sake of exposition, we first apply our technique to the problems of bounding the price of anarchy and stability of exact and approximate pure Nash equilibria, as well as the approximation ratio of the strategy profiles achieved after a one-round walk starting from the empty state, in the case of affine latency functions and we show how all the known upper bounds for these measures (and some of their generalizations) can be easily reobtained under a unified approach. Then, we use the technique to attack the more challenging setting of polynomial latency functions. In particular, we obtain the first known upper bounds on the price of stability of pure Nash equilibria and on the approximation ratio of the strategy profiles achieved after a one-round walk starting from the empty state for unweighted players in the cases of quadratic and cubic latency functions.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00224-017-9826-1", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1052098", 
            "issn": [
              "1432-4350", 
              "1433-0490"
            ], 
            "name": "Theory of Computing Systems", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "5", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "62"
          }
        ], 
        "name": "A Unifying Tool for Bounding the Quality of Non-Cooperative Solutions in Weighted Congestion Games", 
        "pagination": "1288-1317", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "c6acd6f4961ed256e8f119b71ecfd92f2c01638e1b2f5b4c15a76e7cd2cea20b"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00224-017-9826-1"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1093123382"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00224-017-9826-1", 
          "https://app.dimensions.ai/details/publication/pub.1093123382"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T17:27", 
        "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/0000000001_0000000264/records_8672_00000493.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007/s00224-017-9826-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-017-9826-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-017-9826-1'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00224-017-9826-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-017-9826-1'


     

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

    198 TRIPLES      21 PREDICATES      65 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00224-017-9826-1 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author N974474566e4d4fea94265240e6aa45d2
    4 schema:citation sg:pub.10.1007/11561071_8
    5 sg:pub.10.1007/11671411_13
    6 sg:pub.10.1007/3-540-49116-3_38
    7 sg:pub.10.1007/978-3-319-08783-2_47
    8 sg:pub.10.1007/978-3-540-27821-4_17
    9 sg:pub.10.1007/978-3-642-02927-1_24
    10 sg:pub.10.1007/978-3-642-15640-3_12
    11 sg:pub.10.1007/978-3-642-17572-5_26
    12 sg:pub.10.1007/978-3-642-31104-8_13
    13 sg:pub.10.1007/978-3-642-33996-7_22
    14 sg:pub.10.1007/978-3-662-48995-6_10
    15 sg:pub.10.1007/978-3-662-53354-3_8
    16 sg:pub.10.1007/bf01737559
    17 sg:pub.10.1007/s00224-008-9112-3
    18 sg:pub.10.1007/s00224-008-9152-8
    19 sg:pub.10.1007/s00224-010-9309-0
    20 sg:pub.10.1007/s00224-011-9315-x
    21 sg:pub.10.1007/s00224-013-9529-1
    22 sg:pub.10.1007/s00453-006-1211-4
    23 sg:pub.10.1007/s00453-010-9427-8
    24 sg:pub.10.1007/s00453-010-9449-2
    25 sg:pub.10.1007/s00453-013-9806-z
    26 sg:pub.10.1007/s10878-015-9898-2
    27 https://doi.org/10.1016/j.tcs.2012.02.033
    28 https://doi.org/10.1017/s0960129515000079
    29 https://doi.org/10.1137/06067660x
    30 https://doi.org/10.1137/070680096
    31 https://doi.org/10.1137/090748986
    32 https://doi.org/10.1145/1060590.1060600
    33 https://doi.org/10.1145/1187436.1216584
    34 https://doi.org/10.1145/1868237.1868251
    35 https://doi.org/10.1145/1993636.1993716
    36 https://doi.org/10.1145/2209249.2209274
    37 https://doi.org/10.1145/2629666
    38 https://doi.org/10.1145/2841229
    39 https://doi.org/10.1145/2940716.2940750
    40 https://doi.org/10.1145/950620.950621
    41 https://doi.org/10.1287/moor.1120.0543
    42 schema:datePublished 2018-07
    43 schema:datePublishedReg 2018-07-01
    44 schema:description We present a general technique, based on a primal-dual formulation, for analyzing the quality of self-emerging solutions in weighted congestion games. With respect to traditional combinatorial approaches, the primal-dual schema has at least three advantages: first, it provides an analytic tool which can always be used to prove tight upper bounds for all the cases in which we are able to characterize exactly the polyhedron of the solutions under analysis; secondly, in each such a case, the complementary slackness conditions give us a hint on how to construct matching lower bounding instances; thirdly, proofs become simpler and easy to check. For the sake of exposition, we first apply our technique to the problems of bounding the price of anarchy and stability of exact and approximate pure Nash equilibria, as well as the approximation ratio of the strategy profiles achieved after a one-round walk starting from the empty state, in the case of affine latency functions and we show how all the known upper bounds for these measures (and some of their generalizations) can be easily reobtained under a unified approach. Then, we use the technique to attack the more challenging setting of polynomial latency functions. In particular, we obtain the first known upper bounds on the price of stability of pure Nash equilibria and on the approximation ratio of the strategy profiles achieved after a one-round walk starting from the empty state for unweighted players in the cases of quadratic and cubic latency functions.
    45 schema:genre research_article
    46 schema:inLanguage en
    47 schema:isAccessibleForFree false
    48 schema:isPartOf N6d3ad51876194101ba165a4d472abd39
    49 Nb23367ddadca4f64a7760b3da43442d6
    50 sg:journal.1052098
    51 schema:name A Unifying Tool for Bounding the Quality of Non-Cooperative Solutions in Weighted Congestion Games
    52 schema:pagination 1288-1317
    53 schema:productId N2f135bf2263a4ce094848c8bdf8e395e
    54 Nbbdc378427324dbfbdb1a918315ec9e0
    55 Ned0bf49ba91248c3ade19aaafbb4e1dc
    56 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093123382
    57 https://doi.org/10.1007/s00224-017-9826-1
    58 schema:sdDatePublished 2019-04-10T17:27
    59 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    60 schema:sdPublisher Na4247772333b4de986983441efac7d2a
    61 schema:url http://link.springer.com/10.1007/s00224-017-9826-1
    62 sgo:license sg:explorer/license/
    63 sgo:sdDataset articles
    64 rdf:type schema:ScholarlyArticle
    65 N2f135bf2263a4ce094848c8bdf8e395e schema:name doi
    66 schema:value 10.1007/s00224-017-9826-1
    67 rdf:type schema:PropertyValue
    68 N6d3ad51876194101ba165a4d472abd39 schema:issueNumber 5
    69 rdf:type schema:PublicationIssue
    70 N974474566e4d4fea94265240e6aa45d2 rdf:first sg:person.012652036261.27
    71 rdf:rest rdf:nil
    72 Na4247772333b4de986983441efac7d2a schema:name Springer Nature - SN SciGraph project
    73 rdf:type schema:Organization
    74 Nb23367ddadca4f64a7760b3da43442d6 schema:volumeNumber 62
    75 rdf:type schema:PublicationVolume
    76 Nbbdc378427324dbfbdb1a918315ec9e0 schema:name readcube_id
    77 schema:value c6acd6f4961ed256e8f119b71ecfd92f2c01638e1b2f5b4c15a76e7cd2cea20b
    78 rdf:type schema:PropertyValue
    79 Ned0bf49ba91248c3ade19aaafbb4e1dc schema:name dimensions_id
    80 schema:value pub.1093123382
    81 rdf:type schema:PropertyValue
    82 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    83 schema:name Mathematical Sciences
    84 rdf:type schema:DefinedTerm
    85 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    86 schema:name Pure Mathematics
    87 rdf:type schema:DefinedTerm
    88 sg:journal.1052098 schema:issn 1432-4350
    89 1433-0490
    90 schema:name Theory of Computing Systems
    91 rdf:type schema:Periodical
    92 sg:person.012652036261.27 schema:affiliation https://www.grid.ac/institutes/grid.9906.6
    93 schema:familyName Bilò
    94 schema:givenName Vittorio
    95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012652036261.27
    96 rdf:type schema:Person
    97 sg:pub.10.1007/11561071_8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049866450
    98 https://doi.org/10.1007/11561071_8
    99 rdf:type schema:CreativeWork
    100 sg:pub.10.1007/11671411_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053385843
    101 https://doi.org/10.1007/11671411_13
    102 rdf:type schema:CreativeWork
    103 sg:pub.10.1007/3-540-49116-3_38 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002207134
    104 https://doi.org/10.1007/3-540-49116-3_38
    105 rdf:type schema:CreativeWork
    106 sg:pub.10.1007/978-3-319-08783-2_47 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044149470
    107 https://doi.org/10.1007/978-3-319-08783-2_47
    108 rdf:type schema:CreativeWork
    109 sg:pub.10.1007/978-3-540-27821-4_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003507443
    110 https://doi.org/10.1007/978-3-540-27821-4_17
    111 rdf:type schema:CreativeWork
    112 sg:pub.10.1007/978-3-642-02927-1_24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014032202
    113 https://doi.org/10.1007/978-3-642-02927-1_24
    114 rdf:type schema:CreativeWork
    115 sg:pub.10.1007/978-3-642-15640-3_12 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017021240
    116 https://doi.org/10.1007/978-3-642-15640-3_12
    117 rdf:type schema:CreativeWork
    118 sg:pub.10.1007/978-3-642-17572-5_26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041684511
    119 https://doi.org/10.1007/978-3-642-17572-5_26
    120 rdf:type schema:CreativeWork
    121 sg:pub.10.1007/978-3-642-31104-8_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036296323
    122 https://doi.org/10.1007/978-3-642-31104-8_13
    123 rdf:type schema:CreativeWork
    124 sg:pub.10.1007/978-3-642-33996-7_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026445824
    125 https://doi.org/10.1007/978-3-642-33996-7_22
    126 rdf:type schema:CreativeWork
    127 sg:pub.10.1007/978-3-662-48995-6_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053291738
    128 https://doi.org/10.1007/978-3-662-48995-6_10
    129 rdf:type schema:CreativeWork
    130 sg:pub.10.1007/978-3-662-53354-3_8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011215800
    131 https://doi.org/10.1007/978-3-662-53354-3_8
    132 rdf:type schema:CreativeWork
    133 sg:pub.10.1007/bf01737559 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044775936
    134 https://doi.org/10.1007/bf01737559
    135 rdf:type schema:CreativeWork
    136 sg:pub.10.1007/s00224-008-9112-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029504498
    137 https://doi.org/10.1007/s00224-008-9112-3
    138 rdf:type schema:CreativeWork
    139 sg:pub.10.1007/s00224-008-9152-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042669741
    140 https://doi.org/10.1007/s00224-008-9152-8
    141 rdf:type schema:CreativeWork
    142 sg:pub.10.1007/s00224-010-9309-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040895760
    143 https://doi.org/10.1007/s00224-010-9309-0
    144 rdf:type schema:CreativeWork
    145 sg:pub.10.1007/s00224-011-9315-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1046753659
    146 https://doi.org/10.1007/s00224-011-9315-x
    147 rdf:type schema:CreativeWork
    148 sg:pub.10.1007/s00224-013-9529-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047944956
    149 https://doi.org/10.1007/s00224-013-9529-1
    150 rdf:type schema:CreativeWork
    151 sg:pub.10.1007/s00453-006-1211-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022756805
    152 https://doi.org/10.1007/s00453-006-1211-4
    153 rdf:type schema:CreativeWork
    154 sg:pub.10.1007/s00453-010-9427-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016706126
    155 https://doi.org/10.1007/s00453-010-9427-8
    156 rdf:type schema:CreativeWork
    157 sg:pub.10.1007/s00453-010-9449-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027923807
    158 https://doi.org/10.1007/s00453-010-9449-2
    159 rdf:type schema:CreativeWork
    160 sg:pub.10.1007/s00453-013-9806-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1036677546
    161 https://doi.org/10.1007/s00453-013-9806-z
    162 rdf:type schema:CreativeWork
    163 sg:pub.10.1007/s10878-015-9898-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015171432
    164 https://doi.org/10.1007/s10878-015-9898-2
    165 rdf:type schema:CreativeWork
    166 https://doi.org/10.1016/j.tcs.2012.02.033 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018901539
    167 rdf:type schema:CreativeWork
    168 https://doi.org/10.1017/s0960129515000079 schema:sameAs https://app.dimensions.ai/details/publication/pub.1054905039
    169 rdf:type schema:CreativeWork
    170 https://doi.org/10.1137/06067660x schema:sameAs https://app.dimensions.ai/details/publication/pub.1062849940
    171 rdf:type schema:CreativeWork
    172 https://doi.org/10.1137/070680096 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062850841
    173 rdf:type schema:CreativeWork
    174 https://doi.org/10.1137/090748986 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062855983
    175 rdf:type schema:CreativeWork
    176 https://doi.org/10.1145/1060590.1060600 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050456256
    177 rdf:type schema:CreativeWork
    178 https://doi.org/10.1145/1187436.1216584 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025772968
    179 rdf:type schema:CreativeWork
    180 https://doi.org/10.1145/1868237.1868251 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012378343
    181 rdf:type schema:CreativeWork
    182 https://doi.org/10.1145/1993636.1993716 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007979705
    183 rdf:type schema:CreativeWork
    184 https://doi.org/10.1145/2209249.2209274 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029940041
    185 rdf:type schema:CreativeWork
    186 https://doi.org/10.1145/2629666 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031469011
    187 rdf:type schema:CreativeWork
    188 https://doi.org/10.1145/2841229 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030920497
    189 rdf:type schema:CreativeWork
    190 https://doi.org/10.1145/2940716.2940750 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032682251
    191 rdf:type schema:CreativeWork
    192 https://doi.org/10.1145/950620.950621 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000944981
    193 rdf:type schema:CreativeWork
    194 https://doi.org/10.1287/moor.1120.0543 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064723231
    195 rdf:type schema:CreativeWork
    196 https://www.grid.ac/institutes/grid.9906.6 schema:alternateName University of Salento
    197 schema:name Department of Mathematics and Physics “Ennio De Giorgi”, University of Salento, Provinciale Lecce-Arnesano, P.O. Box 193, 73100, Lecce, Italy
    198 rdf:type schema:Organization
     




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


    ...