Optimization despite chaos: Convex relaxations to complex limit sets via poincaré recurrence

Georgios Piliouras*, Jeff S. Shamma

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

27 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
PublisherAssociation for Computing Machinery
Pages861-873
Number of pages13
ISBN (Print)9781611973389
DOIs
StatePublished - Jan 1 2014
Event25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 - Portland, OR, United States
Duration: Jan 5 2014Jan 7 2014

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
CountryUnited States
CityPortland, OR
Period01/5/1401/7/14

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Optimization despite chaos: Convex relaxations to complex limit sets via poincaré recurrence'. Together they form a unique fingerprint.

Cite this