Nash Equilibrium and Price of Anarchy for Scheduling Games Based on a Mixed Coordination Mechanism
摘要
We investigate two machine-scheduling games under a mixed coordination mechanism, where some machines operate based on Shortest Processing Time (SPT) rules and others operate based on Longest Processing Time (LPT) rules. Jobs regarded as selfish players choose some machine and generate a schedule where each job aims to minimize its own completion time. We evaluate the effectiveness of the pure Nash equilibrium (NE) by analyzing the Price of Anarchy (PoA) concerning both the total completion time and the makespan for all jobs. The maximum ratio of the worst central objective value of NEs to the optimal central objective value across all problem instances defines the PoA. We propose different algorithms tailored to the parallel and uniform machine-models, each capable of producing NE; and provide upper bounds on the PoA from the perspective of total completion time and makespan.