1 Search Results for "Lücking, Thomas"

Document
DOI: 10.4230/DagSemProc.05011.19
The Price of Anarchy for Polynomial Social Cost

Authors: Martin Gairing, Thomas Lücking, Marios Mavronicolas, and Burkhard Monien

Published in: Dagstuhl Seminar Proceedings, Volume 5011, Computing and Markets (2005)

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.
Cite as

Martin Gairing, Thomas Lücking, Marios Mavronicolas, and Burkhard Monien. The Price of Anarchy for Polynomial Social Cost. In Computing and Markets. Dagstuhl Seminar Proceedings, Volume 5011, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05011.19},
  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}
}
  • Refine by Author
  • 1 Gairing, Martin
  • 1 Lücking, Thomas
  • 1 Mavronicolas, Marios
  • 1 Monien, Burkhard

  • Refine by Classification

  • Refine by Keyword
  • 1 KP-model
  • 1 fully mixed Nash Equilibrium
  • 1 price of anarchy
  • 1 selfish routing

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2005

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact