两台平行机排序博弈问题的协调机制

排序理论是组合最优化理论的重要组成部分,如果在排序过程中有一个系统管理员来安排相应任务,那么往往会得到比较理想的解。但是,随着互联网的发展,在许多排序过程中由系统管理员来强加控制是不可行的,因为互联网的用户具有独立性和自利性,他们"自私"地追求自身的利益最优,而不在乎是否造成社会资源的浪费。若没有合理的资源使用机制,这种自利性往往会使结果与理论最优值偏差巨大。因此设计合理的机制以影响、引导独立和"自私"的用户的选择从而减少社会资源的浪费将具有重大的理论意义。本文针对如下排序博弈模型:具有2台平行机,工件是局中人,工件的策略是对机器的选择,工件的目标是最小化它的完工时间,全局目标是最小化最大完工时间,探讨SPT-LPT机制(SPT-LPT机制是指一台机器按工件加工时间的不减顺序排序,另一台机器按工件加工时间的不增顺序排序),首先研究了SPT-LPT机制下相应排序博弈问题的纳什均衡解的情况,其次证明了当工件数不小于4时,SPT-LPT机制下的无秩序代价为4/3。