View in EDS PDF Full Text

Approximate Equilibria and Ball Fusion.

Saved in:
Bibliographic Details
Title: Approximate Equilibria and Ball Fusion.
Authors: Koutsoupias, Elias1,2 elias@di.uoa.gr, Mavronicolas, Marios3 mavronic@ucy.ac.cy, Spirakis, Paul4,5 spirakis@cti.gr
Source: Theory of Computing Systems. Nov/Dec2003, Vol. 36 Issue 6, p683-693. 11p.
Subjects: Computer peripherals, Network hubs, Equilibrium, Distribution (Probability theory), Mathematical functions, Computer systems
Abstract: We consider selfish routing over a network consisting of m parallel links through which $n$ selfish users route their traffic trying to minimize their own expected latency. We study the class of mixed strategies in which the expected latency through each link is at most a constant multiple of the optimum maximum latency had global regulation been available. For the case of uniform links it is known that all Nash equilibria belong to this class of strategies. We are interested in bounding the coordination ratio (or price of anarchy) of these strategies defined as the worst-case ratio of the maximum (over all links) expected latency over the optimum maximum latency. The load balancing aspect of the problem immediately implies a lower bound Ω(ln m ln ln m) of the coordination ratio. We give a tight (up to a multiplicative constant) upper bound. To show the upper bound, we analyze a variant of the classical balls and bins problem, in which balls with arbitrary weights are placed into bins according to arbitrary probability distributions. At the heart of our approach is a new probabilistic tool that we call ball fusion; this tool is used to reduce the variant of the problem where balls bear weights to the classical version (with no weights). Ball fusion applies to more general settings such as links with arbitrary capacities and other latency functions. [ABSTRACT FROM AUTHOR]
Copyright of Theory of Computing Systems is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Links:
  – Type: pdflink
Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 11627346
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Approximate Equilibria and Ball Fusion.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Koutsoupias%2C+Elias%22">Koutsoupias, Elias</searchLink><relatesTo>1,2</relatesTo><i> elias@di.uoa.gr</i><br /><searchLink fieldCode="AR" term="%22Mavronicolas%2C+Marios%22">Mavronicolas, Marios</searchLink><relatesTo>3</relatesTo><i> mavronic@ucy.ac.cy</i><br /><searchLink fieldCode="AR" term="%22Spirakis%2C+Paul%22">Spirakis, Paul</searchLink><relatesTo>4,5</relatesTo><i> spirakis@cti.gr</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Theory+of+Computing+Systems%22">Theory of Computing Systems</searchLink>. Nov/Dec2003, Vol. 36 Issue 6, p683-693. 11p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Computer+peripherals%22">Computer peripherals</searchLink><br /><searchLink fieldCode="DE" term="%22Network+hubs%22">Network hubs</searchLink><br /><searchLink fieldCode="DE" term="%22Equilibrium%22">Equilibrium</searchLink><br /><searchLink fieldCode="DE" term="%22Distribution+%28Probability+theory%29%22">Distribution (Probability theory)</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+functions%22">Mathematical functions</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+systems%22">Computer systems</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: We consider selfish routing over a network consisting of m parallel links through which $n$ selfish users route their traffic trying to minimize their own expected latency. We study the class of mixed strategies in which the expected latency through each link is at most a constant multiple of the optimum maximum latency had global regulation been available. For the case of uniform links it is known that all Nash equilibria belong to this class of strategies. We are interested in bounding the coordination ratio (or price of anarchy) of these strategies defined as the worst-case ratio of the maximum (over all links) expected latency over the optimum maximum latency. The load balancing aspect of the problem immediately implies a lower bound Ω(ln m ln ln m) of the coordination ratio. We give a tight (up to a multiplicative constant) upper bound. To show the upper bound, we analyze a variant of the classical balls and bins problem, in which balls with arbitrary weights are placed into bins according to arbitrary probability distributions. At the heart of our approach is a new probabilistic tool that we call ball fusion; this tool is used to reduce the variant of the problem where balls bear weights to the classical version (with no weights). Ball fusion applies to more general settings such as links with arbitrary capacities and other latency functions. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Theory of Computing Systems is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=11627346
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1007/s00224-003-1131-5
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 11
        StartPage: 683
    Subjects:
      – SubjectFull: Computer peripherals
        Type: general
      – SubjectFull: Network hubs
        Type: general
      – SubjectFull: Equilibrium
        Type: general
      – SubjectFull: Distribution (Probability theory)
        Type: general
      – SubjectFull: Mathematical functions
        Type: general
      – SubjectFull: Computer systems
        Type: general
    Titles:
      – TitleFull: Approximate Equilibria and Ball Fusion.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Koutsoupias, Elias
      – PersonEntity:
          Name:
            NameFull: Mavronicolas, Marios
      – PersonEntity:
          Name:
            NameFull: Spirakis, Paul
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 11
              Text: Nov/Dec2003
              Type: published
              Y: 2003
          Identifiers:
            – Type: issn-print
              Value: 14324350
          Numbering:
            – Type: volume
              Value: 36
            – Type: issue
              Value: 6
          Titles:
            – TitleFull: Theory of Computing Systems
              Type: main
ResultId 1