Profitable Deviation Strong Equilibria

International audienceThis paper deals with states that are immune to group deviations. Group deviations help the players of a strategic game to escape from undesirable states but they compromise the stability of a system. We propose and analyse a solution concept, called profitable deviation strong equilibrium, which is between two well-known equilibria: the strong equilibrium and the super strong equilibrium. The former precludes joint deviations by groups of players who all benefit. The latter is more demanding in the sense that at least one member of a deviating coalition must be better off while the other members cannot be worst off. We study the existence, computation and convergence to a profitable deviation strong equilibrium in three important games in algorithmic game theory: job scheduling, max cut and singleton congestion game