Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/11003Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Fotakis, D. | en |
| dc.contributor.author | Kontogiannis, S. | en |
| dc.contributor.author | Koutsoupias, E. | en |
| dc.contributor.author | Mavronicolas, M. | en |
| dc.contributor.author | Spirakis, P. | en |
| dc.date.accessioned | 2015-11-24T17:01:57Z | - |
| dc.date.available | 2015-11-24T17:01:57Z | - |
| dc.identifier.issn | 0304-3975 | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/11003 | - |
| dc.rights | Default Licence | - |
| dc.subject | algorithmic game theory | en |
| dc.subject | selfish routing | en |
| dc.subject | nash equilibrium | en |
| dc.subject | worst-case equilibria | en |
| dc.subject | price | en |
| dc.subject | existence | en |
| dc.subject | anarchy | en |
| dc.subject | model | en |
| dc.subject | cost | en |
| dc.title | The structure and complexity of Nash equilibria for a selfish routing game | en |
| heal.type | journalArticle | - |
| heal.type.en | Journal article | en |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.identifier.primary | DOI 10.1016/j.tcs.2008.01.004 | - |
| heal.language | en | - |
| heal.access | campus | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.publicationDate | 2009 | - |
| heal.abstract | In this work, we study the combinatorial structure and the computational complexity of Nash equilibria for a certain game that models selfish routing over a network consisting of m parallel links. We assume a collection of it users, each employing a mixed strategy, which is a probability distribution over links, to control the routing Of her own traffic. In a Nosh equilibrium, each user selfishly routes her traffic on those links that minimize her expected latency cost, given the network congestion caused by the other users. The social cost of a Nash equilibrium is the expectation, over all random choices of the users, of the maximum, over all links, latency through a link. We embark on a systematic study of several algorithmic problems related to the computation of Nash equilibria for the selfish routing game we consider. In a nutshell, these problems relate to deciding the existence of a pure Nash equilibrium, constructing a Nash equilibrium, constructing the pure Nash equilibria of minimum and maximum social cost, and Computing the Social Cost of a given mixed Nash equilibrium. Our work provides a comprehensive collection of efficient algorithms, hardness results, and structural results for these algorithmic problems. Our results span and contrast a wide range of assumptions on the syntax of the Nash equilibria and on the parameters of the system. (C) 2008 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-2009-The structure and co.pdf | 975.11 kB | Adobe PDF | View/Open Request a copy |
This item is licensed under a Creative Commons License
