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 Nb5371b566d8e465cbcdfe1fc7cc4e62f
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 N3f5418d88dd7493589feaf925d321da4
11 Ne2fb1c5ea4ad42f3afa626ead4a3bfca
12 sg:journal.1047644
13 schema:name Selfish Load Balancing and Atomic Congestion Games
14 schema:pagination 79-96
15 schema:productId N6c641ae3854d4e96878b08878edbd863
16 N808640f43d824269b881fc732aa4e651
17 N8129f71658eb4301b0fc525836b90242
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 Ne223e86c883e44c6a2300e369bd40142
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 N123b16cbec324dc7bc823da6c254fe47 rdf:first sg:person.011373745067.01
28 rdf:rest Ne799d1578aa444a6a1786f9d8b3fc204
29 N3f5418d88dd7493589feaf925d321da4 schema:volumeNumber 47
30 rdf:type schema:PublicationVolume
31 N6c641ae3854d4e96878b08878edbd863 schema:name readcube_id
32 schema:value 6c6af4ef2b2d4142210c14c8aa2c5543a1cd976e9ce94ea3af91ae2aaa7bde21
33 rdf:type schema:PropertyValue
34 N808640f43d824269b881fc732aa4e651 schema:name dimensions_id
35 schema:value pub.1022756805
36 rdf:type schema:PropertyValue
37 N8129f71658eb4301b0fc525836b90242 schema:name doi
38 schema:value 10.1007/s00453-006-1211-4
39 rdf:type schema:PropertyValue
40 Nb5371b566d8e465cbcdfe1fc7cc4e62f rdf:first sg:person.012347751512.96
41 rdf:rest N123b16cbec324dc7bc823da6c254fe47
42 Ne223e86c883e44c6a2300e369bd40142 schema:name Springer Nature - SN SciGraph project
43 rdf:type schema:Organization
44 Ne2fb1c5ea4ad42f3afa626ead4a3bfca schema:issueNumber 1
45 rdf:type schema:PublicationIssue
46 Ne799d1578aa444a6a1786f9d8b3fc204 rdf:first sg:person.015252425053.08
47 rdf:rest rdf:nil
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)


...