Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/10848Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Fotakis, D. | en |
| dc.contributor.author | Kontogiannis, S. | en |
| dc.contributor.author | Spirakis, P. | en |
| dc.date.accessioned | 2015-11-24T17:00:58Z | - |
| dc.date.available | 2015-11-24T17:00:58Z | - |
| dc.identifier.issn | 0304-3975 | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/10848 | - |
| dc.rights | Default Licence | - |
| dc.subject | pure nash equilibria | en |
| dc.subject | network congestion games | en |
| dc.subject | unsplittable flows | en |
| dc.subject | price of anarchy | en |
| dc.subject | quadratic programming | en |
| dc.subject | games | en |
| dc.title | Selfish unsplittable flows | en |
| heal.type | journalArticle | - |
| heal.type.en | Journal article | en |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.identifier.primary | DOI 10.1016/j.tcs.2005.09.024 | - |
| heal.language | en | - |
| heal.access | campus | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.publicationDate | 2005 | - |
| heal.abstract | What is the price of anarchy when unsplittable demands are routed selfishly in general networks with load-dependent edge delays? Motivated by this question we generalize the model of Koutsoupias and Papadimitriou (Worst-case equilibria, in: Proc. of the 16th Annual Symp. on Theoretical Aspects of Computer Science (STACS '99), Lecture Notes in Computer Science, Vol. 1563, Springer, Berlin, 1999, pp. 404-413) to the case of weighted congestion games. We show that varying demands of users crucially affect the nature of these games, which are no longer isomorphic to exact potential games, even for very simple instances. Indeed we construct examples where even a single-commodity (weighted) network congestion game may have no pure Nash equilibrium. On the other hand, we prove that any weighted network congestion game with linear edge delays admits a pure Nash equilibrium that can be found in pseudo-polynomial time. Finally, we consider the family of e-layered networks and give a surprising answer to the question above: the price of anarchy of any weighted congestion game in a e-layered network with in edges and edge delays equal to the loads is Theta(log m/ log log m). (c) 2005 Elsevier B.V. All rights reserved. | en |
| heal.journalName | Theoretical Computer Science | en |
| heal.journalType | peer reviewed | - |
| heal.fullTextAvailability | TRUE | - |
| Appears in Collections: | Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά) | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Fotakis-2005-Selfish unsplittable.pdf | 271.79 kB | Adobe PDF | View/Open Request a copy |
This item is licensed under a Creative Commons License
