Research Projects

Many practical applications like demand response in smart grids, crowdsourcing, sponsored search auction warrants the use of game theory along with the machine learning solutions. Through this project, I want to develop the mathematical theory which characterizes and thus helps in designing robust and efficient combinatorial Multi-Armed Bandit (MAB) mechanisms which appears in all the above applications. Designing combinatorial MAB mechanisms is hard in two ways: 1) One needs to solve the combinatorial optimization problem 2) Agents have interdependent utility functions thus making it harder to satisfy game theoretic constraints. In this project, the goal will be to characterize and design combinatorial multi-armed bandit mechanisms in several applications where at each time, combination of agents need to be selected and paid in such a way so as to elicit their private properties truthfully through solving a combinatorial optimization problem each time. In several applications, certain properties of the problems are helpful. One such property could be submodular property, where greedy solutions give good approximation guarantees. Researchers have mainly focused on single-pull multi-armed bandit problems, where generally utility of one agent does not depend on the other agent as long as he is getting selected. Combinatorial multi-armed bandit mechanism design is a tremendously hard problem as the utilities of the agents become interdependent to each other. There exists characterization results and impossibility results which bounds the inefficiency due to the strategic nature of the problem. However, no such characterization result exists when the problem is combinatorial.