
In this work, we consider an interesting variant of the well-studied KP model [KP99] for selfish routing that reflects some influence from the much older Wardrop [War52]. In the new model, user traffics are still unsplittable, while social cost is now the expectation of the sum, over all links, of a certain polynomial evaluated at the total latency incurred by all users choosing the link; we call it polynomial social cost. The polynomials that we consider have non-negative coefficients. We are interested in evaluating Nash equilibria in this model, and we use the Price of Anarchy as our evaluation measure. We prove the Fully Mixed Nash Equilibrium Conjecture for identical users and two links, and establish an approximate version of the conjecture for arbitrary many links. Moreover, we give upper bounds on the Price of Anarchy.
Polynomial price of anarchy, Combinatorial mathematics, Telecommunication links, selfish routing, Nash equilibria, Polynomials, polynomial price of anarchy, Theoretical Computer Science, Upper Bound, KP-model, Social cost, Games involving graphs, Non negatives, fully mixed Nash Equilibrium, Price of anarchy, Mathematical models, price of anarchy, Network design and communication in computer systems, Telecommunication networks, User traffics, Combinatorics in computer science, 004, Costs, Telecommunication traffic, Selfish routing, Evaluation measures, Computer Science(all)
Polynomial price of anarchy, Combinatorial mathematics, Telecommunication links, selfish routing, Nash equilibria, Polynomials, polynomial price of anarchy, Theoretical Computer Science, Upper Bound, KP-model, Social cost, Games involving graphs, Non negatives, fully mixed Nash Equilibrium, Price of anarchy, Mathematical models, price of anarchy, Network design and communication in computer systems, Telecommunication networks, User traffics, Combinatorics in computer science, 004, Costs, Telecommunication traffic, Selfish routing, Evaluation measures, Computer Science(all)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 25 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
