Designing Ad Auctions: An Algorithmic Perspective

Опубликовано 6 сентября 2016, 5:47

Search engines, such as MSN, Google, and Yahoo, have revolutionized the use of the Internet by individuals. Their dramatic revenues are supported by a second revolution: in the way businesses advertise to consumers. I will talk about this lesser known revolution and several underlying computational problems it raises. In particular, I will talk about designing a mechanism for allocating ad space to advertisers based on their bids and budgets. This problem is an elegant generalization of the online bipartite matching problem. I will describe two optimal algorithms for this task, each achieving a competitive ratio of 1-1/e. The design of these algorithms is made possible by the new notion of tradeoff-revealing linear programs.