Symmetry in network congestion games: Pure equilibria and anarchy cost
| dc.contributor.author | Fotakis, D. | en |
| dc.contributor.author | Kontogiannis, S. | en |
| dc.contributor.author | Spirakis, P. | en |
| dc.date.accessioned | 2015-11-24T17:01:16Z | |
| dc.date.available | 2015-11-24T17:01:16Z | |
| dc.identifier.issn | 0302-9743 | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/10899 | |
| dc.rights | Default Licence | - |
| dc.subject | worst-case equilibria | en |
| dc.subject | nash equilibria | en |
| dc.subject | selfish | en |
| dc.subject | complexity | en |
| dc.subject | bounds | en |
| dc.title | Symmetry in network congestion games: Pure equilibria and anarchy cost | en |
| heal.abstract | We study computational and coordination efficiency issues of Nash equilibria in symmetric network congestion games. We first propose a simple and natural greedy method that computes a pure Nash equilibrium with respect to traffic congestion in a network. In this algorithm each user plays only once and allocates her traffic to a path selected via a shortest path computation. We then show that this algorithm works for series-parallel networks when users are identical or when users are of varying demands but have the same best response strategy for any initial network traffic. We also give constructions where the algorithm fails if either the above condition is violated (even for series-parallel networks) or the network is not series-parallel (even for identical users). Thus, we essentially indicate the limits of the applicability of this greedy approach. We also study the price of anarchy for the objective of maximum latency. We prove that for any network of m uniformly related links and for identical users, the price of anarchy is circle minus((logm)/(loglogm)). | en |
| heal.access | campus | - |
| heal.fullTextAvailability | TRUE | - |
| heal.journalName | Approximation and Online Algorithms | en |
| heal.journalType | peer reviewed | - |
| heal.language | en | - |
| heal.publicationDate | 2006 | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.type | journalArticle | - |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.type.en | Journal article | en |
Αρχεία
Φάκελος/Πακέτο αδειών
1 - 1 of 1
Φόρτωση...
- Ονομα:
- license.txt
- Μέγεθος:
- 1.74 KB
- Μορφότυπο:
- Item-specific license agreed upon to submission
- Περιγραφή: