We use cookies to improve your experience with our site.

受限路由中的最坏均衡

Worst-Case Nash Equilibria in Restricted Routing

  • 摘要: 我们研究了受限及相关链接的路由问题。在一个源和汇之间有若干条不同速度的平行链接。每一个用户希望通过这些链接传输一定大小的数据。但是每个用户可以选择的链接是所有链接的一个子集。 每条链接的延迟等于该链接上的流量之和除以他的传输速度,这个延迟也是这条链接上所有用户的延迟。一个状态被称作是纳什均衡当且仅当每一个用户都不能通过单方面改变自己的选择来减小当前自己的延迟。 最坏均衡比的概念就是为了衡量这种用户的自利行为对整个个系统的影响,它被定义为最坏情况下一个均衡状态系统的延迟和最优系统延迟的比例。
    受限及相关链接的路由问题的最坏均衡比之前就研究过,可能达到线性的比例,非常差。 但是这种达到非常差的最坏均衡比的例子都非常的人为,不大可能在现实中出现。 为了更好的理解这个问题,我们对系统引入了一个参数,然后对于给定的参数来研究这个最坏均衡比。我们发现当系统满足比较好的参数条件的时候,最坏均衡比会比线性好很多。我们还找到我们这个结果在调度问题的协调机制设计方面的一个应用。 利用我们的结果,我们提出了一个更好的协调机制。

     

    Abstract: 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.

     

/

返回文章
返回