Search

We study the classic setting where two agents compete against each other in a zero-sum game by applying the Multiplicative Weights Update (MWU) algorithm. In a twist of the standard approach of [Freund and Schapire 1999], we focus on the K-L divergence from the equilibrium but instead of providing an upper bound about the rate of increase we provide a nonnegative lower bound for games with interior equilibria. This implies movement away from equilibria and towards the boundary. In the case of zero-sum games without interior equilibria convergence to the boundary (and in fact to the minimal product of subsimplexes that contains all Nash equilibria) follows via an orthogonal argument. In that subspace divergence from the set of NE applies for all nonequilibrium initial conditions via the first argument. We argue the robustness of this non-equilibrating behavior by considering the following generalizations: Step size: Agents may be using different and even decreasing step sizes. Dynamics: Agents may be using Follow-the-Regularized-Leader algorithms and possibly apply different regularizers (e.g. MWU versus Gradient Descent). We also consider a linearized version of MWU. More than two agents: Multiple agents can interact via arbitrary networks of zero-sum polymatrix games and their affine variants. Our results come in stark contrast with the standard interpretation of the behavior of MWU (and more generally regret minimizing dynamics) in zero-sum games, which is typically referred to as "converging to equilibrium". If equilibria are indeed predictive even for the benchmark class of zero-sum games, agents in practice must deviate robustly from the axiomatic perspective of optimization driven dynamics as captured by MWU and variants and apply carefully tailored equilibrium-seeking behavioral dynamics. [ABSTRACT FROM AUTHOR]

Many multi-agent machine learning settings can be modeled as games, from social or economic systems with algorithmic decision-makers to popular learning architectures such as generative adversarial networks (GANs). Desired outcomes in these settings are often encoded as equilibrium concepts, and therefore a primary goal is identifying machine learning algorithms with provable convergence to these equilibria. However, a growing body of negative results casts doubt on this goal by uncovering games exhibiting non-convergence, chaos, and even essentially arbitrary behaviour [Andrade et al. 2021; Benaïm et al. 2012; Cheung and Piliouras 2019; Chotibut et al. 2020; Flokas et al. 2020; Letcher 2021; Milionis et al. 2022; Wibisono et al. 2022]. [ABSTRACT FROM AUTHOR]

What does it mean to fully understand the behavior of a network of adaptive agents? The golden standard typically is the behavior of learning dynamics in potential games, where many evolutionary dynamics, e.g., replicator dynamics, are known to converge to sets of equilibria. Even in such classic settings many questions remain unanswered. We examine issues such as: --Point-wise convergence: Does the system always equilibrate, even in the presence of continuums of equilibria? --Computing regions of attraction: Given point-wise convergence can we compute the region of asymptotic stability of each equilibrium (e.g., estimate its volume, geometry)? --System invariants: Invariant functions remain constant along every system trajectory. This notion is orthogonal to the game theoretic concept of a potential function, which always strictly increases/decreases along system trajectories. Do dynamics in potential games exhibit invariant functions? If so, how many? How do these functions look like? Based on these geometric characterizations, we propose a novel quantitative framework for analyzing the efficiency of potential games with many equilibria. The predictions of different equilibria are weighted by their probability to arise under evolutionary dynamics given uniformly random initial conditions. This average case analysis is shown to offer novel insights in classic game theoretic challenges, including quantifying the risk dominance in stag-hunt games and allowing for more nuanced performance analysis in networked coordination and congestion games with large gaps between price of stability and price of anarchy. [ABSTRACT FROM AUTHOR]

The article discusses the risk sensitivity of the price of anarchy framework in algorithmic game theory and decision making under uncertainty. Topics discussed include the exposition of the single agent decision making framework, the case of congestion games with randomized scheduling policies, and the price of anarchy for each of several decision making principles including risk-neutral stochastic optimization, Wald's minimax cost principle, and average case analysis.