Online Algorithms for New Markets (...and a glimpse into the field of Internet Economics)

Aranyak Mehta, IBM Almaden Research Center

Search engine companies have revolutionized the way we use the Internet. Their dramatic revenues are supported by a different innovation: keyword based advertising. I will talk about this innovation, and show how it has an intimate link with classic matching problems. A new algorithmic technique (of tradeoff revealing family of LP’s) leads to an simple, intuitive (and optimal) algorithm for Adwords allocation.

This work fits within a broader theme of network and Internet economics: The algorithmic study of the economic activities that have emerged on the Internet. I will give an overview of the different research questions and applications in this area. I will also talk about a related question: how techniques from machine learning and game theory can be used in the optimal design of networks.

(This talk is based on three joint works with Deeparnab Chakrabarty, Gagan Goel, Amin Saberi, Umesh Vazirani and Vijay Vazirani)

Speaker Biography

Aranyak Mehta is a postdoctoral researcher at IBM’s Almaden Research Center in San Jose. He received his Ph.D. from Georgia Tech in July 2005. His interests lie in algorithms and their applications, and the interaction with Internet economics and game theory.