Mathematics of Information Seminar
Beyond Equilibria (1st of 2 parts. Cont. on Nov. 11.)
The notion of equilibrium is a central concept that lies on the intersection of game theory, control theory, dynamical systems and computer science. It provides a palpable and easy-to-understand handle for arguing about decentralized systems. This simplicity, however, comes at a cost since many times in practice this framework is too restrictive and cannot address key real life phenomena. These include the effects of transient system phenomena, the plausibility of persistent far-from-equilibrium behavior, as well as the quantitative analysis of systems with multiple equilibria.
We will discuss a number of different techniques to address such challenges and pinpoint some key mathematical tools for:
a) online learning/optimization based approaches (e.g., regret minimization) and their connections to convex relaxations of the notion of (Nash) equilibrium;
b) the techniques and limitations of robust price of anarchy (including recent couplings of these ideas with stochastic/robust optimization);
c) average case analysis techniques for systems with many attracting equilibria (from identifying system invariants to approximating the volumes of regions of attraction);
d) novel frameworks for analyzing disequilibrium systems (e.g., persistent patterns).
No background will be assumed in the respective disciplines and the talk will be self-contained.