Show simple item record

dc.contributor.authorGairing, M.en
dc.contributor.authorLücking, T.en
dc.contributor.authorMavronicolas, Mariosen
dc.contributor.authorMonien, Burkharden
dc.creatorGairing, M.en
dc.creatorLücking, T.en
dc.creatorMavronicolas, Mariosen
dc.creatorMonien, Burkharden
dc.description.abstractIn this work, we consider an interesting variant of the well studied KP model for selfish routing on parallel links, which reflects some influence from the much older Wardrop model [J.G. Wardrop, Some theoretical aspects of road traffic research, Proc. Inst. of Civil Eng. Part II 1 (1956) 325-378]. In the new model, user traffics are still unsplittable and links are identical. Social cost is now the expectation of the sum, over all links, of latency costsen
dc.description.abstracteach latency cost is modeled as a certain polynomial latency cost function evaluated at the latency incurred by all users choosing the link. The resulting social cost is called polynomial social cost, or monomial social cost when the latency cost function is a monomial. All considered polynomials are of degree d, where d ≥ 2, and have non-negative coefficients. We are interested in evaluating Nash equilibria in this model, and we use the monomial price of anarchy (MPoA) and the polynomial price of anarchy (PPoA) as our evaluation measures. Through establishing some remarkable relations of these costs and measures to some classical combinatorial numbers such as the Stirling numbers of the second kind and the Bell numbers, we obtain a multitude of results:• For the special case of identical users:{ring operator}The fully mixed Nash equilibrium, where all probabilities are strictly positive, maximizes polynomial social cost.{ring operator}The MPoA is no more than Bd, the Bell number of order d.This immediately implies that the PPoA is no more than ∑1 ≤ t ≤ d Bt.For the special case of two links, the MPoA is no more than 2d - 2 (1 + (1 / n)d - 1), and this bound is tight for n = 2.• The MPoA is exactly((2d - 1)d / (d - 1) (2d - 2)d - 1) ((d - 1) / d)d for pure Nash equilibria. This immediately implies that the PPoA is no more than ∑2 ≤ t ≤ d ((2t - 1)t / (t - 1) (2t - 2)t - 1) ((t - 1) / t)t. © 2006 Elsevier B.V. All rights reserved.en
dc.sourceTheoretical Computer Scienceen
dc.subjectMathematical modelsen
dc.subjectTelecommunication linksen
dc.subjectPrice of anarchyen
dc.subjectTelecommunication trafficen
dc.subjectCombinatorial mathematicsen
dc.subjectSelfish routingen
dc.subjectPolynomial price of anarchyen
dc.titleThe price of anarchy for polynomial social costen
dc.description.endingpage135 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied SciencesΤμήμα Πληροφορικής / Department of Computer Science
dc.description.notes<p>Cited By :12</p>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