# Data-Scarce Identification of Game Dynamics via Sum-of-Squares Optimization

arXiv: https://arxiv.org/abs/2307.06640 · HTML: https://mlsanity.com/paper/2307.06640/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 52 references that are in the map.
- First posted on arXiv 13 Jul 2023.

## Builds on (most cited first, 12 of 12)

- [AI Feynman: a Physics-Inspired Method for Symbolic Regression](https://mlsanity.com/paper/1905.11481/) (2019)
- [Discovering Symbolic Models from Deep Learning with Inductive Biases](https://mlsanity.com/paper/2006.11287/) (2020)
- [Physics-informed learning of governing equations from scarce data](https://mlsanity.com/paper/2005.03448/) (2020)
- [AI Feynman 2.0: Pareto-optimal symbolic regression exploiting graph modularity](https://mlsanity.com/paper/2006.10782/) (2020)
- [Sparse identification of nonlinear dynamics for model predictive control in the low-data limit](https://mlsanity.com/paper/1711.05501/) (2017)
- [AI Poincar'e: Machine Learning Conservation Laws from Trajectories](https://mlsanity.com/paper/2011.04698/) (2020)
- [Nonparametric inference of interaction laws in systems of agents from trajectory data](https://mlsanity.com/paper/1812.06003/) (2018)
- [Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Games](https://mlsanity.com/paper/1905.08396/) (2019)
- [Exploration-Exploitation in Multi-Agent Competition: Convergence with Bounded Rationality](https://mlsanity.com/paper/2106.12928/) (2021)
- [Learning Dynamical Systems with Side Information](https://mlsanity.com/paper/2008.10135/) (2020)
- [Shape-Constrained Regression using Sum of Squares Polynomials](https://mlsanity.com/paper/2004.03853/) (2020)
- [The Price of Anarchy in Transportation Networks: Data-Driven Evaluation and Reduction Strategies](https://mlsanity.com/paper/1606.02194/) (2016)

## Abstract (arXiv)

Understanding how players adjust their strategies in games, based on their experience, is a crucial tool for policymakers. It enables them to forecast the system's eventual behavior, exert control over the system, and evaluate counterfactual scenarios. The task becomes increasingly difficult when only a limited number of observations are available or difficult to acquire. In this work, we introduce the Side-Information Assisted Regression (SIAR) framework, designed to identify game dynamics in multiplayer normal-form games only using data from a short run of a single system trajectory. To enhance system recovery in the face of scarce data, we integrate side-information constraints into SIAR, which restrict the set of feasible solutions to those satisfying game-theoretic properties and common assumptions about strategic interactions. SIAR is solved using sum-of-squares (SOS) optimization, resulting in a hierarchy of approximations that provably converge to the true dynamics of the system. We showcase that the SIAR framework accurately predicts player behavior across a spectrum of normal-form games, widely-known families of game dynamics, and strong benchmarks, even if the unknown system is chaotic.