Algorithmic Market Design: Advertising Auctions and Convex Characterizations
Abstract
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 tradeoffs between objectives such as revenue and welfare. In
this talk, I'll discuss how these tradeoffs 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
tradeoffs 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 subgradients. 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.
Bio
Ian Kash is a researcher in the Systems and Networking and Machine Intelligence and Perception groups 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.