论文部分内容阅读
研究同速机上的负载平衡博弈中的近似强均衡问题．一个纳什均衡是一种对单方面的背离有弹性的策略组合．一个强纳什均衡是一种对任何联盟的合作背离都稳定的策略组合．对于该问题的一个排序，一个工件一次背离的改进率定义为它背离前和背离后的成本的比率．如果不存在这样一个联盟，使得联盟中的每个成员都能从联盟的合作背离中获得大于p的改进率，那么这个纳什均衡就称为p-近似强均衡（p≥1）．对于到8台机器为止的负载平衡博弈，证明了任何纳什均衡都是5／4-近似强均衡，这个界是紧的．进一步的，在m（m≥9）台机器上.