Computing Nash Equilibria for Scheduling on Restricted Parallel Links
Computing Nash Equilibria for Scheduling on Restricted Parallel Links
复制标题
DOI：
10.1007/s00224-009-9191-9
复制
发表时间：
2004-06
影响因子：
0.5
通讯作者：
Martin Gairing;T. Lücking;M. Mavronicolas;B. Monien
中科院分区：
文献类型：
--
作者：
Martin Gairing;T. Lücking;M. Mavronicolas;B. Monien
在每个用户只能在某一组用户允许的链路中的一条链路上被路由的限制下，我们考虑了并行链路上的用户路由问题。因此，该问题等价于相应的约束调度问题--分配n个作业为并行机。在Anash均衡下，任何用户都不能通过单方面地从其允许的链路集中切换到另一条链路来改善自己的个人成本(延迟).对于相同的链路，我们给出了一个多项式时间算法，该算法可以从任意给定的分配中计算出一个不增加完工时间的纳什均衡.该算法通过将不可拆分的用户流量推送到由用户和链路构成的流网络中，逐步实现任务的转换。该算法借鉴了阻塞流的思想，并使用了类似于一般Preflow Pushalg算法的技术，在多项式时间内逼近了具有最优完工时间的调度。这导致了对于相同链路的改进的近似因子，其中1是最大的用户流量，并且对于相关链路的近似因子是大约2。
We consider the problem of routingnusersonmparallellinksunder the restriction that each user may only be routed on a link from a certain set ofallowed linksfor the user. So, this problem is equivalent to the correspondingly restricted scheduling problem of assigningnjobstomparallelmachines. In aNash equilibrium, no user may improve its ownIndividual Cost(latency) by unilaterally switching to another link from its set of allowed links.Foridentical links, we present, as our main result, a polynomial time algorithm to compute from any given assignment a Nash equilibrium with non-increasedmakespan. The algorithm gradually transforms the assignment by pushing the unsplittable usertrafficsthrough aflow network, which is constructed from the users and the links. The algorithm uses ideas fromblocking flows.Furthermore, we use techniques simular to those in the genericPreflowPushalgorithm to approximate in polynomial time a schedule with optimum makespan. This results to an improved approximation factor offoridentical links, wherew1is the largest user traffic, and to an approximation factor of 2 forrelated links.