Solutions to Games, Transitions and Efficiency

For any solution concept, we extend the solution set of a strategic-form game to a transition set. This set contains profiles where various agents simultaneously follow different solutions, e.g. different Nash equilibria. This models the fact that in practice, complicated agents are rarely perfectly coordinated on the same equilibrium. We define two efficiency measures, called the price of transition anarchy and stability, and bound them. We also refine the notion of transition to the notion of limited transition, where only a limited number of solutions is simultaneously played, and to stable transitions, which allow for only minor lack of coordination. We bound the efficiency of transitions for important cases, including the important cases of constant-sum and potential games, which span the set of finite games with the same number of strategies for each agent. Finally, we prove tight efficiency bounds for routing games and coordination games on graphs. We conclude that for the sake of efficiency, it is crucial to avoid uncoordinated transitions, besides certain cases, such as constant-sum games, identical utility games, some types of routing games, limited transitions in potential games, and stable transitions in coordination games.