<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body style="overflow-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;">
<i>Department of Computer Science Seminar</i>
<div><br>
</div>
<div><b>Amy Greenwald</b></div>
<div><b>Professor, Computer Science</b></div>
<div><b>Brown University </b></div>
<div><b><br>
</b></div>
<div><b>Monday, October 16th</b></div>
<div><b style="background-color: rgb(255, 251, 0);">4:00pm - 5:00pm </b></div>
<div><b style="background-color: rgb(255, 251, 0);">In-Person: John Crerar Library 346</b></div>
<div><b><br>
</b></div>
<div><b>Title: From Min-max Optimization to Stackelberg Games: Solutions and Applications</b></div>
<div><b><br>
</b></div>
<div><b>Abstract:</b></div>
<div>
<div>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.</div>
<div><br>
</div>
<div>Joint work with Denizalp Goktas</div>
</div>
<div><b><br>
</b></div>
<div><b>Bio:</b></div>
<div>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.</div>
<div><br>
</div>
<div><img id="<A4C85BC0-15B7-480F-8161-10BE8DC5E474>" src="cid:C766DBD2-ABCF-406E-9454-6BC089135CB8" alt="amy.jpeg" class="Apple-web-attachment" style="opacity: 1;"></div>
<div><br>
</div>
<div>---</div>
<div>
<div dir="auto" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; overflow-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;">
<div>Holly Santos<br>
Executive Assistant to Hank Hoffmann, Chairman<br>
Department of Computer Science<br>
The University of Chicago<br>
5730 S Ellis Ave-217 Chicago, IL 60637<br>
P: 773-834-8977<br>
hsantos@uchicago.edu</div>
<div><br>
</div>
</div>
<br class="Apple-interchange-newline">
<br class="Apple-interchange-newline">
</div>
<br>
</body>
</html>