Limited Resource Allocation Games With Activation Cost

In this paper, we investigate resource allocation games for job schedulingwith machine activation cost when the resources are limited. No machines areinitially activated. Activating each machine incurs a fixed machine activationcost. Jobs are self-interest-seeking players who choose machines with the objectiveof minimizing their individual cost which is the load on its chosen machine plusits share in the resource.s activation cost. The social cost is the sum of thesystem makespan and activation cost of machines. We assess the quality of pureNash equilibria in terms of the price of anarchy(PoA). The structure of this paperis organized as follows.In the first chapter, the background and some definitions are introduced.Then, we show the related developments of this problem. Finally, we summarizethe main results and innovations of this paper.In the second chapter, we consider a system with a fixed number m ofidentical machines. The activation cost is1. First, we present a proof thatthe PoA is less than m when there are m identical machines. We also provide aninstance to prove the bound is asymptotically tight. In addition, we prove thatthe PoA are bounded by32and2for two special cases of m=2and m=3whenW≥1, respectively. Finally, we also provide instances to prove those bounds aretight.In the third chapter, we consider a system with two uniform machines. Ma-chine speeds are respectively1and a which are in accordance with their activationcosts. First, we show a pure NE always exists and can be computed in polynomialtime when W≤1and W≥1+a. Then, we prove that the PoA is less than1+a. Finally, we provide an instance to prove the bound is tight.