CS-ECON Seminar Series

A Market Model for Scheduling, with Applications to Cloud Computing

Speaker:Ruta Mehta
Date: Friday, March 25, 2016
Time: 12:00pm - 1:00pm
Location: 318 Gross Hall, Duke


We present a market for allocating and scheduling resources to agents who have specified budgets and need to complete specific tasks. Our market model is motivated by applications in cloud computing. Two important aspects required in this market are: (1) agents need specific amounts of each resource to complete their tasks, and (2) agents would like to complete their tasks as soon as possible. In incorporating these aspects, we arrive at a model that deviates substantially from market models studied so far in economics and theoretical computer science. Indeed, all known techniques developed to compute equilibria in markets in the last decade and half seem not to apply here. We give a polynomial time algorithm for computing an equilibrium using a new technique that is somewhat reminiscent of the ironing procedure used in the characterization of optimal auctions by Myerson. This is despite of the fact that the set of equilibrium prices could be non-convex; in fact it could have "holes". Additionally we show that the market satisfies first welfare theorem.

We also show that our market mechanism is incentive compatible when the agents only care about their flow time. A small modification to the payments, keeping the allocation the same, makes the entire mechanism incentive compatible for the setting in which agents want to first minimize flow time and subject to that, minimize their payments. This is complemented by showing impossibility of an incentive compatible mechanism in the quasi-linear model.

Joint work with Nikhil R. Devanur, Jugal Garg, Vijay V. Vazirani, and Sadra Yazdanbod


Dr. Ruta Mehta is an assistant professor in the Department of Computer Science at University of Illinois at Urbana-Champaign. Her research lies at the intersection of theoretical computer science, game theory, and mathematical economics, and their applications to evolution, dynamical systems and learning. She has worked on computability of equilibria, both market and Nash, under various settings, and also on understanding the impact of strategic behavior in multi-agent situations. In addition she has explored learning economic parameters through revealed preferences, fair-division, and genetic evolution under sexual reproduction.

She did her PhD from Indian Institute of Technology, Bombay, under the guidance of Prof. Milind Sohoni, and postdoc from Georgia Tech under supervision of Prof. Vijay V. Vazirani. She spent a semester at Simons Institute at UC Berkeley before joining UIUC. She won ACM India Doctoral Dissertation Award 2012. In 2014, she was conferred the Best Postdoctoral Research Award by CoC at Georgia Tech.

Hosted by:
Vince Conitzer