<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">CANCELLED UNTIL FURTHER NOTICE.<br class=""><div><br class=""><blockquote type="cite" class=""><div class="">Begin forwarded message:</div><br class="Apple-interchange-newline"><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px;" class=""><span style="font-family: -webkit-system-font, Helvetica Neue, Helvetica, sans-serif; color:rgba(0, 0, 0, 1.0);" class=""><b class="">From: </b></span><span style="font-family: -webkit-system-font, Helvetica Neue, Helvetica, sans-serif;" class="">Zainab Aslam <<a href="mailto:zaslam@uchicago.edu" class="">zaslam@uchicago.edu</a>><br class=""></span></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px;" class=""><span style="font-family: -webkit-system-font, Helvetica Neue, Helvetica, sans-serif; color:rgba(0, 0, 0, 1.0);" class=""><b class="">Subject: </b></span><span style="font-family: -webkit-system-font, Helvetica Neue, Helvetica, sans-serif;" class=""><b class="">[Staff] [Colloquium] 2/20 Amy Greenwald (Brown University) Learning in Simulation-Based Games</b><br class=""></span></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px;" class=""><span style="font-family: -webkit-system-font, Helvetica Neue, Helvetica, sans-serif; color:rgba(0, 0, 0, 1.0);" class=""><b class="">Date: </b></span><span style="font-family: -webkit-system-font, Helvetica Neue, Helvetica, sans-serif;" class="">February 13, 2023 at 8:50:34 AM CST<br class=""></span></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px;" class=""><span style="font-family: -webkit-system-font, Helvetica Neue, Helvetica, sans-serif; color:rgba(0, 0, 0, 1.0);" class=""><b class="">To: </b></span><span style="font-family: -webkit-system-font, Helvetica Neue, Helvetica, sans-serif;" class="">"<a href="mailto:colloquium@cs.uchicago.edu" class="">colloquium@cs.uchicago.edu</a>" <<a href="mailto:colloquium@cs.uchicago.edu" class="">colloquium@cs.uchicago.edu</a>><br class=""></span></div><br class=""><div class=""><meta charset="UTF-8" class=""><div class="WordSection1" style="page: WordSection1; caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: 400; 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;"><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><i class=""><span style="font-size: 10pt; font-family: "Times New Roman", serif;" class="">Department of Computer Science Seminar</span></i><span style="color: rgb(33, 33, 33);" class=""><o:p class=""></o:p></span></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif; caret-color: rgb(33, 33, 33); font-variant-caps: normal; text-align: start; -webkit-text-stroke-width: 0px; word-spacing: 0px;" class=""><span style="font-size: 10pt; font-family: "Times New Roman", serif;" class=""> </span><span style="color: rgb(33, 33, 33);" class=""><o:p class=""></o:p></span></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif; caret-color: rgb(33, 33, 33); font-variant-caps: normal; text-align: start; -webkit-text-stroke-width: 0px; word-spacing: 0px;" class=""><b class=""><span style="font-family: "Times New Roman", serif; letter-spacing: 0.15pt;" class="">Amy Greenwald</span></b><span style="font-family: "Times New Roman", serif; letter-spacing: 0.15pt;" class=""><br class=""><b class="">Professor of Computer Science </b><br class=""><b class="">Brown University </b></span><span style="color: rgb(33, 33, 33);" class=""><o:p class=""></o:p></span></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif; caret-color: rgb(33, 33, 33); font-variant-caps: normal; text-align: start; -webkit-text-stroke-width: 0px; word-spacing: 0px;" class=""><b class=""><span style="font-family: "Times New Roman", serif; letter-spacing: 0.15pt;" class=""> </span></b><span style="color: rgb(33, 33, 33);" class=""><o:p class=""></o:p></span></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif; caret-color: rgb(33, 33, 33); font-variant-caps: normal; text-align: start; -webkit-text-stroke-width: 0px; word-spacing: 0px;" class=""><b class=""><span style="font-family: "Times New Roman", serif; letter-spacing: 0.15pt;" class="">Monday, February 20th </span></b><span style="font-family: "Times New Roman", serif; letter-spacing: 0.15pt;" class=""><br class=""><b class="">4:00pm - 5:00pm </b><br class=""><b class="">In Person: John Crerar Library 298</b></span><span style="color: rgb(33, 33, 33);" class=""><o:p class=""></o:p></span></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif; caret-color: rgb(33, 33, 33); font-variant-caps: normal; text-align: start; -webkit-text-stroke-width: 0px; word-spacing: 0px;" class=""><span style="font-family: "Times New Roman", serif;" class=""> </span><span style="color: rgb(33, 33, 33);" class=""><o:p class=""></o:p></span></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif; caret-color: rgb(33, 33, 33); font-variant-caps: normal; text-align: start; -webkit-text-stroke-width: 0px; word-spacing: 0px;" class=""><b class=""><span style="font-family: "Times New Roman", serif; color: rgb(33, 33, 33);" class="">Title: Learning in Simulation-Based Games</span></b><span style="color: rgb(33, 33, 33);" class=""><o:p class=""></o:p></span></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif; caret-color: rgb(33, 33, 33); font-variant-caps: normal; text-align: start; -webkit-text-stroke-width: 0px; word-spacing: 0px;" class=""><span style="font-family: "Times New Roman", serif; color: rgb(33, 33, 33);" class=""> </span><span style="color: rgb(33, 33, 33);" class=""><o:p class=""></o:p></span></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif; caret-color: rgb(33, 33, 33); font-variant-caps: normal; text-align: start; -webkit-text-stroke-width: 0px; word-spacing: 0px;" class=""><b class=""><span style="font-family: "Times New Roman", serif; color: rgb(33, 33, 33);" class="">Abstract:</span></b><span style="color: rgb(33, 33, 33);" class=""><o:p class=""></o:p></span></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif; caret-color: rgb(33, 33, 33); font-variant-caps: normal; text-align: start; -webkit-text-stroke-width: 0px; word-spacing: 0px;" class=""><span style="font-family: "Times New Roman", serif; color: rgb(33, 33, 33);" class="">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.</span><span style="color: rgb(33, 33, 33);" class=""><o:p class=""></o:p></span></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif; caret-color: rgb(33, 33, 33); font-variant-caps: normal; text-align: start; -webkit-text-stroke-width: 0px; word-spacing: 0px;" class=""><span style="font-family: "Times New Roman", serif; color: rgb(33, 33, 33);" class=""> </span><span style="color: rgb(33, 33, 33);" class=""><o:p class=""></o:p></span></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif; caret-color: rgb(33, 33, 33); font-variant-caps: normal; text-align: start; -webkit-text-stroke-width: 0px; word-spacing: 0px;" class=""><span style="font-family: "Times New Roman", serif; color: rgb(33, 33, 33);" class="">Joint Work with Bhaskar Mishra, Cyrus Cousins, Enrique Areyan-Viqueira, and Yasser Mohammad</span><span style="color: rgb(33, 33, 33);" class=""><o:p class=""></o:p></span></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif; caret-color: rgb(33, 33, 33); font-variant-caps: normal; text-align: start; -webkit-text-stroke-width: 0px; word-spacing: 0px;" class=""><span style="font-family: "Times New Roman", serif; color: rgb(33, 33, 33);" class=""> </span><span style="color: rgb(33, 33, 33);" class=""><o:p class=""></o:p></span></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif; caret-color: rgb(33, 33, 33); font-variant-caps: normal; text-align: start; -webkit-text-stroke-width: 0px; word-spacing: 0px;" class=""><b class=""><span style="font-family: "Times New Roman", serif; color: rgb(33, 33, 33);" class="">Bio:</span></b><span style="color: rgb(33, 33, 33);" class=""><o:p class=""></o:p></span></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif; caret-color: rgb(33, 33, 33); font-variant-caps: normal; text-align: start; -webkit-text-stroke-width: 0px; word-spacing: 0px;" class=""><span style="font-family: "Times New Roman", serif; color: rgb(33, 33, 33);" class="">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.</span><span style="color: rgb(33, 33, 33);" class=""><o:p class=""></o:p></span></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif; caret-color: rgb(33, 33, 33); font-variant-caps: normal; text-align: start; -webkit-text-stroke-width: 0px; word-spacing: 0px;" class=""><span style="font-family: "Times New Roman", serif; color: rgb(33, 33, 33);" class=""> </span><span style="color: rgb(33, 33, 33);" class=""><o:p class=""></o:p></span></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif; caret-color: rgb(33, 33, 33); font-variant-caps: normal; text-align: start; -webkit-text-stroke-width: 0px; word-spacing: 0px;" class=""><span style="font-family: "Times New Roman", serif; color: rgb(33, 33, 33);" class=""><img id="Picture_x0020_1" alt="Image" style="" class="" apple-inline="yes" width="261" height="263" src="cid:image001.png@01D93F87.EFA51A90"></span><span style="color: rgb(33, 33, 33);" class=""><o:p class=""></o:p></span></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif; caret-color: rgb(33, 33, 33); font-variant-caps: normal; text-align: start; -webkit-text-stroke-width: 0px; word-spacing: 0px;" class=""><span style="color: rgb(33, 33, 33);" class=""> <o:p class=""></o:p></span></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif; caret-color: rgb(33, 33, 33); font-variant-caps: normal; text-align: start; -webkit-text-stroke-width: 0px; word-spacing: 0px;" class=""><span style="color: rgb(33, 33, 33);" class=""> <o:p class=""></o:p></span></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif; caret-color: rgb(33, 33, 33); font-variant-caps: normal; text-align: start; -webkit-text-stroke-width: 0px; word-spacing: 0px;" class=""><b class=""><span style="font-family: Arial, sans-serif; color: rgb(33, 33, 33);" class="">Zainab Aslam</span></b><span style="color: rgb(33, 33, 33);" class=""><o:p class=""></o:p></span></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif; caret-color: rgb(33, 33, 33); font-variant-caps: normal; text-align: start; -webkit-text-stroke-width: 0px; word-spacing: 0px;" class=""><span style="font-family: Arial, sans-serif; color: rgb(33, 33, 33);" class="">Business Assistant – Computer Science<span class="apple-converted-space"> </span></span><span style="color: rgb(33, 33, 33);" class=""><o:p class=""></o:p></span></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif; caret-color: rgb(33, 33, 33); font-variant-caps: normal; text-align: start; -webkit-text-stroke-width: 0px; word-spacing: 0px;" class=""><span style="font-family: Arial, sans-serif; color: rgb(33, 33, 33);" class="">The University of Chicago<span class="apple-converted-space"> </span></span><span style="color: rgb(33, 33, 33);" class=""><o:p class=""></o:p></span></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif; caret-color: rgb(33, 33, 33); font-variant-caps: normal; text-align: start; -webkit-text-stroke-width: 0px; word-spacing: 0px;" class=""><span style="font-family: Arial, sans-serif; color: rgb(33, 33, 33);" class="">5730 S Ellis Ave, JCL 212</span><span style="color: rgb(33, 33, 33);" class=""><o:p class=""></o:p></span></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif; caret-color: rgb(33, 33, 33); font-variant-caps: normal; text-align: start; -webkit-text-stroke-width: 0px; word-spacing: 0px;" class=""><span style="font-family: Arial, sans-serif; color: rgb(33, 33, 33);" class="">Chicago, IL 60637</span><span style="color: rgb(33, 33, 33);" class=""><o:p class=""></o:p></span></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif; caret-color: rgb(33, 33, 33); font-variant-caps: normal; text-align: start; -webkit-text-stroke-width: 0px; word-spacing: 0px;" class=""><span style="color: rgb(33, 33, 33);" class=""><a href="mailto:zaslam@uchicago.edu" title="mailto:zaslam@uchicago.edu" style="color: rgb(5, 99, 193); text-decoration: underline;" class=""><span style="font-family: Arial, sans-serif; color: rgb(0, 120, 215);" class="">zaslam@uchicago.edu</span></a><o:p class=""></o:p></span></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif; caret-color: rgb(33, 33, 33); font-variant-caps: normal; text-align: start; -webkit-text-stroke-width: 0px; word-spacing: 0px;" class=""><span style="font-family: Arial, sans-serif; color: rgb(33, 33, 33);" class="">Office: 773-702-2166</span><span style="color: rgb(33, 33, 33);" class=""><o:p class=""></o:p></span></div></div><span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: 400; 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; float: none; display: inline !important;" class="">_______________________________________________</span><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: 400; 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;" class=""><span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: 400; 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; float: none; display: inline !important;" class="">Colloquium mailing list - </span><a href="mailto:Colloquium@mailman.cs.uchicago.edu" style="color: rgb(5, 99, 193); text-decoration: underline; font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px;" class="">Colloquium@mailman.cs.uchicago.edu</a><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: 400; 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;" class=""><a href="https://mailman.cs.uchicago.edu/mailman/listinfo/colloquium" style="color: rgb(5, 99, 193); text-decoration: underline; font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px;" class="">https://mailman.cs.uchicago.edu/mailman/listinfo/colloquium</a><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: 400; 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;" class=""><span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: 400; 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; float: none; display: inline !important;" class="">_______________________________________________</span><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: 400; 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;" class=""><span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: 400; 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; float: none; display: inline !important;" class="">staff mailing list - </span><a href="mailto:staff@mailman.cs.uchicago.edu" style="color: rgb(5, 99, 193); text-decoration: underline; font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px;" class="">staff@mailman.cs.uchicago.edu</a><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: 400; 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;" class=""><a href="https://mailman.cs.uchicago.edu/mailman/listinfo/staff" style="color: rgb(5, 99, 193); text-decoration: underline; font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px;" class="">https://mailman.cs.uchicago.edu/mailman/listinfo/staff</a></div></blockquote></div><br class=""></body></html>