Selfish Load Balancing and Atomic Congestion Games View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2007-01

AUTHORS

Subhash Suri, Csaba D. Toth, Yunhong Zhou

ABSTRACT

We revisit a classical load balancing problem in the modern context of decentralized systems and self-interested clients. In particular, there is a set of clients, each of whom must choose a server from a permissible set. Each client has a unit-length job and selfishly wants to minimize its own latency (job completion time). A server's latency is inversely proportional to its speed, but it grows linearly with (or, more generally, as the pth power of) the number of clients matched to it. This interaction is naturally modeled as an atomic congestion game, which we call selfish load balancing. We analyze the Nash equilibria of this game and prove nearly tight bounds on the price of anarchy (worst-case ratio between a Nash solution and the social optimum). In particular, for linear latency functions, we show that if the server speeds are relatively bounded and the number of clients is large compared with the number of servers, then every Nash assignment approaches social optimum. Without any assumptions on the number of clients, servers, and server speeds, the price of anarchy is at most 2.5. If all servers have the same speed, then the price of anarchy further improves to We also exhibit a lower bound of 2.01. Our proof techniques can also be adapted for the coordinated load balancing problem under L2 norm, where it slightly improves the best previously known upper bound on the competitive ratio of a simple greedy scheme. More... »

PAGES

79-96

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-006-1211-4

DOI

http://dx.doi.org/10.1007/s00453-006-1211-4

DIMENSIONS

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


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 California, Santa Barbara", 
          "id": "https://www.grid.ac/institutes/grid.133342.4", 
          "name": [
            "Department of Computer Science, University of California at Santa\nBarbara, Santa Barbara, CA 93106, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Suri", 
        "givenName": "Subhash", 
        "id": "sg:person.012347751512.96", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012347751512.96"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Massachusetts Institute of Technology", 
          "id": "https://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "Department of Mathematics, Room 2-336, MIT, Cambridge, MA 02139, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Toth", 
        "givenName": "Csaba D.", 
        "id": "sg:person.011373745067.01", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011373745067.01"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Hewlett-Packard (United States)", 
          "id": "https://www.grid.ac/institutes/grid.418547.b", 
          "name": [
            "Hewlett-Packard Laboratories, 1501 Page Mill Road, Palo Alto, CA 94304, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zhou", 
        "givenName": "Yunhong", 
        "id": "sg:person.015252425053.08", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252425053.08"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2007-01", 
    "datePublishedReg": "2007-01-01", 
    "description": "We revisit a classical load balancing problem in the modern context of decentralized systems and self-interested clients. In particular, there is a set of clients, each of whom must choose a server from a permissible set. Each client has a unit-length job and selfishly wants to minimize its own latency (job completion time). A server's latency is inversely proportional to its speed, but it grows linearly with (or, more generally, as the pth power of) the number of clients matched to it. This interaction is naturally modeled as an atomic congestion game, which we call selfish load balancing. We analyze the Nash equilibria of this game and prove nearly tight bounds on the price of anarchy (worst-case ratio between a Nash solution and the social optimum). In particular, for linear latency functions, we show that if the server speeds are relatively bounded and the number of clients is large compared with the number of servers, then every Nash assignment approaches social optimum. Without any assumptions on the number of clients, servers, and server speeds, the price of anarchy is at most 2.5. If all servers have the same speed, then the price of anarchy further improves to We also exhibit a lower bound of 2.01. Our proof techniques can also be adapted for the coordinated load balancing problem under L2 norm, where it slightly improves the best previously known upper bound on the competitive ratio of a simple greedy scheme.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00453-006-1211-4", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "47"
      }
    ], 
    "name": "Selfish Load Balancing and Atomic Congestion Games", 
    "pagination": "79-96", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "6c6af4ef2b2d4142210c14c8aa2c5543a1cd976e9ce94ea3af91ae2aaa7bde21"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00453-006-1211-4"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1022756805"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00453-006-1211-4", 
      "https://app.dimensions.ai/details/publication/pub.1022756805"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T02:00", 
    "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_8700_00000512.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007%2Fs00453-006-1211-4"
  }
]
 

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/s00453-006-1211-4'

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/s00453-006-1211-4'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-006-1211-4'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-006-1211-4'


 

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

81 TRIPLES      20 PREDICATES      27 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00453-006-1211-4 schema:about anzsrc-for:14
2 anzsrc-for:1402
3 schema:author Na35939d6f80d4d8d80138151b069d780
4 schema:datePublished 2007-01
5 schema:datePublishedReg 2007-01-01
6 schema:description We revisit a classical load balancing problem in the modern context of decentralized systems and self-interested clients. In particular, there is a set of clients, each of whom must choose a server from a permissible set. Each client has a unit-length job and selfishly wants to minimize its own latency (job completion time). A server's latency is inversely proportional to its speed, but it grows linearly with (or, more generally, as the pth power of) the number of clients matched to it. This interaction is naturally modeled as an atomic congestion game, which we call selfish load balancing. We analyze the Nash equilibria of this game and prove nearly tight bounds on the price of anarchy (worst-case ratio between a Nash solution and the social optimum). In particular, for linear latency functions, we show that if the server speeds are relatively bounded and the number of clients is large compared with the number of servers, then every Nash assignment approaches social optimum. Without any assumptions on the number of clients, servers, and server speeds, the price of anarchy is at most 2.5. If all servers have the same speed, then the price of anarchy further improves to We also exhibit a lower bound of 2.01. Our proof techniques can also be adapted for the coordinated load balancing problem under L2 norm, where it slightly improves the best previously known upper bound on the competitive ratio of a simple greedy scheme.
7 schema:genre research_article
8 schema:inLanguage en
9 schema:isAccessibleForFree true
10 schema:isPartOf N392cf19469a34eb497b969ce8620936d
11 Nbdd7e84bc77244d69e9b8e54f5b6ec52
12 sg:journal.1047644
13 schema:name Selfish Load Balancing and Atomic Congestion Games
14 schema:pagination 79-96
15 schema:productId N29474cb29c324a5084196f91f96b96f8
16 N2d2d40fd31f54c929fb3103a9ffa5592
17 Nd4d31167b724402aafcebcb11ec17d22
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022756805
19 https://doi.org/10.1007/s00453-006-1211-4
20 schema:sdDatePublished 2019-04-11T02:00
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher N0ab491ead9804952a7abcdf619582b96
23 schema:url http://link.springer.com/10.1007%2Fs00453-006-1211-4
24 sgo:license sg:explorer/license/
25 sgo:sdDataset articles
26 rdf:type schema:ScholarlyArticle
27 N0ab491ead9804952a7abcdf619582b96 schema:name Springer Nature - SN SciGraph project
28 rdf:type schema:Organization
29 N16ec6602325f487eaf886facf1136220 rdf:first sg:person.011373745067.01
30 rdf:rest N43c37faf15bc4bc2892846adf79dd8d0
31 N29474cb29c324a5084196f91f96b96f8 schema:name doi
32 schema:value 10.1007/s00453-006-1211-4
33 rdf:type schema:PropertyValue
34 N2d2d40fd31f54c929fb3103a9ffa5592 schema:name readcube_id
35 schema:value 6c6af4ef2b2d4142210c14c8aa2c5543a1cd976e9ce94ea3af91ae2aaa7bde21
36 rdf:type schema:PropertyValue
37 N392cf19469a34eb497b969ce8620936d schema:issueNumber 1
38 rdf:type schema:PublicationIssue
39 N43c37faf15bc4bc2892846adf79dd8d0 rdf:first sg:person.015252425053.08
40 rdf:rest rdf:nil
41 Na35939d6f80d4d8d80138151b069d780 rdf:first sg:person.012347751512.96
42 rdf:rest N16ec6602325f487eaf886facf1136220
43 Nbdd7e84bc77244d69e9b8e54f5b6ec52 schema:volumeNumber 47
44 rdf:type schema:PublicationVolume
45 Nd4d31167b724402aafcebcb11ec17d22 schema:name dimensions_id
46 schema:value pub.1022756805
47 rdf:type schema:PropertyValue
48 anzsrc-for:14 schema:inDefinedTermSet anzsrc-for:
49 schema:name Economics
50 rdf:type schema:DefinedTerm
51 anzsrc-for:1402 schema:inDefinedTermSet anzsrc-for:
52 schema:name Applied Economics
53 rdf:type schema:DefinedTerm
54 sg:journal.1047644 schema:issn 0178-4617
55 1432-0541
56 schema:name Algorithmica
57 rdf:type schema:Periodical
58 sg:person.011373745067.01 schema:affiliation https://www.grid.ac/institutes/grid.116068.8
59 schema:familyName Toth
60 schema:givenName Csaba D.
61 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011373745067.01
62 rdf:type schema:Person
63 sg:person.012347751512.96 schema:affiliation https://www.grid.ac/institutes/grid.133342.4
64 schema:familyName Suri
65 schema:givenName Subhash
66 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012347751512.96
67 rdf:type schema:Person
68 sg:person.015252425053.08 schema:affiliation https://www.grid.ac/institutes/grid.418547.b
69 schema:familyName Zhou
70 schema:givenName Yunhong
71 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252425053.08
72 rdf:type schema:Person
73 https://www.grid.ac/institutes/grid.116068.8 schema:alternateName Massachusetts Institute of Technology
74 schema:name Department of Mathematics, Room 2-336, MIT, Cambridge, MA 02139, USA
75 rdf:type schema:Organization
76 https://www.grid.ac/institutes/grid.133342.4 schema:alternateName University of California, Santa Barbara
77 schema:name Department of Computer Science, University of California at Santa Barbara, Santa Barbara, CA 93106, USA
78 rdf:type schema:Organization
79 https://www.grid.ac/institutes/grid.418547.b schema:alternateName Hewlett-Packard (United States)
80 schema:name Hewlett-Packard Laboratories, 1501 Page Mill Road, Palo Alto, CA 94304, USA
81 rdf:type schema:Organization
 




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


...