<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=Windows-1252">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<!--[if !mso]><style>v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style><![endif]--><style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
font-size:11.0pt;
font-family:"Calibri",sans-serif;
mso-ligatures:standardcontextual;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#0563C1;
text-decoration:underline;}
span.apple-converted-space
{mso-style-name:apple-converted-space;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;
font-family:"Calibri",sans-serif;
mso-ligatures:standardcontextual;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style>
</head>
<body lang="EN-US" link="#0563C1" vlink="#954F72" style="word-wrap:break-word">
<div class="WordSection1">
<p class="MsoNormal"><i><span style="font-size:10.0pt;font-family:"Times New Roman",serif;color:black">Department of Computer Science Seminar</span></i><span style="color:#212121"><o:p></o:p></span></p>
<p class="MsoNormal" style="caret-color: rgb(33, 33, 33);font-variant-caps: normal;orphans: auto;text-align:start;widows: auto;-webkit-text-size-adjust: auto;-webkit-text-stroke-width: 0px;word-spacing:0px">
<span style="font-size:10.0pt;font-family:"Times New Roman",serif;color:black"> </span><span style="color:#212121"><o:p></o:p></span></p>
<p class="MsoNormal" style="caret-color: rgb(33, 33, 33);font-variant-caps: normal;orphans: auto;text-align:start;widows: auto;-webkit-text-size-adjust: auto;-webkit-text-stroke-width: 0px;word-spacing:0px">
<b><span style="font-family:"Times New Roman",serif;color:black;letter-spacing:.15pt">Amy Greenwald</span></b><span style="font-family:"Times New Roman",serif;color:black;letter-spacing:.15pt"><br>
<b>Professor of Computer Science </b><br>
<b>Brown University </b></span><span style="color:#212121"><o:p></o:p></span></p>
<p class="MsoNormal" style="caret-color: rgb(33, 33, 33);font-variant-caps: normal;orphans: auto;text-align:start;widows: auto;-webkit-text-size-adjust: auto;-webkit-text-stroke-width: 0px;word-spacing:0px">
<b><span style="font-family:"Times New Roman",serif;color:black;letter-spacing:.15pt"> </span></b><span style="color:#212121"><o:p></o:p></span></p>
<p class="MsoNormal" style="caret-color: rgb(33, 33, 33);font-variant-caps: normal;orphans: auto;text-align:start;widows: auto;-webkit-text-size-adjust: auto;-webkit-text-stroke-width: 0px;word-spacing:0px">
<b><span style="font-family:"Times New Roman",serif;color:black;letter-spacing:.15pt">Monday, February 20th </span></b><span style="font-family:"Times New Roman",serif;color:black;letter-spacing:.15pt"><br>
<b>4:00pm - 5:00pm </b><br>
<b>In Person: John Crerar Library 298</b></span><span style="color:#212121"><o:p></o:p></span></p>
<p class="MsoNormal" style="caret-color: rgb(33, 33, 33);font-variant-caps: normal;orphans: auto;text-align:start;widows: auto;-webkit-text-size-adjust: auto;-webkit-text-stroke-width: 0px;word-spacing:0px">
<span style="font-family:"Times New Roman",serif;color:black"> </span><span style="color:#212121"><o:p></o:p></span></p>
<p class="MsoNormal" style="caret-color: rgb(33, 33, 33);font-variant-caps: normal;orphans: auto;text-align:start;widows: auto;-webkit-text-size-adjust: auto;-webkit-text-stroke-width: 0px;word-spacing:0px">
<b><span style="font-family:"Times New Roman",serif;color:#212121">Title: Learning in Simulation-Based Games</span></b><span style="color:#212121"><o:p></o:p></span></p>
<p class="MsoNormal" style="caret-color: rgb(33, 33, 33);font-variant-caps: normal;orphans: auto;text-align:start;widows: auto;-webkit-text-size-adjust: auto;-webkit-text-stroke-width: 0px;word-spacing:0px">
<span style="font-family:"Times New Roman",serif;color:#212121"> </span><span style="color:#212121"><o:p></o:p></span></p>
<p class="MsoNormal" style="caret-color: rgb(33, 33, 33);font-variant-caps: normal;orphans: auto;text-align:start;widows: auto;-webkit-text-size-adjust: auto;-webkit-text-stroke-width: 0px;word-spacing:0px">
<b><span style="font-family:"Times New Roman",serif;color:#212121">Abstract:</span></b><span style="color:#212121"><o:p></o:p></span></p>
<p class="MsoNormal" style="caret-color: rgb(33, 33, 33);font-variant-caps: normal;orphans: auto;text-align:start;widows: auto;-webkit-text-size-adjust: auto;-webkit-text-stroke-width: 0px;word-spacing:0px">
<span style="font-family:"Times New Roman",serif;color:#212121">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:#212121"><o:p></o:p></span></p>
<p class="MsoNormal" style="caret-color: rgb(33, 33, 33);font-variant-caps: normal;orphans: auto;text-align:start;widows: auto;-webkit-text-size-adjust: auto;-webkit-text-stroke-width: 0px;word-spacing:0px">
<span style="font-family:"Times New Roman",serif;color:#212121"> </span><span style="color:#212121"><o:p></o:p></span></p>
<p class="MsoNormal" style="caret-color: rgb(33, 33, 33);font-variant-caps: normal;orphans: auto;text-align:start;widows: auto;-webkit-text-size-adjust: auto;-webkit-text-stroke-width: 0px;word-spacing:0px">
<span style="font-family:"Times New Roman",serif;color:#212121">Joint Work with Bhaskar Mishra, Cyrus Cousins, Enrique Areyan-Viqueira, and Yasser Mohammad</span><span style="color:#212121"><o:p></o:p></span></p>
<p class="MsoNormal" style="caret-color: rgb(33, 33, 33);font-variant-caps: normal;orphans: auto;text-align:start;widows: auto;-webkit-text-size-adjust: auto;-webkit-text-stroke-width: 0px;word-spacing:0px">
<span style="font-family:"Times New Roman",serif;color:#212121"> </span><span style="color:#212121"><o:p></o:p></span></p>
<p class="MsoNormal" style="caret-color: rgb(33, 33, 33);font-variant-caps: normal;orphans: auto;text-align:start;widows: auto;-webkit-text-size-adjust: auto;-webkit-text-stroke-width: 0px;word-spacing:0px">
<b><span style="font-family:"Times New Roman",serif;color:#212121">Bio:</span></b><span style="color:#212121"><o:p></o:p></span></p>
<p class="MsoNormal" style="caret-color: rgb(33, 33, 33);font-variant-caps: normal;orphans: auto;text-align:start;widows: auto;-webkit-text-size-adjust: auto;-webkit-text-stroke-width: 0px;word-spacing:0px">
<span style="font-family:"Times New Roman",serif;color:#212121">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:#212121"><o:p></o:p></span></p>
<p class="MsoNormal" style="caret-color: rgb(33, 33, 33);font-variant-caps: normal;orphans: auto;text-align:start;widows: auto;-webkit-text-size-adjust: auto;-webkit-text-stroke-width: 0px;word-spacing:0px">
<span style="font-family:"Times New Roman",serif;color:#212121"> </span><span style="color:#212121"><o:p></o:p></span></p>
<p class="MsoNormal" style="caret-color: rgb(33, 33, 33);font-variant-caps: normal;orphans: auto;text-align:start;widows: auto;-webkit-text-size-adjust: auto;-webkit-text-stroke-width: 0px;word-spacing:0px">
<span style="font-family:"Times New Roman",serif;color:#212121"><img width="261" height="263" style="width:2.7187in;height:2.7395in" id="Picture_x0020_1" src="cid:image001.png@01D93F87.EFA51A90" alt="Image"></span><span style="color:#212121"><o:p></o:p></span></p>
<p class="MsoNormal" style="caret-color: rgb(33, 33, 33);font-variant-caps: normal;orphans: auto;text-align:start;widows: auto;-webkit-text-size-adjust: auto;-webkit-text-stroke-width: 0px;word-spacing:0px">
<span style="color:#212121"> <o:p></o:p></span></p>
<p class="MsoNormal" style="caret-color: rgb(33, 33, 33);font-variant-caps: normal;orphans: auto;text-align:start;widows: auto;-webkit-text-size-adjust: auto;-webkit-text-stroke-width: 0px;word-spacing:0px">
<span style="color:#212121"> <o:p></o:p></span></p>
<p class="MsoNormal" style="caret-color: rgb(33, 33, 33);font-variant-caps: normal;orphans: auto;text-align:start;widows: auto;-webkit-text-size-adjust: auto;-webkit-text-stroke-width: 0px;word-spacing:0px">
<b><span style="font-family:"Arial",sans-serif;color:#212121">Zainab Aslam</span></b><span style="color:#212121"><o:p></o:p></span></p>
<p class="MsoNormal" style="caret-color: rgb(33, 33, 33);font-variant-caps: normal;orphans: auto;text-align:start;widows: auto;-webkit-text-size-adjust: auto;-webkit-text-stroke-width: 0px;word-spacing:0px">
<span style="font-family:"Arial",sans-serif;color:#212121">Business Assistant – Computer Science<span class="apple-converted-space"> </span></span><span style="color:#212121"><o:p></o:p></span></p>
<p class="MsoNormal" style="caret-color: rgb(33, 33, 33);font-variant-caps: normal;orphans: auto;text-align:start;widows: auto;-webkit-text-size-adjust: auto;-webkit-text-stroke-width: 0px;word-spacing:0px">
<span style="font-family:"Arial",sans-serif;color:#212121">The University of Chicago<span class="apple-converted-space"> </span></span><span style="color:#212121"><o:p></o:p></span></p>
<p class="MsoNormal" style="caret-color: rgb(33, 33, 33);font-variant-caps: normal;orphans: auto;text-align:start;widows: auto;-webkit-text-size-adjust: auto;-webkit-text-stroke-width: 0px;word-spacing:0px">
<span style="font-family:"Arial",sans-serif;color:#212121">5730 S Ellis Ave, JCL 212</span><span style="color:#212121"><o:p></o:p></span></p>
<p class="MsoNormal" style="caret-color: rgb(33, 33, 33);font-variant-caps: normal;orphans: auto;text-align:start;widows: auto;-webkit-text-size-adjust: auto;-webkit-text-stroke-width: 0px;word-spacing:0px">
<span style="font-family:"Arial",sans-serif;color:#212121">Chicago, IL 60637</span><span style="color:#212121"><o:p></o:p></span></p>
<p class="MsoNormal" style="caret-color: rgb(33, 33, 33);font-variant-caps: normal;orphans: auto;text-align:start;widows: auto;-webkit-text-size-adjust: auto;-webkit-text-stroke-width: 0px;word-spacing:0px">
<span style="color:#212121"><a href="mailto:zaslam@uchicago.edu" title="mailto:zaslam@uchicago.edu"><span style="font-family:"Arial",sans-serif;color:#0078D7">zaslam@uchicago.edu</span></a><o:p></o:p></span></p>
<p class="MsoNormal" style="caret-color: rgb(33, 33, 33);font-variant-caps: normal;orphans: auto;text-align:start;widows: auto;-webkit-text-size-adjust: auto;-webkit-text-stroke-width: 0px;word-spacing:0px">
<span style="font-family:"Arial",sans-serif;color:#212121">Office: 773-702-2166</span><span style="color:#212121"><o:p></o:p></span></p>
</div>
</body>
</html>