Publications
2025
- NeurIPS ’25Certifying Concavity and Monotonicity in Games via Sum-of-Squares HierarchiesIn Proceedings of the 39th Neural Information Processing Systems Conference, 2025
Concavity and its refinements underpin tractability in multiplayer games, where players independently choose actions to maximize their own payoffs, which depend on other players’ actions. In concave games, where players’ strategy sets are compact and convex, and their payoffs are concave in their own actions, strong guarantees follow: Nash equilibria always exist and decentralized algorithms converge to equilibria. If the game is furthermore monotone, an even stronger guarantee holds: Nash equilibria are unique under strictness assumptions. Unfortunately, we show that certifying concavity or monotonicity is NP-hard, already for games where utilities are multivariate polynomials and compact, convex basic semialgebraic strategy sets—an expressive class that captures extensive-form games with imperfect recall. On the positive side, we develop two hierarchies of sum-of-squares programs that certify concavity and monotonicity of a given game, and each level of the hierarchies can be solved in polynomial time. We show that almost all concave/monotone games are certified at some finite level of the hierarchies. Subsequently, we introduce the classes of SOS-concave/monotone games, which globally approximate concave/monotone games, and show that for any given game we can compute the closest SOS-concave/monotone game in polynomial time. Finally, we apply our techniques to canonical examples of extensive-form games with imperfect recall.
@inproceedings{leon_certifying_2025, title = {Certifying Concavity and Monotonicity in Games via Sum-of-Squares Hierarchies}, author = {Leon, Vincent and Sakos, Iosif and Sim, Ryann and Varvitsiotis, Antonios}, booktitle = {Proceedings of the 39th Neural Information Processing Systems Conference}, year = {2025}, url = {https://openreview.net/forum?id=8ftsTxZOLQ}, } - L4DC ’25Learning and Steering Game Dynamics Towards Desirable OutcomesIlayda Canyakmaz, Iosif Sakos, Wayne Lin, and 2 more authorsIn Proceedings of the 7th Annual Learning for Dynamics & Control Conference, 2025
Game dynamics, which describe how agents’ strategies evolve over time based on past interactions, can exhibit a variety of undesirable behaviors including convergence to suboptimal equilibria, cycling, and chaos. While central planners can employ incentives to mitigate such behaviors and steer game dynamics towards desirable outcomes, the effectiveness of such interventions critically relies on accurately predicting agents’ responses to these incentives—a task made particularly challenging when the underlying dynamics are unknown and observations are limited. To address this challenge, this work introduces the Side Information Assisted Regression with Model Predictive Control (SIAR-MPC) framework. We extend the recently introduced SIAR method to incorporate the effect of control, enabling it to utilize side-information constraints inherent to game-theoretic applications to model agents’ responses to incentives from scarce data. MPC then leverages this model to implement dynamic incentive adjustments. Our experiments demonstrate the effectiveness of SIAR-MPC in guiding systems towards socially optimal equilibria and stabilizing chaotic and cycling behaviors. Notably, it achieves these results in data-scarce settings of few learning samples, where well-known system identification methods paired with MPC show less effective results.
@inproceedings{canyakmaz_learning_2025, title = {Learning and Steering Game Dynamics Towards Desirable Outcomes}, author = {Canyakmaz, Ilayda and Sakos, Iosif and Lin, Wayne and Varvitsiotis, Antonios and Piliouras, Georgios}, booktitle = {Proceedings of the 7th Annual Learning for Dynamics \& Control Conference}, series = {Proceedings of Machine Learning Research}, volume = {283}, pages = {1512--1524}, year = {2025}, url = {https://proceedings.mlr.press/v283/canyakmaz25a.html}, }
2024
- ICLR ’24Beating Price of Anarchy and Gradient Descent without Regret in Potential GamesIosif Sakos, Stefanos Leonardos, Stelios A. Stavroulakis, and 3 more authorsIn Proceedings of the 12th International Conference on Representation Learning, 2024
Arguably one of the thorniest problems in game theory is that of equilibrium selection. Specifically, in the presence of multiple equilibria, do self-interested learning dynamics typically select the socially optimal ones? We study a rich class of continuous-time no-regret dynamics in potential games (PGs). Our class of dynamics, Q-Replicator Dynamics (QRD), includes gradient descent (GD), log-barrier, and replicator dynamics (RD) as special cases. We start by establishing pointwise convergence of all QRD to Nash equilibria in almost all PGs. In the case of GD, we show a tight average-case performance within a factor of two of optimal, for a class of symmetric 2×2 potential games with unbounded Price of Anarchy (PoA). Despite this positive result, we show that GD is not always the optimal choice even in this restricted setting. Specifically, GD outperforms RD if and only if risk- and payoff-dominance equilibria coincide. Finally, we experimentally show how these insights extend to all QRD dynamics and that unbounded gaps between average-case performance and PoA analysis are common even in larger settings.
@inproceedings{sakos_beating_2024, title = {Beating Price of Anarchy and Gradient Descent without Regret in Potential Games}, author = {Sakos, Iosif and Leonardos, Stefanos and Stavroulakis, Stelios A. and Overman, William and Panageas, Ioannis and Piliouras, Georgios}, booktitle = {Proceedings of the 12th International Conference on Representation Learning}, year = {2024}, url = {https://openreview.net/forum?id=36L7W3ri4U}, } - WINE ’24Data-Scarce Identification of Game Dynamics via Sum-of-Squares OptimizationIosif Sakos, Antonios Varvitsiotis, and Georgios PiliourasIn Proceedings of the 20th Web and Internet Economics Conference, 2024
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.
@inproceedings{sakos_data-scarce_2024, title = {Data-Scarce Identification of Game Dynamics via Sum-of-Squares Optimization}, author = {Sakos, Iosif and Varvitsiotis, Antonios and Piliouras, Georgios}, booktitle = {Proceedings of the 20th Web and Internet Economics Conference}, year = {2024}, isbn = {978-3-032-08559-7}, }
2023
- ACM TEACCatastrophe by Design in Population Games: A Mechanism to Destabilize Inefficient Locked-in TechnologiesACM Transactions on Economics and Computation, 2023
In multi-agent environments in which coordination is desirable, the history of play often causes lock-in at suboptimal outcomes. Notoriously, technologies with significant environmental footprint or high social cost persist despite the successful development of more environmentally friendly and/or socially efficient alternatives. The displacement of the status quo is hindered by entrenched economic interests and network effects. To exacerbate matters, the standard mechanism design approaches based on centralized authorities with the capacity to use preferential subsidies to effectively dictate system outcomes are not always applicable to modern decentralized economies. What other types of mechanisms are feasible? In this article, we develop and analyze a mechanism that induces transitions from inefficient lock-ins to superior alternatives. This mechanism does not exogenously favor one option over another; instead, the phase transition emerges endogenously via a standard evolutionary learning model, Q-learning, where agents trade off exploration and exploitation. Exerting the same transient influence to both the efficient and inefficient technologies encourages exploration and results in irreversible phase transitions and permanent stabilization of the efficient one. On a technical level, our work is based on bifurcation and catastrophe theory, a branch of mathematics that deals with changes in the number and stability properties of equilibria. Critically, our analysis is shown to be structurally robust to significant and even adversarially chosen perturbations to the parameters of both our game and our behavioral model.
@article{leonardos_catastrophe_2023, title = {Catastrophe by Design in Population Games: A Mechanism to Destabilize Inefficient Locked-in Technologies}, author = {Leonardos, Stefanos and Sakos, Iosif and Courcoubetis, Constantinos A. and Piliouras, Georgios}, journal = {ACM Transactions on Economics and Computation}, year = {2023}, volume = {11}, number = {1--2}, eid = {1}, doi = {10.1145/3583782}, } - NeurIPS ’23Exploiting Hidden Structures in Non-Convex Games for Convergence to Nash EquilibriumIn Proceedings of the 37th Neural Information Processing Systems Conference, 2023
A wide array of modern machine learning applications—from adversarial models to multi-agent reinforcement learning—can be formulated as non-cooperative games whose Nash equilibria represent the system’s desired operational states. Despite having a highly non-convex loss landscape, many cases of interest possess a latent convex structure that could potentially be leveraged to yield convergence to an equilibrium. Driven by this observation, our paper proposes a flexible first-order method that successfully exploits such "hidden structures" and achieves convergence under minimal assumptions for the transformation connecting the players’ control variables to the game’s latent, convex-structured layer. The proposed method—which we call preconditioned hidden gradient descent (PHGD)—hinges on a judiciously chosen gradient preconditioning scheme related to natural gradient methods. Importantly, we make no separability assumptions for the game’s hidden structure, and we provide explicit convergence rate guarantees for both deterministic and stochastic environments.
@inproceedings{sakos_exploiting_2023, title = {Exploiting Hidden Structures in Non-Convex Games for Convergence to {N}ash Equilibrium}, author = {Sakos, Iosif and Vlatakis-Gkaragkounis, Emmanouil-Vasileios and Mertikopoulos, Panayotis and Piliouras, Georgios}, booktitle = {Proceedings of the 37th Neural Information Processing Systems Conference}, year = {2023}, doi = {10.5555/3666122.3669048}, }
2022
- ICLR ’22Generalized Natural Gradient Flows in Hidden Convex-Concave Games and GANsIn Proceedings of the 10th International Conference on Learning Representations, 2022
Game-theoretic formulations in machine learning have recently risen in prominence, whereby entire modeling paradigms are best captured as zero-sum games. Despite their popularity, however, their dynamics are still poorly understood. This lack of theory is often substantiated with painful empirical observations of volatile training dynamics and even divergence. Such results highlight the need to develop an appropriate theory with convergence guarantees that are powerful enough to inform practice. This paper studies the generalized Gradient Descent-Ascent (GDA) flow in a large class of non-convex non-concave zero-sum games dubbed Hidden Convex-Concave games, a class of games that includes GANs. We focus on two specific geometries: a novel geometry induced by the hidden convex-concave structure that we call the hidden mapping geometry and the Fisher information geometry. For the hidden mapping geometry, we prove global convergence under mild assumptions. In the case of Fisher information geometry, we provide a complete picture of the dynamics in an interesting special setting of team competition via invariant function analysis.
@inproceedings{mladenovic_generalized_2022, title = {Generalized Natural Gradient Flows in Hidden Convex-Concave Games and {GAN}s}, author = {Mladenovic, Andjela and Sakos, Iosif and Gidel, Gauthier and Piliouras, Georgios}, booktitle = {Proceedings of the 10th International Conference on Learning Representations}, year = {2022}, isbn = {979-8-331-32193-2}, url = {https://openreview.net/forum?id=bsycpMi00R1}, }
2020
- WINE ’20Catastrophe by Design in Population Games: Destabilizing Wasteful Locked-In TechnologiesIn Proceedings of the 16th Web and Internet Economics Conference, 2020