Show simple item record

dc.contributor.authorGairing, M.en
dc.contributor.authorLücking, T.en
dc.contributor.authorMavronicolas, Mariosen
dc.contributor.authorMonien, Burkharden
dc.contributor.authorRode, M.en
dc.creatorGairing, M.en
dc.creatorLücking, T.en
dc.creatorMavronicolas, Mariosen
dc.creatorMonien, Burkharden
dc.creatorRode, M.en
dc.description.abstractWe study Nash equilibria in a discrete routing game that combines features of the two most famous models for non-cooperative routing, the KP model [16] and the Wardrop model [27]. In our model, users share parallel links. A user strategy can be any probability distribution over the set of links. Each user tries to minimize its expected latency, where the latency on a link is described by an arbitrary nondecreasing, convex function. The social cost is defined as the sum of the users' expected latencies. To the best of our knowledge, this is the first time that mixed Nash equilibria for routing games have been studied in combination with non-linear latency functions. As our main result, we show that for identical users the social cost of any Nash equilibrium is bounded by the social cost of the fully mixed Nash equilibrium. A Nash equilibrium is called fully mixed if each user chooses each link with non-zero probability. We present a complete characterization of the instances for which a fully mixed Nash equilibrium exists, and prove that (in case of its existence) it is unique. Moreover, we give bounds on the coordination ratio and show that several results for the Wardrop model can be carried over to our discrete model. © Springer-Verlag Berlin Heidelberg 2004.en
dc.sourceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en
dc.subjectGame theoryen
dc.subjectTelecommunication networksen
dc.subjectProbability distributionsen
dc.subjectComputation theoryen
dc.subjectNon-zero probabilityen
dc.subjectConvex functionsen
dc.subjectNash equilibriaen
dc.subjectLatency functionen
dc.subjectCoordination ratioen
dc.subjectDiscrete modelingen
dc.subjectUser strategiesen
dc.titleNash equilibria in discrete routing games with convex latency functionsen
dc.description.endingpage657 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied SciencesΤμήμα Πληροφορικής / Department of Computer Science
dc.description.notes<p>Cited By :37</p>en
dc.source.abbreviationLect. Notes Comput. Sci.en

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record