Worst-Case Nash Equilibria in Restricted Routing
Pin-Yan Lu;Chang-Yuan Yu
【期刊名称】《计算机科学技术学报（英文版）》 【年(卷),期】2012(027)004
【摘要】We study the network routing problem with restricted and related links.There
are
parallel
links
with
possibly
different
speeds,between a source and a sink.Also there are users,and each user has a traffic of some weight to assign to one of the links from a subset of all the links,named his/her allowable set.The users choosing the same link suffer the same delay,which is equal to the total weight assigned to that link over its speed.A state of the system is called a Nash equilibrium if no user can decrease his/her delay by unilaterally changing his/her link.To measure the performance degradation of the system due to the selfish behavior of all the users,Koutsoupias and Papadimitriou proposed the notion Price of Anarchy (denoted by PoA),which is the ratio of the maximum delay in the worst-case Nash equilibrium and in an optimal solution.The PoA for this restricted related model has been studied,and a linear lower bound was obtained.However in their bad instance,some users can only use extremely slow links.This is a little artificial and unlikely to appear in a real world.So in order to better understand this model,we introduce a parameter for the system,and prove a better Price of Anarchy in terms
of the parameter.We also show an important application of our result in coordination mechanism design for task scheduling game.We propose a new coordination mechanism,Group-Makespan,for unrelated selfish task scheduling game with improved price of anarchy. 【总页数】8页(710-717) 【关键词】
【作者】Pin-Yan Lu;Chang-Yuan Yu
【作者单位】Microsoft Research Asia, Beijing 100080, China;Baidu.Inc, Beijing 100085, China 【正文语种】中文 【中图分类】 【文献来源】
https://www.zhangqiaokeyan.com/academic-journal-cn_journal-computer-science-technology_thesis/0201241226679.html 【相关文献】
1.Hybrid Routing by Joint Optimization of Per-Flow Routing and Tag-Based Routing in Software-Defined Networks [J], Gongming Zhao; Liusheng Huang; Ziqiang Li; Hongli Xu
2.Effective local dynamic routing strategy for air route networks [J], Wu Wenjun; Zhao Lingxi
3.Overall Planning of Tour Routes: A Case Study of Tour Route Planning in Panzhihua City [J], HUAN Shaojun; NI Yan
4.A Study on Selecting the Shortest Routes by Voronoi Diagram in Route Networks of GIS [J],
5.Comparative Study on Optical Properties and Scratch Resistance of Nanocomposite Coatings Incorporated with Flame Spray Pyrolyzed Silica Modified via in-situ Route and ex-situ Route [J], Yun Wang; Ling Zhang; Yanjie Hu; Chunzhong Li
以上内容为文献基本信息，获取文献全文请下载
Worst-Case Nash Equilibria in Restricted Routing
