dc.contributor.author | Fotakis, Dimitris A. | en |
dc.contributor.author | Kontogiannis, Spyros C. | en |
dc.contributor.author | Koutsoupias, Elias | en |
dc.contributor.author | Mavronicolas, Marios | en |
dc.contributor.author | Spirakis, Paul G. | en |
dc.creator | Fotakis, Dimitris A. | en |
dc.creator | Kontogiannis, Spyros C. | en |
dc.creator | Koutsoupias, Elias | en |
dc.creator | Mavronicolas, Marios | en |
dc.creator | Spirakis, Paul G. | en |
dc.date.accessioned | 2019-11-13T10:40:05Z | |
dc.date.available | 2019-11-13T10:40:05Z | |
dc.date.issued | 2002 | |
dc.identifier.issn | 0302-9743 | |
dc.identifier.uri | http://gnosis.library.ucy.ac.cy/handle/7/53948 | |
dc.description.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 n users, each employing a mixed strategy, which is a probability distribution over links, to control the routing of its own assigned traffic. In a Nash equilibrium, each user selfishly routes its traffic on those links that minimize its 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 Nash equilibrium, constructing a Nash equilibrium with given support characteristics, constructing the worst Nash equilibrium (the one with maximum social cost), constructing the best Nash equilibrium (the one with minimum social cost), or computing the social cost of a (given) Nash equilibrium. Our work provides a comprehensive collection of efficient algorithms, hardness results (both as NP-hardness and #P-completeness 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. © 2002 Springer-Verlag Berlin Heidelberg. | en |
dc.source | 29th International Colloquium on Automata, Languages, and Programming, ICALP 2002 | en |
dc.source.uri | https://www.scopus.com/inward/record.uri?eid=2-s2.0-84869168491&partnerID=40&md5=5ed523446fb6e03f4f3b2c466df05461 | |
dc.subject | Game theory | en |
dc.subject | Algorithms | en |
dc.subject | Telecommunication networks | en |
dc.subject | Automata theory | en |
dc.subject | Probability distributions | en |
dc.subject | Costs | en |
dc.subject | Hardness | en |
dc.subject | Systematic study | en |
dc.subject | Nash equilibria | en |
dc.subject | Mixed strategy | en |
dc.subject | Parallel links | en |
dc.subject | Selfish routing | en |
dc.subject | Social cost | en |
dc.subject | Algorithmic problems | en |
dc.subject | Combinatorial structures | en |
dc.subject | Hardness result | en |
dc.subject | Latency costs | en |
dc.subject | Network congestions | en |
dc.subject | Random choice | en |
dc.subject | NP-hardness | en |
dc.subject | P-completeness | en |
dc.title | The structure and complexity of Nash equilibria for a selfish routing game | en |
dc.type | info:eu-repo/semantics/article | |
dc.description.volume | 2380 LNCS | en |
dc.description.startingpage | 123 | |
dc.description.endingpage | 134 | |
dc.author.faculty | 002 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied Sciences | |
dc.author.department | Τμήμα Πληροφορικής / Department of Computer Science | |
dc.type.uhtype | Article | en |
dc.description.notes | <p>Sponsors: Unicaja (the first savings bank of Andalucia) | en |
dc.description.notes | University of Malaga | en |
dc.description.notes | Science and Technology Minister | en |
dc.description.notes | Malaga City Council | en |
dc.description.notes | Conference code: 93934 | en |
dc.description.notes | Cited By :142</p> | en |
dc.source.abbreviation | Lect. Notes Comput. Sci. | en |
dc.contributor.orcid | Kontogiannis, Spyros C. [0000-0002-8559-6418] | |
dc.contributor.orcid | Spirakis, Paul G. [0000-0001-5396-3749] | |
dc.gnosis.orcid | 0000-0002-8559-6418 | |
dc.gnosis.orcid | 0000-0001-5396-3749 | |