Efficiency and inefficiency of Nash equilibrium for scheduling games on batching-machines with activation cost.

We study two scheduling games on parallel-batching machines with activation cost, where each game involves n jobs being processed on m parallel-batching identical machines. Each job, as an agent, selects a machine (more precisely, a batch on a machine) for processing to minimize his disutility. For the former game, on the basis of previous results, we find the conditions for the existence of Nash equilibrium, and present the parametric upper bounds of price of anarchy (PoA) and the price of stability (PoS) for the minimax and minisum objectives, and provide some mixed strategy Nash equilibria for two special cases. For the latter game, we first analyze the conditions for the nonexistence of Nash equilibrium, and provide tight approximate Nash equilibrium. Then, the conditions for the existence of Nash equilibrium are studied, and the constant-bounds of PoA and PoS for the minimax objective are given. [ABSTRACT FROM AUTHOR]