文章基本信息

标题：Competitive Packet Routing with Priority Lists
本地全文：下载
作者：Tobias Harks ; Britta Peis ; Daniel Schmand 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：58
页码：49:1-49:14
DOI：10.4230/LIPIcs.MFCS.2016.49
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：In competitive packet routing games, packets are routed selfishly through a network and scheduling policies at edges determine which packages are forwarded first if there is not enough capacity on an edge to forward all packages 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.
关键词：packet routing; Nash equilibrium; price of anarchy; priority policy; complexity