Show simple item record

dc.contributor.authorMavronicolas, Mariosen
dc.contributor.authorSpirakis, Paul G.en
dc.creatorMavronicolas, Mariosen
dc.creatorSpirakis, Paul G.en
dc.description.abstractWe study the problem of routing traffic through a congested network. We focus on the simplest case of a network consisting of m parallel links. We assume a collection of n network usersen
dc.description.abstracteach user employs a mixed strategy, which is a probability distribution over links, to control the shipping of its own assigned traffic. Given a capacity for each link specifying the rate at which the link processes traffic, the objective is to route traffic so that the maximum (over all links) latency is minimized. We consider both uniform and arbitrary link capacities. How much decrease in global performace is necessary due to the absence of some central authority to regulate network traffic and implement an optimal assignment of traffic to links? We investigate this fundamental question in the context of Nash equilibria for such a system, where each network user selfishly routes its traffic only on those links available to it that minimize its expected latency cost, given the network congestion caused by the other users. We use the Coordination Ratio, originally defined by Koutsoupias and Papadimitriou, as a measure of the cost of lack of coordination among the usersen
dc.description.abstractroughly speaking, the Coordination Ratio is the ratio of the expectation of the maximum (over all links) latency in the worst possible Nash equilibrium, over the least possible maximum latency had global regulation been available. Our chief instrument is a set of combinatorial Minimum Expected Latency Cost Equations, one per user, that characterize the Nash equilibria of this system. These are linear equations in the minimum expected latency costs, involving the user traffics, the link capacities, and the routing pattern determined by the mixed strategies. In turn, we solve these equations in the case of fully mixed strategies, where each user assigns its traffic with a strictly positive probability to every link, to derive the first existence and uniqueness results for fully mixed Nash equilibria in this setting. Through a thorough analysis and characterization of fully mixed Nash equilibria, we obtain tight upper bounds of no worse than O(ln n/ln ln n) on the Coordination Ratio for (i) the case of uniform capacities and arbitrary traffics and (ii) the case of arbitrary capacities and identical traffics. © Springer 2007.en
dc.sourceAlgorithmica (New York)en
dc.subjectCost effectivenessen
dc.subjectProbability distributionsen
dc.subjectChannel capacityen
dc.subjectTelecommunication linksen
dc.subjectTelecommunication trafficen
dc.subjectNetwork routingen
dc.subjectUser interfacesen
dc.subjectNash equilibriaen
dc.subjectSelfish routingen
dc.subjectCoordination ratioen
dc.subjectFully mixed Nash equiliumen
dc.subjectLatency Cost Equationsen
dc.titleThe price of selfish routingen
dc.description.endingpage126 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied SciencesΤμήμα Πληροφορικής / Department of Computer Science
dc.description.notes<p>Cited By :41</p>en
dc.source.abbreviationAlgorithmica (New York)en
dc.contributor.orcidSpirakis, Paul G. [0000-0001-5396-3749]

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record