Approximate strong equilibrium in job scheduling games

A Nash Equilibrium (NE) is a strategy profile that is resilient to unilateral deviations, and is predominantly used in the analysis of multi-agent systems. A downside of NE is that it is not necessarily stable against deviations by coalitions. Yet, as we show in this paper, in some cases, NE does exhibit stability against coalitional deviations, in that the benefits from a joint deviation are bounded. In this sense, NE approximates strong equilibrium (SE) [6]. Coalition formation is a key issue in multiagent systems. We provide a framework for quantifying the stability and the performance of various assignment policies and solution concept in the face of coalitional deviations. Within this framework we evaluate a given configuration according to three measurements: (i) IRmin: the maximal number α, such that there exists a coalition in which the minimum improvement ratio among the coalition members is α (ii) IRmax: the maximum improvement ratio among the coalition’s members. (iii) DRmax: the maximum possible damage ratio of an agent outside the coalition. This framework can be used to study the proximity between different solution concepts