工件排序博弈：同类机上的资源分配与纳什均衡分析

本文主要探讨的是"两台带激活费用的同类机上的分配博弈"问题，发表于2012年的曲阜师范大学学报。研究焦点在于工件排序在两台速度不同的机器之间的资源分配，其中每台机器在被激活后会产生激活费用，这个费用与机器速度成正比。工件的决策不再是简单的寻找整体最优，而是追求个体费用最小化，因为它们的目标是自身的成本最小化，这符合纳什均衡（Nash Equilibrium）的概念，即在其他工件策略不变的情况下，任何工件改变策略都无法降低其自身费用。 工件的个体费用由其选择的机器的完工时间和在该机器上加工所承担的激活费用之和构成。整体费用则由两台机器中最长的完工时间和总激活费用决定。文章关注的是这种情况下，当工件作为博弈中的局中人，如何通过策略选择实现最有利的结果，以及与全局最优解的差距，即价格混乱度（Price of Anarchy，PoA）的分析。 作者首先基于所有工件加工时间总和的范围，提出了一种纳什均衡算法，证明了在这个范围内存在至少一种合理的工件排序方式。接着，作者证明了一个重要的结论，即在这样的资源配置博弈中，PoA小于1加上一个常数α，这意味着即使考虑到个体工件的最优选择，整体系统的效率损失也是有限的。 通过具体的例子，作者进一步证实了1+α是PoA的紧界，即PoA不会超过这个界限，这为理解此类资源分配问题提供了定量的理论支持。研究的背景和应用广泛，涉及资源分配问题在工件排序、无线电网络及运输系统等领域的实际意义，展示了博弈理论在运筹学中的重要作用，特别是在处理非合作博弈情况下的决策分析。 这篇文章深入剖析了工件在带有激活费用的同类机器间的策略选择问题，为理解和优化这类复杂系统提供了数学模型和理论依据。