TY - GEN

T1 - Optimization despite chaos

T2 - 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014

AU - Piliouras, Georgios

AU - Shamma, Jeff S.

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84902097276&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84902097276&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973402.64

DO - 10.1137/1.9781611973402.64

M3 - Conference contribution

AN - SCOPUS:84902097276

SN - 9781611973389

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 861

EP - 873

BT - Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014

PB - Association for Computing Machinery

Y2 - 5 January 2014 through 7 January 2014

ER -