Designing Ad Auctions: An Algorithmic Perspective

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.

Speaker Details

Amin Saberi received his PhD in 2004 from the College of Computing in Georgia Tech. He was a post doc in the theory group in Microsoft Research. He is currently an assistant professor in Stanford University.He is interested in the design and analysis of efficient algorithms especially in the area of algorithmic game theory and approximation algorithms. His interests also include modeling, design, and algorithmic analysis of large-scale complex networks such as the Internet, WWW, or peer-to-peer networks.

Date:
Speakers:
Amin Saberi
Affiliation:
Stanford University
    • Portrait of Jeff Running

      Jeff Running