License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.05011.19
URN: urn:nbn:de:0030-drops-2005
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2005/200/
Go to the corresponding Portal

Gairing, Martin ; Lücking, Thomas ; Mavronicolas, Marios ; Monien, Burkhard

The Price of Anarchy for Polynomial Social Cost

pdf-format:
05011.GairingMartin.ExtAbstract.pdf (0.2 MB)

Abstract

In this work, we consider an interesting variant
of the well-studied KP model [KP99] for selfish
routing that reflects some influence from the much
older Wardrop [War52]. In the new model, user
traffics are still unsplittable, while social cost
is now the expectation of the sum, over all links,
of a certain polynomial evaluated at the total
latency incurred by all users choosing the link;
we call it polynomial social cost. The polynomials
that we consider have non-negative coefficients.
We are interested in evaluating Nash equilibria in
this model, and we use the Price of Anarchy as our
evaluation measure. We prove the Fully Mixed Nash
Equilibrium Conjecture for identical users and two
links, and establish an approximate version of the
conjecture for arbitrary many links. Moreover, we
give upper bounds on the Price of Anarchy.

BibTeX - Entry

@InProceedings{gairing_et_al:DagSemProc.05011.19,
  author =	{Gairing, Martin and L\"{u}cking, Thomas and Mavronicolas, Marios and Monien, Burkhard},
  title =	{{The Price of Anarchy for Polynomial Social Cost}},
  booktitle =	{Computing and Markets},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5011},
  editor =	{Daniel Lehmann and Rudolf M\"{u}ller and Tuomas Sandholm},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2005/200},
  URN =		{urn:nbn:de:0030-drops-2005},
  doi =		{10.4230/DagSemProc.05011.19},
  annote =	{Keywords: selfish routing , KP-model , price of anarchy , fully mixed Nash Equilibrium}
}

Keywords: selfish routing , KP-model , price of anarchy , fully mixed Nash Equilibrium
Collection: 05011 - Computing and Markets
Issue Date: 2005
Date of publication: 19.07.2005

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI