[Colloquium] 10/16 Amy Greenwald (Brown) From Min-max Optimization to Stackelberg Games: Solutions and Applications

[Holly Santos]

Department of Computer Science Seminar

Amy Greenwald
Professor, Computer Science
Brown University

Monday, October 16th
11:00am - 12:00pm
In-Person: John Crerar Library 298

Title:  From Min-max Optimization to Stackelberg Games: Solutions and Applications

Abstract:
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

Bio:
Amy Greenwald is Professor of Computer Science at Brown University.  Her research focus is on game-theoretic and economic interactions among computational agents, applied to areas like autonomous bidding in wireless spectrum auctions and ad exchanges.  Before joining Brown, Greenwald was a postdoctoral researcher at IBM's T.J. Watson Research Center, where her “Shopbots and Pricebots" paper was named Best Paper at IBM Research.  Since joining Brown, she has held visiting appointments at the Japanese National Institute of Advanced Industrial Science and Technology’s Artificial Intelligence Research Center, Microsoft Research, the Amsterdam Center for Mathematics and Computer Science, and the Erasmus Research Institute of Management.  Her honors include the Presidential Early Career Award for Scientists and Engineers (PECASE), a Fulbright nomination, and a Sloan Fellowship.  Finally, Greenwald is active in promoting diversity in Computer Science, leading multiple K-12 initiatives in which Brown undergraduates teach computer science to public school students in the greater Providence area.

[amy.jpeg]


----
Holly Santos
Executive Assistant to Hank Hoffmann, Chairman
Department of Computer Science
The University of Chicago
5730 S Ellis Ave-217   Chicago, IL 60637
P: 773-834-8977
hsantos at uchicago.edu




-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20231011/99940d14/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: amy.jpeg
Type: image/jpeg
Size: 20829 bytes
Desc: amy.jpeg
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20231011/99940d14/attachment-0001.jpeg>