在平行机博弈排序中的近似强纳什均衡问题

摘要

本文研究的是在平行机博弈排序模型中的近似的强纳什均衡的问题。具体的这里所说的平行机,是指一类最基本,最重要的平行机模型——同速机。在平行机(同速机)博弈排序模型中,每一个工件(客户)都要求自主选择机器(服务器)中的一个来加工它自己,这样每个工件的目标就是希望能极小化它自己的成本。在这里它的成本是指它所选择的那台机器的总完工时间(workload)的函数。显然,一个已经选择好机器的工件如果发现它改选其它的某个机器会使自己的成本降低的话,它会自主的改变自己原来的选择。而每个工件的选择会影响到别的工件的成本。
　　一个纳什均衡是一个工件的排序状态(工件的策略组合)。其中工件的策略是指这个工件选择哪一台机器来加工它自己,而当每一个工件都给出一个策略以后,就得到了一个工件的策略组合,即一个工件的排序状态。作为一个纳什均衡,这个工件的策略组合必须满足以下条件:就是在其它所有工件的策略都不变的情况下,任何一个工件如果单方面的改变自己的策略,那么它自己的成本不会变的比原来更好。显然纳什均衡是一个比较稳定的状态。在所讨论的这个博弈排序模型中,要想要找到一个纳什均衡是十分简单的,然而在一个纳什均衡中,如果有若干个工件彼此联络从而形成了一个联盟,那么这个联盟的一次联合改变策略的行动就有可能打破原来的稳定状态。定义一个强纳什均衡是一个工件的排序状态(工件的策略组合),它满足:对于任何一个工件的联盟(也包括单个工件形成的联盟),在联盟外工件都不改变策略的情况下,联盟内工件都改变自己的策略,那么不会出现联盟中的每个工件都受益(严格降低了自己的成本)的情况。虽然强纳什均衡有很好的稳定性,但一般来说它是难以实现的,所以定义近似强纳什均衡的概念。
　　在一个平行机博弈排序问题中,给出任何一个工件的排序状态(工件的策略组合),定义一个工件一次背离(改变策略)的改进率为:它在背离前与背离后的自己的成本的比值。一个工件的改进率反映出了这个工件进行这次背离行动的动力。一个纳什均衡点被称为ρ-近似强纳什均衡(ρ≥1),如果它满足:任何一个工件的联盟都不能通过该联盟的一次单独联合背离而使联盟内的每一个工件都获得一个严格大于ρ的改进率。显然ρ越小则原来的排序就越稳定,当ρ=1时原来的排序就是强纳什均衡点。
　　在本文中,证明了对于平行机博弈排序问题,当机器个数不超过8台时,任何一个纳什均衡点都是一个5/4近似强纳什均衡,并且这个界是紧的。更进一步的,当机器个数为 m(m≥9)台时,任何一个纳什均衡点都是一个(32–2m-32(m-1)2)近似强纳什均衡。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 引 言

第二章 定义与预备工作

第一节 图论工具

第二节 K 星和猜想

第三章 一般近似性

第四章 不多于 8 台机器时的情况

第一节 5 台机器的情况

第二节 6 台机器的情况

第三节 7 台机器的情况

第四节 8 台机器的情况

第五章 总结评论

参考文献

在校期间发表的学术论文

致谢