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 behavior patterns that do not reflect their equilibrium properties. The challenge of any analytic investigation is to identify and characterize persistent properties despite the inherent irregularities of such systems and to do so efficiently. We develop a novel framework to address this challenge. Our setting focuses on evolutionary dynamics in network extensions of zero-sum games. Such dynamics have been shown analytically to exhibit chaotic behavior which traditionally has been thought of as an overwhelming obstacle to algorithmic inquiry. We circumvent these issues as follows: First, we combine ideas from dynamical systems and game theory to produce topological characterizations of system trajectories. Trajectories capture the time evolution of the system 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 utility 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.