排序问题是一类重要的组合最优化问题,它是利用一些处理机、机器或资源,最优的完成一批给定的任务或作业。博弈排序是排序问题的重要组成部分,是传统的排序论与博弈论的交叉。　　在博弈排序问题中我们考虑将n个工件放在m台机器上加工,每个“局中人”选择一台机器来加工其工件,使其目标函数值达到最优。纳什均衡是一种博弈的解的概念,一个博弈中包含两个或更多个局中人，假设每个局中人了解其他局中人的策略并且每个局中人不会因为单方面改变他自己的策略而获益。一般来说，纯策略纳什均衡不一定存在但是混合策略纳什均衡是普遍存在的。本文我们只探讨纯策略纳什均衡。　　在排序模型中，每个工件的加工时间是Cj,工件的社会效用定义为-Cj。没有一个中央协调，每个工件选择能使自己尽早完工的机器,而无视中心目标的性能,这可能会导致混乱。为了解决这一冲突,每台机器提前宣布自己的局部排序规则,依此规则安排在该机器上加工的工件.例如, SPT规则,被安排到这台机器上的工件按加工时间的非减序加工。如果排序规则仅仅依赖于该机器工件的加工时间,称作强局部规则。本文主要研究了机器在EDD局部排序规则下恒速机上目标函数分别为最大误工、总误工、误工任务数以及在LW局部排序规则下目标函数为加权总误工任务数的博弈排序问题的纳什均衡状态。　　本文结构安排如下：　　第一章为绪论,主要介绍了排序问题、协调机制、博弈论和纳什均衡问题、博弈排序问题的产生和它的主要内容以及国内外研究现状。　　第二章主要介绍了m台恒速机上，每台机器的局部排序规则为EDD，目标函数为最大误工和总误工的博弈排序问题。在纳什均衡中,在每个工件的策略都不改变的情况下,任何一个工件都不能通过单方面的改变自己的策略来降低它的成本.但是纳什均衡不一定是最优的,实际上还常常与最优值存在很大差距。我们通常用POA（the price of anarchy）来衡量纳什均衡的稳定性.在本文中由于目标函数的最优值可能是0,因此我们又定义了APOA(absolute price of anarchy)。在本章中我们分别求出了目标函数为最大误工与总误工的博弈排序问题APOA的上界。　　第三章首先介绍了两台恒速机上,每台机器的局部规则为EDD，目标函数为误工任务数的博弈排序问题；每台机器的局部规则为LW，目标函数为误工任务数的博弈排序问题.然后我们将机器环境扩展到m台恒速机上,分别求出在各自排序规则下上述问题纳什均衡状态下APOA的值。