排序,也称为调度,是组合优化理论中的一个重要分支。对于传统的排序问题,给定工件集和机器集,为了达到某个目标值,决策者们通常考虑如何将工件最好的安排到机器上进行加工。这个问题不仅在理论上具有很高的研究价值,在现实中也拥有广泛的应用背景。本文主要研究的是博弈排序问题中无秩序代价,即在排序问题中考虑博弈理论。在博弈排序问题中,没有中央决策者的存在,每个工件被看作是自私的博弈者或每个工件为一个代理所拥有,他们追求个体的最大利益;工件的策略集为可选择的机器集。工件的完工时间的相反数作为工件的效用函数,以所有工件的完工时间和(社会成本)为该问题的目标函数。由于自由博弈产生的纳什均衡解不一定是系统的最优解,因此,纳什均衡解与最优解之间的差异的大小是我们所要讨论的问题。常用无秩序代价(PoA)来刻画纳什均衡解和最优解之间的差距。特别地,PoA值越接近于1说明纳什均衡解对应的目标函数值与最优值越接近。本文的第一章介绍了排序问题的背景知识、基本概念和定义。第二章研究了协调机制为LPT的2台同类机目标函数为所有工件的完工时间和的博弈排序问题。我们证明了在LPT的协调机制下,各代理之间的自由博弈达到的稳定状态为纳什均衡并证得PoA的上界为(?)。此外,通过构建该问题的一个实例,我们给出了该问题PoA的一个下界3。在第三章中,我们将第二章的问题进行了推广,研究了 m台同类机的博弈排序问题。证得PoA的上界为(?)。类似于第二章下界证明,通过构建该问题的一个实例求得该问题PoA的一个下界为3。