Stability of Service Under Time-of-Use Pricing

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