TITLE : Dynamic Inefficiency: Anarchy without Stability AUTHORS : Noam Berger, Michal Feldman, Ofer Neiman and Mishael Rosenthal ABSTRACT : The price of anarchy is by now a standard measure for quantifying the inefficiency introduced in games due to selfish behavior, and is defined as the ratio between the optimal outcome and the worst Nash equilibrium. However, the price of anarchy is not even defined in games that admit no Nash equilibrium. We propose the dynamic inefficiency measure, which quantifies the average inefficiency introduced by a process in which players follow best-response dynamics. We consider three best-response dynamic rules — Random Walk (RW), Round Robin (RR) and Best Improvement (BI) — which are distinguished according to the order in which players apply their best responses. We use the proposed measure to study three different games that may admit no pure Nash equilibrium, namely non-preemptive job scheduling on unrelated machines, the Hotelling game and the facility location game. We find that using different dynamic rules may yield diverse inefficiency outcomes, moreover it seems that no single dynamic rule is superior to another. It is also shown that the dynamic inefficiency may be arbitrarily higher than the price of anarchy in games where a Nash equilibrium may exist. In particular, Azar et al. gave a tight bound to the price of anarchy for a certain policy of job scheduling games, however we show that when no Nash equilibrium exists, the dynamic inefficiency may be arbitrarily higher. Our results resolve an open question raised in Azar et al. To the best of our knowledge this is the first work quantifying the inefficiency of games that may admit no Nash equilibrium with respect to general best-response dynamics. Both the price of anarchy and the price of sinking can be obtained as special cases of the dynamic inefficiency measure