Bayesian Implementation in Auctions

The problem of designing auctions to maximize the revenue of the auctioneer and/or the social welfare has been an extensively studied problem in game theory. The celebrated result of Myerson, which contributed to his Nobel Prize in Economics, puts forth a mechanism that maximizes revenue for the auctioneer when the participants are truthful. This result has been mimicked in various settings and under numerous assumptions. I am currently working on the problem where the auctioneer is ignorant and the sellers have arbitrarily correlated knowledge distributions.

• Chetan Rao, Bayesian Implementation in Crowdsourced Auctions, Research Proposal, 2012. [link]

Mechanisms for Prediction Markets

Prediction markets (also known as information markets) address the issue of information aggregation and are useful to measure the likelihood of future events. The recent success of Iowa Electronic Market (IEM) in predicting the winner of US presidential elections influenced the technology giants such as Google, Microsoft and Yahoo! to setup internal prediction markets to accurately estimate product sales and other parameters of interest. This has sparkled a growing trend towards research in prediction markets.

• Chetan Rao, Pranav Chachra, Rohith DV and Y. Narahari, Multi-round wagering mechanisms for Prediction Markets, Technical report, 2010.

Space Complexity of Matchings in Graphs

Analysing the space complexity of certain problems can help in assessing the relations between different complexity classes. As a part of my undergraduate major thesis, I worked on the space complexity of Matching problem in graphs. We classified the problem in the non-deterministic logspace class (NL). Further, we tried to check if the problem lies in deterministic logspace (L) by reducing the matching problem to a reachability problem. Owing to Reingold's result, Undirected ST-connectivity in log-space (STOC 2005), the matching problem can be classified to be in deterministic logspace (L) if a successful reduction can be inferred. This, inturn, can cause a breakthrough in complexity theory, if true.

• Chetan Rao and Nithin Varma, A study of Matchings in Graphs, Undergraduate thesis, 2011. [link]

Placement Algorithm for Virtual Machines

In today's world, with the increase in mechanization, power has become a scarce resource. With the use of virtualization and availability of high network bandwidth, cloud computing has a vital role to play in the modern highly connected dense networks. Underneath this layer of abstraction lies massive data centers which need to be optimized for power usage. Our project concentrated on optimizing power consumption in big data centers and showed some promising results.

• Umesh Bellur, Chetan Rao and Madhu Kumar SD, Optimal Placement Algorithm for Virtual Machines, ArXiv report, 2010. [link]

Approximation Algorithm for Vector Bin Packing

Bin Packing is a very interesting problem in it's own right both systemically and theoretically. It is not only widely applicable in the industry but also one of the celebrated challenges in the theoretical forefront. Many interesting variants of the problems have been exposed and research is currently being pursued in this area. The approximation guarantees have not been very promising nor practical as many modified versions of simplistic heuristics outperform the approximation algorithms in most cases. Our result mainly aimed at achieving better & efficient solutions for most cases of the problem.

• Chetan Rao, Improved approximation bounds for Vector Bin Packing, ArXiv report, 2010. [link]