[Colloquium] 2/20 Amy Greenwald (Brown University) Learning in Simulation-Based Games

[Zainab Aslam]

Department of Computer Science Seminar

Amy Greenwald
Professor of Computer Science
Brown University

Monday, February 20th
4:00pm - 5:00pm
In Person: John Crerar Library 298

Title: Learning in Simulation-Based Games

Abstract:
In recent years, empirical game-theoretic analysis (EGTA) has emerged as a powerful tool for analyzing games in which an exact specification of the utilities is unavailable.  Instead, EGTA assumes access to an oracle, e.g., a simulator, which can generate unbiased noisy samples of players' unknown utilities, given a strategy profile.  Utilities can thus be empirically estimated by repeatedly querying the oracle.  There are many flavors of EGTA; our approach is statistical, in the spirit of probably approximately correct (PAC) learning.  First, we show that uniform approximations of simulation-based games preserve equilibria, at least approximately and with high probability.  In light of this result, we design a progressive sampling algorithm that efficiently learns a uniform approximation of a simulation-based game, pruning queries once it is determined that the players' utilities have been sufficiently well-estimated.  We further observe that while uniformly approximating a simulation-based game is sufficient for preserving equilibria, it is not necessary.  Our second algorithm prunes queries with provably high regret, which equilibria are unlikely to comprise, non-uniformly.  We prove the correctness and efficiency of our algorithms, and demonstrate their savings empirically on a suite of games, showing that they make frugal use of data and produce accurate estimates more often than the theory predicts.  Finally, we demonstrate the use of our methodology in empirical mechanism design.

Joint Work with Bhaskar Mishra, Cyrus Cousins, Enrique Areyan-Viqueira, and Yasser Mohammad

Bio:
Amy Greenwald is Professor of Computer Science at Brown University in Providence, Rhode Island.  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.

[Image]


Zainab Aslam
Business Assistant – Computer Science
The University of Chicago
5730 S Ellis Ave, JCL 212
Chicago, IL 60637
zaslam at uchicago.edu<mailto:zaslam at uchicago.edu>
Office: 773-702-2166
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20230213/d9458742/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.png
Type: image/png
Size: 1524565 bytes
Desc: image001.png
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20230213/d9458742/attachment-0001.png>