TITLE:  Mean Field Equilibria of Dynamic Auctions with Learning

SPEAKER: Ramesh Johari

ABSTRACT:

We study learning in a dynamic setting where identical copies of a good are sold over time through a sequence of second price auctions. Each agent in the market has an 'unknown' independent private valuation which determines the distribution of the reward she obtains from the good; for example, in sponsored search settings, advertisers may initially be unsure of the value of a click. Though the induced dynamic game is complex, we simplify analysis of the market using an approximation methodology known as 'mean field equilibrium' (MFE). The methodology assumes that agents optimize only with respect to long run average estimates of the distribution of other players' bids.

We show a remarkable fact: in a mean field equilibrium, the agent has an optimal strategy where she bids truthfully according to a 'conjoint valuation'. The conjoint valuation is the sum of her current expected valuation, together with an overbid amount that is exactly the expected marginal benefit to one additional observation about her true private valuation. Under mild conditions on the model, we show that an MFE exists, and that it is a good approximation to a 'rational' agent's behavior as the number of agents increases. Formally, if every agent except one follows the MFE strategy, then the remaining agent's loss on playing the MFE strategy converges to zero as the number of agents in the market increases.

We conclude by discussing the implications of the auction format and design on the auctioneer's revenue. In particular, we establish a dynamic version of the revenue equivalence theorem, and discuss optimal selection of reserve prices in dynamic auctions.

This is joint work with Krishnamurthy Iyer and Mukund Sundararajan.

Bio:  Ramesh Johari is an Associate Professor at Stanford University and the Cisco Faculty Scholar in the School of Engineering, with a full-time appointment in the Department of Management Science and Engineering (MS&E), and courtesy appointments in the Departments of Computer Science (CS) and Electrical Engineering (EE). He is a member of the Operations Research group in MS&E, the Information Systems Laboratory in EE, and the Institute for Computational and Mathematical Engineering. He received an A.B. in Mathematics from Harvard (1998), a Certificate of Advanced Study in Mathematics from Cambridge (1999), and a Ph.D. in Electrical Engineering and Computer Science from MIT (2004).

He is the recipient of a British Marshall Scholarship (1998), First Place in the INFORMS George E. Nicholson Student Paper Competition (2003), the George M. Sprowls Award for the best doctoral thesis in computer science at MIT (2004), Honorable Mention for the ACM Doctoral Dissertation Award (2004), the Okawa Foundation Research Grant (2005), the MS&E Graduate Teaching Award (2005, 2010), the INFORMS Telecommunications Section Doctoral Dissertation Award (2006), and the NSF CAREER Award (2007). He has served on the program committees of ACM Electronic Commerce (2007, 2009-2011), ACM SIGCOMM (2006, 2011), IEEE Infocom (2007-2011), and ACM SIGMETRICS (2008-2009).