Date & Time:
October 16, 2023 11:00 am – 12:00 pm
10/16/2023 11:00 AM 10/16/2023 12:00 PM America/Chicago Amy Greenwald (Brown University)-From Min-max Optimization to Stackelberg Games: Solutions and Applications Computer Science Seminar

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

Speakers

Headshot of Amy Greenwald

Amy Greenwald

Professor, Computer Science

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.

Related News & Events

Video

“Machine Learning Foundations Accelerate Innovation and Promote Trustworthiness” by Rebecca Willett

Jan 26, 2024
Video

Nightshade: Data Poisoning to Fight Generative AI with Ben Zhao

Jan 23, 2024
No Name

In The News: U.N. Officials Urge Regulation of Artificial Intelligence

"Security Council members said they feared that a new technology might prove a major threat to world peace."
Jul 27, 2023
No Name

UChicago Computer Scientists Bring in Generative Neural Networks to Stop Real-Time Video From Lagging

Jun 29, 2023
No Name

Computer Science Displays Catch Attention at MSI’s Annual Robot Block Party

Apr 07, 2023
No Name

UChicago, Stanford Researchers Explore How Robots and Computers Can Help Strangers Have Meaningful In-Person Conversations

Mar 29, 2023
No Name

Postdoc Alum John Paparrizos Named ICDE Rising Star

Mar 15, 2023
No Name

New EAGER Grant to Asst. Prof. Eric Jonas Will Explore ML for Quantum Spectrometry

Mar 03, 2023
No Name

Assistant Professor Chenhao Tan Receives Sloan Research Fellowship

Feb 15, 2023
No Name

UChicago Scientists Develop New Tool to Protect Artists from AI Mimicry

Feb 13, 2023
No Name

Professors Rebecca Willett and Ben Zhao Discuss the Future of AI on Public Radio

Jan 26, 2023
No Name

UChicago Launches Transform Accelerator for Data Science & Emerging AI Startups

Jan 19, 2023
arrow-down-largearrow-left-largearrow-right-large-greyarrow-right-large-yellowarrow-right-largearrow-right-smallbutton-arrowclosedocumentfacebookfacet-arrow-down-whitefacet-arrow-downPage 1CheckedCheckedicon-apple-t5backgroundLayer 1icon-google-t5icon-office365-t5icon-outlook-t5backgroundLayer 1icon-outlookcom-t5backgroundLayer 1icon-yahoo-t5backgroundLayer 1internal-yellowinternalintranetlinkedinlinkoutpauseplaypresentationsearch-bluesearchshareslider-arrow-nextslider-arrow-prevtwittervideoyoutube