and all epochs benefit similarly from sprinting. When an
agent cannot distinguish between epochs, she sets a low
threshold and sprints for every epoch. In effect, for such
applications, E-T produces a greedy equilibrium.
6. 3 Sprinting strategies
Figure 7 uses density plots for two representative applications, Linear Regression and PageRank, to show how often and
how much their tasks benefit from sprinting. Linear Regression
presents a narrower distribution and performance gains
from sprinting vary in a band between 3× and 5×. In contrast,
PageRank’s performance gains can often exceed 10×.
The coordinator uses density plots to optimize threshold
strategies. Linear Regression’s strategy is aggressive and uses a
low threshold that often induces sprints. This strategy arises
from its relatively low variance in performance gains. If sprinting’s benefits are indistinguishable across tasks and epochs,
an agent sprints indiscriminately and at every opportunity.
PageRank’s strategy is more nuanced and uses a high threshold, which cuts her bimodal distribution and implements
judicious sprinting. She sprints for tasks and epochs that
benefit most (i.e., those that see performance gains greater
Figure 8 illustrates diversity in agents’ strategies by
reporting their propensities to sprint. Linear Regression and
Correlation’s narrow density functions and low thresholds
cause these applications to sprint at every opportunity. The
NaiveDecisionGradient SVM LinearKmeans ALS CorrelationPagerank CCTriangle
Figure 6. Performance, measured in tasks per second and
normalized against greedy, for a single application type.
0 5 10 15
Figure 7. Probability density for sprinting speedups.
NaiveDecisionGradient SVMLinearKmeans ALS Correlation Pagerank CCTriangle
Figure 8. Probability of sprinting. Greedy Exponential Equilibrium Cooperative
Active (not sprinting)
Figure 5. Percentage of time spent in agent states for a representative
application, Decision Tree.
majority of applications, however, resemble PageRank with
higher thresholds and judicious sprints.
6. 4 Equilibrium versus cooperation
Equilibrium thresholds are robust to strategic behavior and
perform well, but cooperative thresholds can perform even
better. The sprinting game’s equilibrium delivers 90% of the
performance from cooperation because the penalties from
non-cooperative behavior are low. Figure 9 shows how efficiency falls as recovery from power emergencies become
increasingly expensive. Recall that pr is the probability an
agent in recovery stays in that state.
The sprinting game fails when an emergency requires indefinite recovery and pr is one. This game has no equilibrium that
avoids tripping the breaker and triggering indefinite recovery.
If a strategic agent were to observe system dynamics that avoid
tripping the breaker, which means Ptrip is zero, she would realize
that other agents have set high thresholds to avoid sprints. Her
best response would be lowering her threshold and sprinting
more often. Others would behave similarly and drive Ptrip
higher. In equilibrium, Ptrip would rise above zero and agents
would eventually trip the breaker, putting the system into
indefinite recovery. Thus, selfish agents would produce inefficient equilibria—the Prisoner’s Dilemma in which each
agent’s best response performs worse than a cooperative one.
The Folk theorem guides agents to a more efficient equilibrium by punishing agents whose responses harm the system.
The coordinator would assign agents the best cooperative
thresholds to maximize system performance from sprinting.
When an agent deviates, she is punished such that