We consider “time-of-use” pricing as a technique for matching supply and demand of temporal resources
with the goal of maximizing social welfare. Relevant examples include energy, computing resources
on a cloud computing platform, and charging stations for electric vehicles, among many others.
A client/job in this setting has a window of time during which he needs service, and a particular value
for obtaining it. We assume a stochastic model for demand, where each job materializes with some
probability via an independent Bernoulli trial. Given a per-time-unit pricing of resources, any realized
job will first try to get served by the cheapest available resource in its window and, failing that, will try
to find service at the next cheapest available resource, and so on. Thus, the natural stochastic fluctuations
in demand have the potential to lead to cascading overload events. Our main result shows that setting
prices so as to optimally handle the expected demand works well: with high probability, when the actual
demand is instantiated, the system is stable and the expected value of the jobs served is very close to that
of the optimal offline algorithm.
Joint work with S. Chawla, N. Devanur, A. Holroyd, A. Karlin, J. Martin and B. Sivan