Markov chain that describes each agent’s behavior. As agents
play their strategies, the Markov chain converges to a station-
ary distribution in which each agent is active with probability
pA. Given N agents, the expected number of sprinters is
Given the expected number of sprinters, the game
updates the probability of tripping the breaker according to
its trip curve (e.g., Figure 2).
Ptrip may change u T and nS, which may produce a new . If
Ptrip = , then agents are playing optimized strategies that
produce an equilibrium.
4. 4 Finding the equilibrium
When the game begins, agents make initial assumptions
about population behavior and the probability of tripping
the breaker. Agents optimize their strategies in response to
population behavior. Strategies produce sprints that affect
the probability of tripping the breaker. Over time, population behavior and agent strategies converge to a stationary
distribution. The game is in equilibrium if the following
• Given tripping probability Ptrip, the sprinting strategy
dictated by threshold uT is optimal and solves the
Bellman equation in Equations ( 1)–( 3).
• Given sprinting strategy u T, the probability of tripping
the circuit breaker is Ptrip and is calculated by Equations
( 8)–( 10).
In equilibrium, every agent plays her optimal strategy and
no agent benefits when deviating from her strategy. In practice, the coordinator in the management framework finds
and maintains an equilibrium with a mix of offline analysis
and online play.
Offline analysis. Agents sample epochs and measure utility from sprinting to produce a density function f(u), which
characterizes how often an agent sees utility u from sprinting. The coordinator collects agents’ density functions, analyzes population dynamics, and tailors sprinting strategies
for each agent. Finally, the coordinator assigns optimized
strategies to support online sprinting decisions.
Algorithm 1 describes the coordinator’s offline analysis.
It initializes the probability of tripping the breaker. Then, it
iteratively analyzes population dynamics to find an equilibrium. Each iteration proceeds in three steps. First, the coordinator optimizes sprinting threshold uT by solving the
dynamic program defined in Equations ( 1)–( 7). Second, it
estimates the number of sprinters according to Equation ( 9).
Finally, it updates the probability of tripping the breaker
according to Equation ( 10). The algorithm terminates when
thresholds, number of sprinters, and tripping probability
Value in active state. An action’s value depends on benefits in the current epoch plus the discounted value from
future epochs. Suppose an agent in the active state decides
to sprint. Her value from sprinting is her immediate utility u
plus her discounted future utility. When she sprints, future
utility is calculated for the cooling state V (C) or the recovery
state V (R) when her sprint trips the breaker.
However, an agent who does not sprint will remain in the
active state unless other sprinting agents trip the circuit
breaker and require recovery.
V (A) denotes an agent’s expected value from being in the
active state. The game profiles an application and its time-varying computational phases to obtain a density function
f(u), which characterizes how often an agent derives utility u
from sprinting. With this density, the game estimates
Value in cooling and recovery states. An active agent transitions into cooling and recovery states when she and/or others sprint.
Parameters pc and pr are technology-specific probabilities of
an agent in cooling and recovery states staying in those
states. The game tunes these parameters to reflect the time
required for chip cooling after a sprint and for rack recovery
after a power emergency.
Threshold strategy. An agent should sprint if her utility
from doing so is greater than not. Equation ( 7), which follows from Equations ( 2) and ( 3), states that an agent should
sprint if her utility u is greater than her optimal threshold for
sprinting u T. Applying this strategy in every epoch maximizes
expected value across time in the repeated game.
4. 3 Characterizing the sprint distribution
Given threshold u T, an agent estimates the probability that
she sprints, ps, in a given epoch.
The probabilities of sprinting (ps) and cooling (pc) define a