Competitive Packet Routing with Priority Lists

In competitive packet routing games, the packets are routed selfishly through a network and scheduling policies at edges determine which packets are forwarded first if there is not enough capacity on an edge to forward all packets at once. We analyze the impact of priority lists on the worst-case qu...

Full description

Saved in:
Bibliographic Details
Published in:ACM transactions on economics and computation 2018-03, Vol.6 (1), p.1-26
Main Authors: Harks, Tobias, Peis, Britta, Schmand, Daniel, Tauer, Bjoern, Koch, Laura Vargas
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In competitive packet routing games, the packets are routed selfishly through a network and scheduling policies at edges determine which packets are forwarded first if there is not enough capacity on an edge to forward all packets at once. We analyze the impact of priority lists on the worst-case quality of pure Nash equilibria. A priority list is an ordered list of players that may or may not depend on the edge. Whenever the number of packets entering an edge exceeds the inflow capacity, packets are processed in list order. We derive several new bounds on the price of anarchy and stability for global and local priority policies. We also consider the question of the complexity of computing an optimal priority list. It turns out that even for very restricted cases, i.e., for routing on a tree, the computation of an optimal priority list is APX-hard.
ISSN:2167-8375
2167-8383
DOI:10.1145/3184137