Decentralized scheduling with precedence constraints

We consider decentralized scheduling with precedence constraints (DSwP) games where a set of players are scheduling jobs to complete while a set of hard precedence constraints link the jobs of the players. The impact of these decentralized scheduling efforts can be quantified by examining the price of anarchy (PoA) and the price of stability (PoS), which measure, respectively, the ratio of social costs of the worst and best equilibrium solutions with the optimal (centralized) social costs. We demonstrate that equilibrium solutions do not, in general, exist for this class of games and prove their existence for certain classes of games. Upper bounds for the PoA and the PoS are proven to depend linearly on the sum of the processing times of the jobs across the players and we present an example to demonstrate that this bound cannot be tightened beyond the sum of the processing times divided by two.