Title: The Advantages of Regret Minimization in Bounding the Price of Anarchy

Abstract:

A central question in mechanism design when viewed from the perspective of optimization is: How much does performance degrade from its
optimal value when the elements of a system are controlled by selfish agents? This degradation is quantified by "the price of anarchy" of a system, and must be based on some assumption about how selfish agents will behave. The standard presumption is that selfish agents will play according to a Nash equilibrium. This assumption is, however, problematic in many settings. Since Nash Equilibria cannot in general be computed efficiently, they do not always constitute a plausible solution concept for computationally bounded agents. As mechanism designers, we may not have perfect knowledge of the utility functions of all players, and so bounds proven for Nash equilibria -- which offer no guarantee of stability unless all players participate -- may be brittle in the face of Byzantine or malicious agents. Finally, studying Nash equilibria in a one-shot game does not allow the consideration of dynamic noise models which might greatly affect the overall social welfare.

In this talk, I will propose "regret minimization" as a criterion for rationality when studying the price of anarchy, and show how it addresses each of the criticisms above. It is a strictly weaker assumption on repeated play than that players converge to a Nash equilibrium, and one that can be satisfied easily by computationally efficient players. Nevertheless, it is often a sufficiently strong condition to prove tight price-of anarchy bounds. Moreover, in the
regret-minimization model, it is possible to prove price-of-anarchy bounds even in the presence of Byzantine players, about whom we make no
assumptions. Finally, I will show a game and a noise model under which regret minimizing players are guaranteed to achieve social welfare that can be unboundedly better than that of the worst Nash equilibrium.

Much of this work is joint with Avrim Blum, Mohammadtaghi
Hajiaghayi,and Katrina Ligett.