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.date.accessioned2019-11-13T10:40:06Z
dc.date.available2019-11-13T10:40:06Z
dc.date.issued2006
dc.identifier.urihttp://gnosis.library.ucy.ac.cy/handle/7/53955
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.source.urihttps://www.scopus.com/inward/record.uri?eid=2-s2.0-33750989087&doi=10.1016%2fj.tcs.2006.07.055&partnerID=40&md5=ee751afc637f15cc8b6473f60bd608e3
dc.subjectMathematical modelsen
dc.subjectTelecommunication linksen
dc.subjectPolynomialsen
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.typeinfo:eu-repo/semantics/article
dc.identifier.doi10.1016/j.tcs.2006.07.055
dc.description.volume369
dc.description.issue1-3
dc.description.startingpage116
dc.description.endingpage135
dc.author.faculty002 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied Sciences
dc.author.departmentΤμήμα Πληροφορικής / Department of Computer Science
dc.type.uhtypeArticleen
dc.description.notes<p>Cited By :12</p>en
dc.source.abbreviationTheor.Comput.Sci.en


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record