Optimization despite chaos: convex relaxations to complex limit sets via Poincaré recurrence

It is well understood that decentralized systems can, through network interactions, give rise to complex be-havior patterns that do not reflect their equilibrium properties. The challenge of any analytic investigation is to identify and characterize persistent properties de-spite the inherent irregularities of such systems and to do so efficiently. We develop a novel framework to ad-dress this challenge. Our setting focuses on evolutionary dynamics in network extensions of zero-sum games. Such dynam-ics have been shown analytically to exhibit chaotic be-havior which traditionally has been thought of as an overwhelming obstacle to algorithmic inquiry. We cir-cumvent these issues as follows: First, we combine ideas from dynamical systems and game theory to pro-duce topological characterizations of system trajecto-ries. Trajectories capture the time evolution of the sys-tem given an initial starting state. They are complex, and do not necessarily converge to limit points or even limit cycles. We provide tractable approximations of such limit sets. These relaxed descriptions involve sim-plices, and can be computed in polynomial time. Next, we apply standard optimization techniques to compute extremal values of system features (e.g. expected util-ity of an agent) within these relaxations. Finally, we use information theoretic conservation laws along with Poincare ́ recurrence theory to argue about tightness and optimality of our relaxation techniques. This work is supported by FA9550-09-1-0538. Authors ’ ad-