Despite much interest in using game theoretic models for the analysis of resource allocation problems in multi-agent networked systems, most of the existing works focus on static equilibrium analysis without establishing how an equilibrium can be reached dynamically. In the theory of games, natural distributed dynamics reach an equilibrium only for restrictive classes of games; potential games is an example. These considerations lead to a natural and important question: can we have a systematic approach to analyze dynamic properties of natural update schemes for general games?
Motivated by this question, this talk presents a new approach for the analysis of games, which involves viewing preferences of agents over the strategy profiles as flows on a graph. Using tools from the theory of graph flows (which are combinatorial analogues of those for continuous vector fields), we show that any finite strategic form game can be written as the direct sum of a potential game, a harmonic game, and a nonstrategic part. Hence, this decomposition leads to a new class of games, "harmonic games", with well-understood equilibrium and dynamic properties. Moreover, this approach allows projecting an arbitrary game onto the space of potential games using convex optimization techniques and exploit the relation between the two games to analyze the static and dynamic equilibrium properties of the original game. The second part of the talk uses this idea to study a non-cooperative power control game and investigate the system optimality properties along dynamic trajectories of natural user update schemes for this game.
This is joint work with Ozan Candogan, Ishai Menache, and Pablo Parrilo.