Data-Scarce Identification of Game Dynamics via Sum-of-Squares Optimization
This addresses the challenge for policymakers in forecasting and controlling strategic interactions in games when data is scarce, representing a novel method for a known bottleneck.
The paper tackles the problem of identifying game dynamics from limited data by introducing the Side-Information Assisted Regression (SIAR) framework, which uses sum-of-squares optimization to incorporate side-information constraints and provably converges to true dynamics, accurately predicting player behavior across various games and benchmarks, including chaotic systems.
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.