Algorithmic Market Design: Advertising Auctions and Convex Characterizations

Thursday, March 31, 2016 11:00 am - 12:00 pm EDT (GMT -04:00)


          Ian A. Kash, Microsoft Research Canada, United Kingdom

Invited by Professor Krzysztof Czarnecki



Markets are a powerful tool for producing desirable outcomes in an engineered system.  As computers allow us to build new and more complex markets, we need algorithmic tools to understand and improve them.  In this talk I'll discuss two recent lines of work in this space.

Advertising is the main source of revenue for search engines such as Bing and Google.  Decisions about how to which ads to show where impose trade-offs between objectives such as revenue and welfare.  In this talk, I'll discuss how these trade-offs should be made, beginning with a new ranking algorithm based on the revenue-optimal auction that uses a reserve price to change the way ads are ranked, not merely as a minimum bid.  From there, I'll discuss the optimal way to make such trade-offs in general and evaluate it using numerical simulations and Bing data.

Our tools to understand auctions rely on characterization theorems regarding convex functions and their sub gradients.  Similar characterizations arise in applications in statistics, finance, and machine learning.  I'll present a unifying framework that brings the characterizations from these disparate domains together, and discuss some applications to machine learning.


Ian Kash is a researcher in the Networks, Economics, and Algorithms group at Microsoft Research in Cambridge, UK. Previously he was a postdoctoral research fellow at the Center for Research on Computation and Society at Harvard University advised by David Parkes. He received his Ph.D. from Cornell University, where he was advised by Eric Friedman and Joe Halpern.