import matplotlib
if not hasattr(matplotlib.RcParams, "_get"):
matplotlib.RcParams._get = dict.get
4.5.1: Exercises#
The introduction used the interactive activity to show why activating every agent at every step is wasteful when most agents are idle. Here you will build that idea into a small, self-contained Mesa model and measure the payoff for yourself.
The model is deliberately simple, so that nothing distracts from the one idea that matters: scheduling an event for a known future moment, instead of checking every agent at every step. Everything below uses only standard Mesa, with no add-ons.
Important
For live code, launch Thebe by clicking on the in the toolbar. Your code edits are automatically saved in your browser. Use the button to export your progress to a file, to import a previously saved session, or to reset to the original code.
%pip install mesa==3.5.0
%pip install seaborn
%pip install networkx
Attention
This model is up-to-date with mesa version 3.5.0
4.5.1.1: A city of idle citizens#
Our model is a distilled version of the jailed-agent example from the introduction. A city has a fixed population of citizens. At each moment, a free citizen has a small chance of being arrested. An arrested citizen is jailed for a known number of steps, its term, and while jailed it does nothing at all: it simply waits for the moment of release, which is already known the instant it is arrested.
This is exactly the situation in which event scheduling shines: a jailed citizen is idle, yet its release time is known in advance. We will build the model twice:
first with incremental time, activating every citizen at every step;
then with event scheduling, where an arrest schedules a single release event and jailed citizens are left untouched until that event is due.
Both versions obey the same rules. Only their efficiency differs.
Before building either version of the model, it helps to picture a citizen as a small state machine. The cards below lay out the states a citizen can occupy, from the two in the base model to the cool-off state added later, together with the events that carry it between them.
Keep this picture in mind as you read the code: the incremental model checks a citizen in every state at every step, whereas event scheduling leaves it untouched until the moment it becomes free again.
4.5.1.1.1: Understand the incremental model#
In the incremental version the model advances by calling model.step() in a plain Python loop. Each step, every citizen is activated through self.agents.shuffle_do("step"), Mesa’s way of activating all agents in a random order.
A citizen’s step method does one of two things:
if it is free, it is arrested with probability
p_arrest, and if arrested it draws a random jail term and starts serving it;if it is jailed, it does nothing useful: it just decrements its remaining term by one, and is released when the term reaches zero.
That second case is the waste we are after. A jailed citizen is activated at every step only to subtract one from a counter. The model keeps a running total in self.activations, so we can measure exactly how much work is done.
from mesa import Model, Agent
class Citizen(Agent):
"""A citizen who is occasionally jailed and then waits for release."""
def __init__(self, model, p_arrest, max_term):
super().__init__(model)
self.p_arrest = p_arrest # chance of arrest per step while free
self.max_term = max_term # longest possible jail term
self.jailed = False
self.term_left = 0
def step(self):
self.model.activations += 1 # count every activation
if self.jailed:
# idle waiting: the only thing a jailed citizen does
self.term_left -= 1
if self.term_left <= 0:
self.jailed = False
elif self.random.random() < self.p_arrest:
self.jailed = True
self.term_left = self.random.randint(1, self.max_term)
class City(Model):
"""Incremental-time city: every citizen is activated at every step."""
def __init__(self, n=200, p_arrest=0.05, max_term=50, seed=None):
super().__init__(rng=seed)
self.activations = 0
for _ in range(n):
Citizen(self, p_arrest, max_term)
def step(self):
self.agents.shuffle_do("step")
steps = 100
city = City(n=200, max_term=50, seed=42)
for _ in range(steps):
city.step()
print(f"Incremental activations: {city.activations}")
print(f"That is exactly {len(city.agents)} citizens x {steps} steps.")
Incremental activations: 20000
That is exactly 200 citizens x 100 steps.
4.5.1.1.2: Add event scheduling#
Now the interesting version. Two things change.
First, the model keeps a set of the free citizens and, at each step, activates only those, not the jailed ones. Mesa provides AgentSet for exactly this kind of book-keeping; jailed citizens are removed from it and added back on release.
Second, and this is the heart of event scheduling, an arrest no longer starts a countdown. Instead it schedules a release event for the exact future moment when the term ends:
self.model.schedule_event(self.release, after=term)
schedule_event is built into every Mesa model. It places a one-off event on an internal, time-ordered queue; when the model’s clock reaches that time, Mesa calls self.release. Between arrest and release the citizen is never touched. We advance the model with model.run_for(steps), which lets Mesa manage the clock and fire events at the right moments, instead of us calling model.step() by hand.
Event scheduling replaces the tick-by-tick loop with a different one built around a queue of future events. Before reading the code, try assembling that loop from its shuffled steps.
from mesa.agent import AgentSet
class ScheduledCitizen(Agent):
"""A citizen who schedules its own release instead of counting down."""
def __init__(self, model, p_arrest, max_term):
super().__init__(model)
self.p_arrest = p_arrest
self.max_term = max_term
def step(self):
# only free citizens are ever stepped, so no "am I jailed?" check is needed
self.model.activations += 1
if self.random.random() < self.p_arrest:
term = self.random.randint(1, self.max_term)
self.model.free.discard(self) # stop activating it
self.model.schedule_event(self.release, after=term) # release it later
def release(self):
self.model.activations += 1
self.model.free.add(self) # back in circulation
class ScheduledCity(Model):
"""Event-scheduled city: jailed citizens are left untouched until release."""
def __init__(self, n=200, p_arrest=0.05, max_term=50, seed=None):
super().__init__(rng=seed)
self.activations = 0
citizens = [ScheduledCitizen(self, p_arrest, max_term) for _ in range(n)]
self.free = AgentSet(citizens, random=self.random)
def step(self):
self.free.shuffle_do("step") # only the free citizens
scheduled = ScheduledCity(n=200, max_term=50, seed=42)
scheduled.run_for(steps)
saving = 1 - scheduled.activations / city.activations
print(f"Event-driven activations: {scheduled.activations}")
print(f"Incremental activations: {city.activations}")
print(f"Event scheduling did {saving:.0%} less work for the same {steps} steps.")
Event-driven activations: 10028
Incremental activations: 20000
Event scheduling did 50% less work for the same 100 steps.
You have now built the model both ways: the incremental version that steps through time tick by tick, and the event-driven version that jumps from one scheduled event to the next. Before measuring how much time the second one saves, it helps to see the difference happen. The two towns below run side by side.
The point to carry into the next section is that event scheduling is not a different model, it is a faster way to run the same model: it spends effort only where something happens, so the more idle time there is, the more it saves.
4.5.1.2: How much computation does it save?#
The saving depends on how much time citizens spend idle. If arrests are rare and terms are short, almost everyone is active and there is little to skip. If terms are long, a large fraction of the city sits in jail at any moment, and event scheduling avoids activating all of them.
Let us make that precise by sweeping the maximum jail term from short to long, and measuring both the total activations and the wall-clock runtime of each scheme.
4.5.1.2.1: Sweep the jail term#
import time
import matplotlib.pyplot as plt
terms = [2, 10, 20, 40, 80, 160]
inc_activations, ev_activations = [], []
inc_runtime, ev_runtime = [], []
for max_term in terms:
# activations (one representative run of each scheme)
c = City(n=200, max_term=max_term, seed=7)
for _ in range(steps):
c.step()
inc_activations.append(c.activations)
s = ScheduledCity(n=200, max_term=max_term, seed=7)
s.run_for(steps)
ev_activations.append(s.activations)
# runtime (best of five, to reduce noise)
def time_incremental():
m = City(n=200, max_term=max_term, seed=1)
t0 = time.perf_counter()
for _ in range(steps):
m.step()
return time.perf_counter() - t0
def time_scheduled():
m = ScheduledCity(n=200, max_term=max_term, seed=1)
t0 = time.perf_counter()
m.run_for(steps)
return time.perf_counter() - t0
inc_runtime.append(1000 * min(time_incremental() for _ in range(5)))
ev_runtime.append(1000 * min(time_scheduled() for _ in range(5)))
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(11, 4.2))
ax1.plot(terms, inc_activations, "o-", color="#B3261E", label="Incremental")
ax1.plot(terms, ev_activations, "s-", color="#006B54", label="Event-driven")
ax1.set_xlabel("Maximum jail term (idle time)")
ax1.set_ylabel("Total agent activations")
ax1.set_title("Work done")
ax1.legend()
ax1.grid(alpha=0.3)
ax2.plot(terms, inc_runtime, "o-", color="#B3261E", label="Incremental")
ax2.plot(terms, ev_runtime, "s-", color="#006B54", label="Event-driven")
ax2.set_xlabel("Maximum jail term (idle time)")
ax2.set_ylabel("Runtime (ms)")
ax2.set_title("Wall-clock runtime")
ax2.legend()
ax2.grid(alpha=0.3)
fig.suptitle("The longer agents sit idle, the more event scheduling saves",
fontweight="bold")
fig.tight_layout()
plt.show()
The left panel shows the point directly. Incremental time does the same amount of work no matter what: a flat line at 200 x 100 = 20 000 activations, because it activates every citizen at every step regardless of whether anything happens to them. Event scheduling does less and less work as jail terms lengthen, because more citizens are idle, and idle citizens are simply skipped.
The right panel is more subtle, and more honest. Event scheduling is not free: keeping the event queue in order costs a little time. When jail terms are short, that overhead makes it slower than the plain loop. It only pays off once enough agents are idle for long enough to outweigh the book-keeping. Event scheduling is a tool with a sweet spot, not a free lunch.
You have now seen the two schemes run and measured the gap between them. The sort below checks that you can tell which scheme each property belongs to.
4.5.1.2.2: Average over repeated runs#
The run above used a single random seed, so it is just one possible history of the city. A different seed would arrest different citizens at different moments and give slightly different totals. Before trusting a measurement we should repeat it across several seeds and look at both the average and the spread. The incremental scheme needs no averaging: it activates every citizen at every step, so it always does exactly n × steps work regardless of the seed.
The run above used a single seed, so it tells only one of many possible stories. The questions below check why that matters before the code repeats the measurement across many seeds.
n × steps work by construction, identical for every seed, so it needs no averaging.In short, a stochastic result is only trustworthy once you have seen how much it varies from seed to seed.
import numpy as np
seeds = range(12) # twelve independent random histories
terms = [2, 10, 20, 40, 80, 160]
ev_mean, ev_lo, ev_hi = [], [], []
for max_term in terms:
runs = []
for sd in seeds:
s = ScheduledCity(n=200, max_term=max_term, seed=sd)
s.run_for(steps)
runs.append(s.activations)
runs = np.array(runs)
ev_mean.append(runs.mean())
ev_lo.append(runs.min())
ev_hi.append(runs.max())
incremental = 200 * steps # identical for every seed, by construction
plt.figure(figsize=(7, 4.2))
plt.fill_between(terms, ev_lo, ev_hi, color="#006B54", alpha=0.18,
label="Event-driven (min-max over 12 runs)")
plt.plot(terms, ev_mean, "s-", color="#006B54", label="Event-driven (mean)")
plt.axhline(incremental, color="#B3261E", ls="--", label="Incremental (always 20 000)")
plt.xlabel("Maximum jail term (idle time)")
plt.ylabel("Total agent activations")
plt.title("Averaging over runs: the saving is real, not a lucky seed")
plt.legend()
plt.grid(alpha=0.3)
plt.tight_layout()
plt.show()
4.5.1.2.3: Vary the arrest rate#
Idle time has two ingredients, not one. A citizen sits in jail for longer when terms are long (the sweep above), but more citizens are in jail at any one moment when arrests are frequent. Holding the term fixed at max_term=50, we can sweep the arrest chance instead and watch the saving grow as the streets empty into the jail.
rates = [0.01, 0.02, 0.05, 0.10, 0.20]
ev_by_rate = []
for p in rates:
runs = []
for sd in range(12):
s = ScheduledCity(n=200, p_arrest=p, max_term=50, seed=sd)
s.run_for(steps)
runs.append(s.activations)
ev_by_rate.append(np.mean(runs))
plt.figure(figsize=(7, 4.2))
plt.plot([100 * r for r in rates], ev_by_rate, "s-", color="#006B54",
label="Event-driven (mean of 12 runs)")
plt.axhline(200 * steps, color="#B3261E", ls="--", label="Incremental")
plt.xlabel("Arrest chance per step (%)")
plt.ylabel("Total agent activations")
plt.title("More frequent arrests leave more citizens idle to skip")
plt.legend()
plt.grid(alpha=0.3)
plt.tight_layout()
plt.show()
4.5.1.2.4: Find the break-even point#
The work saved is only half the story; the other half is whether that saving is worth the book-keeping. Keeping the event queue in time order costs a little on every arrest and release, and when jail terms are short there is barely any idle time to skip, so the plain loop can actually be faster. Sweeping short terms one by one lets us find the break-even point, the term length at which event scheduling finally overtakes the incremental loop.
terms_fine = list(range(1, 26))
inc_rt, ev_rt = [], []
def best_time(build, run, reps=5):
best = float("inf")
for _ in range(reps):
m = build()
t0 = time.perf_counter()
run(m)
best = min(best, time.perf_counter() - t0)
return 1000 * best # milliseconds
for mt in terms_fine:
inc_rt.append(best_time(lambda: City(n=200, max_term=mt, seed=1),
lambda m: [m.step() for _ in range(steps)]))
ev_rt.append(best_time(lambda: ScheduledCity(n=200, max_term=mt, seed=1),
lambda m: m.run_for(steps)))
crossover = next((mt for mt, i, e in zip(terms_fine, inc_rt, ev_rt) if e < i), None)
plt.figure(figsize=(7, 4.2))
plt.plot(terms_fine, inc_rt, "o-", color="#B3261E", label="Incremental")
plt.plot(terms_fine, ev_rt, "s-", color="#006B54", label="Event-driven")
if crossover is not None:
plt.axvline(crossover, color="#888", ls=":", label=f"break-even = {crossover}")
plt.xlabel("Maximum jail term (idle time)")
plt.ylabel("Runtime (ms)")
plt.title("Below the break-even term, queue overhead makes event scheduling slower")
plt.legend()
plt.grid(alpha=0.3)
plt.tight_layout()
plt.show()
print(f"Event scheduling becomes the faster option at about max_term = {crossover}.")
4.5.1.3: A richer city with cool-off and repeat offenders#
So far every citizen is identical and can be re-arrested the instant it is freed. Real populations are not like that, and the interesting question is whether event scheduling still helps once the model gains some structure. We add two behaviours:
a cool-off period: for a fixed number of steps after release, a citizen is left alone before it can be arrested again;
recidivism: the more often a citizen has already been arrested, the likelier the next arrest becomes.
Both are handled by the very same idea. A cool-off is just another stretch of known idle time, so release schedules a second event, end_cool_off, chaining one scheduled event to the next. Recidivism changes only how likely an arrest is, not how idleness is handled, so it costs nothing extra. Throughout, a citizen that is waiting, whether in jail or cooling off, is simply not in the active set and is never activated.
class RepeatOffenderCitizen(Agent):
"""A citizen that cools off after release and reoffends more with each arrest."""
def __init__(self, model, p_arrest, max_term, cool_off=15):
super().__init__(model)
self.base_p = p_arrest # arrest chance for a first-time offender
self.max_term = max_term
self.cool_off = cool_off
self.priors = 0 # number of previous arrests
@property
def p_arrest(self):
# every prior arrest raises the chance of the next one (capped at 0.9)
return min(0.9, self.base_p * (1 + self.priors))
def step(self):
self.model.activations += 1
if self.random.random() < self.p_arrest:
self.priors += 1
term = self.random.randint(1, self.max_term)
self.model.free.discard(self) # jailed: stop activating
self.model.schedule_event(self.release, after=term) # release, scheduled
def release(self):
self.model.activations += 1
# not free yet: serve a cool-off, scheduled as a second, chained event
self.model.schedule_event(self.end_cool_off, after=self.cool_off)
def end_cool_off(self):
self.model.activations += 1
self.model.free.add(self) # finally back in circulation
class RicherCity(Model):
"""Event-scheduled city whose citizens cool off and reoffend."""
def __init__(self, n=200, p_arrest=0.03, max_term=50, cool_off=15, seed=None):
super().__init__(rng=seed)
self.activations = 0
citizens = [RepeatOffenderCitizen(self, p_arrest, max_term, cool_off)
for _ in range(n)]
self.free = AgentSet(citizens, random=self.random)
def step(self):
self.free.shuffle_do("step")
4.5.1.3.1: Test whether the richer model changes the result#
Adding structure needed no new machinery: every “wait” is a scheduled event, and idle citizens are never polled. Because the cool-off adds even more idle time on top of the jail term, event scheduling should save even more than before. The incremental baseline is unmoved: a plain loop still activates all n citizens every step, whatever they are doing, so it always does n × steps work. The table below sweeps the cool-off length and reports how much work the event-driven city avoids.
incremental = 200 * steps # a plain loop always activates everyone, every step
print("cool_off | event-driven activations | work saved vs incremental")
print("-" * 58)
for cool_off in [0, 5, 15, 30]:
runs = []
for sd in range(12):
m = RicherCity(n=200, p_arrest=0.03, max_term=50, cool_off=cool_off, seed=sd)
m.run_for(steps)
runs.append(m.activations)
mean_act = sum(runs) / len(runs)
print(f"{cool_off:>8} | {mean_act:>24,.0f} | {1 - mean_act / incremental:>17.0%}")
The longer the cool-off, the more time each citizen spends out of circulation, and the more activations event scheduling skips. Recidivism sharpens the effect: repeat offenders spend ever longer stretches jailed and cooling off, so they leave the active set for longer and longer. None of this required touching the scheduling logic, which is the real lesson. Once a behaviour has a known future time, whether it is jail, a cool-off, sleep, travel or recovery, it can be scheduled instead of polled, and heterogeneous, data-like behaviour costs nothing extra.
Exercises#
Now make the model your own.
Exercise 1: quantify the speed-up#
Using the two classes above, measure the runtime of the incremental and event-scheduled versions at a single setting (for example n=200, max_term=50, over steps=100). Time each with time.perf_counter() and report the ratio.
How much faster, or slower, is the event-scheduled version at this setting?
Increase
max_termto 200 and repeat. Which way does the ratio move, and why?
Hint
The saving comes from jailed citizens, who under incremental time are activated every step only to decrement a counter. The longer the jail term, the larger the idle population, and the more event scheduling avoids. Watch the queue overhead at very short terms, where scheduling can actually be slower.
Solution
At short-to-moderate terms the two are close, and event scheduling can even be slower because of the cost of keeping the event queue ordered. As max_term grows, a larger fraction of the city is jailed at any moment, so the event-scheduled version activates far fewer agents and pulls clearly ahead.
import time
def timed(build, run):
m = build()
t0 = time.perf_counter()
run(m)
return time.perf_counter() - t0
for max_term in [50, 200]:
inc = timed(lambda: City(n=200, max_term=max_term, seed=1),
lambda m: [m.step() for _ in range(100)])
ev = timed(lambda: ScheduledCity(n=200, max_term=max_term, seed=1),
lambda m: m.run_for(100))
print(f"max_term={max_term:>3}: incremental {inc*1000:.1f} ms, "
f"event-driven {ev*1000:.1f} ms, speed-up {inc/ev:.2f}x")
The speed-up rises with max_term, because idle time is exactly what event scheduling removes.
# answer here
Exercise 2: a rehabilitation programme#
The richer city above lets offenders reoffend ever more easily, with no way back. Add a rehabilitation programme: once a citizen has been free and clean for rehab steps after a cool-off, its record is wiped (priors returns to 0), lowering its arrest chance again. Implement the “clean for rehab steps” wait as another scheduled event, so a rehabilitating citizen is still never activated while it waits.
Extend
RepeatOffenderCitizenso thatend_cool_offschedules agraduateeventrehabsteps later, andgraduateresetspriors, but only if the citizen has stayed free in the meantime.Does rehabilitation raise or lower the total number of activations? Think about the two competing effects before you measure.
Hint
The pattern is the same chaining you have already seen: end_cool_off schedules graduate after rehab steps. The only new wrinkle is the guard, when graduate finally fires the citizen may have been re-arrested in the meantime, so reset priors only if it is currently free (self in self.model.free). Rehabilitation has two opposing effects on activations: resetting priors lowers future arrest chances (fewer arrests, so more agents active each step), but every graduate call is itself an activation.
Solution
Chain a third event after the cool-off, and guard it so an already re-arrested citizen is not wrongly wiped clean:
class RehabCitizen(RepeatOffenderCitizen):
def __init__(self, model, p_arrest, max_term, cool_off=15, rehab=40):
super().__init__(model, p_arrest, max_term, cool_off)
self.rehab = rehab
def end_cool_off(self):
super().end_cool_off() # back in circulation
self.model.schedule_event(self.graduate, after=self.rehab)
def graduate(self):
self.model.activations += 1
if self in self.model.free: # stayed clean since release?
self.priors = 0 # a fresh record
class RehabCity(Model):
def __init__(self, n=200, p_arrest=0.03, max_term=50, cool_off=15, rehab=40, seed=None):
super().__init__(rng=seed)
self.activations = 0
citizens = [RehabCitizen(self, p_arrest, max_term, cool_off, rehab)
for _ in range(n)]
self.free = AgentSet(citizens, random=self.random)
def step(self):
self.free.shuffle_do("step")
for rehab in [10, 40, 100]:
m = RehabCity(rehab=rehab, seed=1)
m.run_for(steps)
print(f"rehab={rehab:>3}: {m.activations} activations")
Rehabilitation usually lowers total activations: keeping arrest chances from spiralling means fewer arrests overall, and each avoided arrest removes an active citizen for a whole jail-plus-cool-off spell, while the extra graduate activations are few by comparison. The guard matters: without it, a citizen re-arrested during its clean stretch would be wiped clean while still in jail.
# answer here
Exercise 3: when is event scheduling worth it?#
In one or two sentences, describe a system met in this book, or elsewhere, in which most agents are idle most of the time, and explain why event scheduling would help there. Then name a system in which it would help little, and explain why.
Hint
Event scheduling pays off when activations are dominated by idle waiting with a known end time, such as jail, sleep, travel, or recovery. It helps little when almost every agent must act at almost every step, because then there are few idle activations to skip, and the queue overhead (the right panel above) is not repaid.
Exercise 4: does population size change the saving?#
The city above always holds 200 citizens. Does the proportion of work that event scheduling saves depend on how big the city is? Run ScheduledCity for n in [50, 100, 200, 400, 800] at a fixed max_term, and for each one compute the saving fraction 1 - activations / (n * steps). Plot or print the fraction against n.
Is the saving fraction roughly flat in
n, or does it trend up or down?Explain what that says about where the saving comes from.
Hint
The incremental baseline for a city of n citizens is exactly n * steps activations. The saving fraction depends on the share of citizens that are idle at any moment, which is set by the arrest rate and term length per citizen, not by how many citizens there are. Expect the fraction to stay roughly constant while the absolute numbers scale with n.
Solution
for n in [50, 100, 200, 400, 800]:
s = ScheduledCity(n=n, max_term=50, seed=1)
s.run_for(steps)
frac = 1 - s.activations / (n * steps)
print(f"n={n:>4}: saving fraction {frac:.0%}")
The saving fraction is essentially flat: doubling the population doubles both the work done and the work saved, leaving the proportion unchanged. The saving comes from the fraction of time each citizen is idle, a per-citizen property, not from the size of the crowd.
# answer here
Completion and reflection#
Before you finish, confirm that you can:
Verify that incremental and event-scheduled versions represent the same mechanism.
Measure the saving across repeated runs rather than reporting one timing.
Locate a condition where event scheduling helps little and explain why.
Identify another mostly idle system where event scheduling would be appropriate.