PhD Proposal: Optimization and Mechanism Design for Resource Management with Uncertainty

Many classic and fundamental problems in computer science and economy can be viewed as a resource management problem. Resource management is used to assign the available resources in an economic way, where the resource denotes an economic and productive factor required to accomplish an activity, or to achieve a desired outcome. Assigning tasks to machines in scheduling problems, assigning servers to queries in the k-server problem, budget distribution in competitions, and influence maximization problems are some classic and well-motivated instances of resource management problems.
In most realistic models, we are forced to make decisions in the presence of incomplete input. This is the source of uncertainty for an optimization algorithm/mechanism. There are different types of uncertainty. For example, in stochastic settings, we may have some random variables derived from some known/unknown distributions. In online settings, the complete input is not known in a-priori and pieces of the input become available sequentially; leaving the algorithm to make decisions only with partial data. In game theoretic settings, agents take actions without having complete knowledge of the other agents’ actions.
In this project, we intend to study fundamental resource management problems with uncertainty. We would like to consider online stochastic scheduling, online stochastic k-server, budget allocation for influence maximization in social networks, and optimal budget allocation in competitive games such as Colonel Blotto and Dueling games. We aim to study the hardness of such problems and provide efficient algorithms/mechanisms for them.
Examining Committee:
Chair: Dr. Mohammad Hajiaghayi
Dept. rep: Dr. Dana Nau
Member: Dr. Raghu Raghavan