Amy Greenwald (Brown University)-From Min-max Optimization to Stackelberg Games: Solutions and Applications

While optimization has always been crucial to the design of individual AI agents, min-max optimization is emerging as a powerful technique in which to design and analyze multi-agent AI systems. Because of the minimax theorem, convex-concave min-max optimization is often viewed as a simultaneous-move two-player zero-sum game; in such games, simultaneous gradient descent ascent (GDA) converges to Nash equilibrium in polynomial time. Generalizing from these classic results, we first study convex-concave two-player Stackelberg, i.e., sequential, zero-sum games, played between a leader and a follower, for which we develop a nested version of GDA that converges to Stackelberg equilibrium in polynomial time. We then study pseudo-games, a generalization of simultaneous-move games, for which the canonical solution concept is generalized Nash equilibrium. We reduce pseudo-games to quasi-min-max optimization, which we can again solve efficiently for certain well-behaved classes of pseudo-games. Finally, we put these pieces together to analyze Stackelberg-Nash pseudo-games, in which a leader moves first, after which multiple agents engage in a pseudo-game. We apply these Stackelberg game models to Fisher and Arrow-Debreu markets, noting that their competitive equilibria correspond to Stackelberg-Nash equilibria, thereby deriving efficient algorithms that converge to competitive equilibrium in broad classes of these markets.

Joint work with Denizalp Goktas