The notion of a market has undergone a paradigm shift with the Internet -- totally new and highly successful markets have been defined and launched by Internet companies such as Google, Yahoo!, Amazon, MSN and Ebay. This, and the availability of massive computational power for running these markets in a centralized or distributed manner, has motivated an algorithmic study of markets. This is the primary focus of the PI's research. The PI's research also involves work on some fundamental open problems in the theory of algorithms -- determining the integrality gap of the bidirected cut relaxation for the metric Steiner tree problem and studying the complexity of design problems arising from counting problems.
The work on algorithms for markets involves handling the case of concave utility functions, developing distributed models and algorithms for computing market equilibria, obtaining algorithmically-amenable market models for some of the new markets, and developing an algorithm for the Adwords problem assuming a stochastic arrival model for the queries.
This research will contribute to the Primary Priority Area, Advances in Science and Engineering (ASE), and will promote Economic Prosperity and Vibrant Civil Society (ECS). Its broader impacts involve the training of graduate students and the dissemination of research results via papers, courses, lectures and workshops.
