Flows and Decompositions of Games: Harmonic and Potential Games

-
Pablo Parrilo, MIT
Fine Hall 214

We introduce a novel flow representation for finite games in strategic form. Based on this representation, we develop a canonical direct sum decomposition of an arbitrary game into three components, which we refer to as the potential, harmonic and nonstrategic components. Besides its intrinsic interest, this decomposition facilitates the study of Nash and correlated equilibria as well as convergence properties of natural distributed game dynamics. We explain the basic ideas, and illustrate the implications of the decomposition for dynamic analysis, pricing schemes, efficiency loss, and network games. Based on joint work with Ozan Candogan, Ishai Menache, and Asu Ozdaglar (MIT).