On The PoA And SPoA Of Machine Covering Game For Two Uniform Machines

In this thesis, we study Nash equilibrium and Strong Nash equilibrium for a machine covering game problem on two uniform machines, where the selfish goal of each player(job) is to minimize its own cost, which is defined as the total load on the machine that this job is assigned to. Our goal is to maximize the social value,which is the minimum load(cover) over the machines.We study the Price of Anarchy(PoA) and Strong Price of Anarchy(SPoA) of this problem The PoA is the worst case ratio between the social value of an optimal schedule and the value of any Nash equilibrium The SPoA is the worst case ratio between the social value of an optimal schedule and the value of any strong Nash equilibrium We obtain some results as follows:When S≥2,SPoA(s)=∞When 1