marimo-team/marimo-learn
3
1# /// script2# requires-python = ">=3.13"3# dependencies = [4# "altair",5# "asimpy",6# "marimo",7# "polars==1.24.0",8# ]9# ///10 11import marimo12 13__generated_with = "0.20.4"14app = marimo.App(width="medium")15 16 17@app.cell(hide_code=True)18def _():19 import marimo as mo20 import math21 import random22 23 import altair as alt24 import polars as pl25 26 from asimpy import Environment, Process27 28 return Environment, Process, alt, math, mo, pl, random29 30 31@app.cell(hide_code=True)32def _(mo):33 mo.md(r"""34 # Braess's Paradox35 36 ## *Adding a Road Makes Traffic Worse*37 38 A city has two routes from source $S$ to destination $T$:39 40 - **Top route** $S \to A \to T$: link $SA$ is congestion-dependent; link $AT$ has a fixed travel time.41 - **Bottom route** $S \to B \to T$: link $SB$ has a fixed travel time; link $BT$ is congestion-dependent.42 43 The network is symmetric. A city planner proposes adding a new shortcut link $A \to B$ with near-zero travel time, creating a third route $S \to A \to B \to T$. To her surprise, adding the shortcut makes everyone's travel time longer at the selfish-routing Nash equilibrium.44 45 ### Without the shortcut46 47 Both routes are symmetric. In equilibrium, traffic splits evenly. If $N/2$ drivers use each route and the congested links have delay $\alpha \cdot n$ (where $n$ is the number of cars):48 49 $$t_{\text{top}} = \frac{N}{2}\alpha + c = t_{\text{bottom}}$$50 51 ### With the shortcut $A \to B$52 53 Each driver thinks, "Link $AB$ is free; I can use $SA$, slip across to $B$, then take $BT$ instead of the slow constant link $AT$." All $N$ drivers make this choice. The Nash equilibrium has everyone on $S \to A \to B \to T$:54 55 $$t_{\text{shortcut}} = N\alpha + \varepsilon + N\alpha = 2N\alpha + \varepsilon$$56 57 Since $2N\alpha > \frac{N}{2}\alpha + c$ for typical parameters, travel times *increase* after the road is added. This is the paradox: individually rational decisions produce a collectively worse outcome. The ratio of Nash equilibrium cost to the socially optimal cost is called the *[price of anarchy](https://en.wikipedia.org/wiki/Price_of_anarchy)*.58 59 [Braess's paradox](https://en.wikipedia.org/wiki/Braess%27s_paradox) is not theoretical. Seoul, Stuttgart, and New York all observed traffic *improvements* after closing roads. Conversely, new roads in highly congested networks have sometimes worsened average travel times.60 """)61 return62 63 64@app.cell(hide_code=True)65def _(mo):66 mo.md(r"""67 ## Implementation68 69 The simulation maintains a shared `LinkCounts` object tracking how many cars are currently on each link. Each `Car` process:70 71 1. Observes current link counts and computes expected travel time for each available route.72 2. Greedily picks the route with minimum expected time.73 3. Traverses each link in sequence, incrementing the count on entry and decrementing on exit; the delay is fixed at the count observed on entry.74 75 Two runs are compared: one with only the top and bottom routes, one with the $AB$ shortcut added. The simulation uses a probabilistic [logit](https://en.wikipedia.org/wiki/Logit) choice rule so that convergence to Nash equilibrium is smooth rather than instant.76 """)77 return78 79 80@app.cell(hide_code=True)81def _(mo):82 n_rounds_slider = mo.ui.slider(83 start=10,84 stop=200,85 step=10,86 value=80,87 label="Number of rounds",88 )89 90 beta_slider = mo.ui.slider(91 start=0.1,92 stop=2.0,93 step=0.1,94 value=0.5,95 label="Sensitivity (β)",96 )97 98 seed_input = mo.ui.number(99 value=192,100 step=1,101 label="Random seed",102 )103 104 run_button = mo.ui.run_button(label="Run simulation")105 106 mo.vstack([107 n_rounds_slider,108 beta_slider,109 seed_input,110 run_button,111 ])112 return beta_slider, n_rounds_slider, seed_input113 114 115@app.cell116def _(beta_slider, n_rounds_slider, seed_input):117 N_ROUNDS = int(n_rounds_slider.value)118 BETA = float(beta_slider.value)119 SEED = int(seed_input.value)120 N_DRIVERS = 4000121 CAPACITY = 100.0122 CONST_DELAY = 45.0123 return BETA, CAPACITY, CONST_DELAY, N_DRIVERS, N_ROUNDS, SEED124 125 126@app.cell127def _(CAPACITY, CONST_DELAY):128 def route_times(n_top, n_bot, n_short):129 n_sa = n_top + n_short130 n_bt = n_bot + n_short131 t_top = n_sa / CAPACITY + CONST_DELAY132 t_bot = CONST_DELAY + n_bt / CAPACITY133 t_short = n_sa / CAPACITY + n_bt / CAPACITY134 return t_top, t_bot, t_short135 136 return (route_times,)137 138 139@app.cell140def _(BETA, math):141 def logit_split(times):142 vals = [math.exp(-BETA * t) for t in times]143 total = sum(vals)144 return [v / total for v in vals]145 146 return (logit_split,)147 148 149@app.cell150def _(N_DRIVERS, N_ROUNDS, Process, logit_split, route_times):151 class RoutingGame(Process):152 def init(self, has_shortcut, history):153 self.has_shortcut = has_shortcut154 self.history = history155 self._n_top = N_DRIVERS // 2156 self._n_bot = N_DRIVERS - N_DRIVERS // 2157 self._n_short = 0158 159 async def run(self):160 for _ in range(N_ROUNDS):161 await self.timeout(1.0)162 t_top, t_bot, t_short = route_times(self._n_top, self._n_bot, self._n_short)163 if self.has_shortcut:164 probs = logit_split([t_top, t_bot, t_short])165 self._n_top = round(N_DRIVERS * probs[0])166 self._n_bot = round(N_DRIVERS * probs[1])167 self._n_short = N_DRIVERS - self._n_top - self._n_bot168 else:169 probs = logit_split([t_top, t_bot])170 self._n_top = round(N_DRIVERS * probs[0])171 self._n_bot = N_DRIVERS - self._n_top172 self._n_short = 0173 t_top2, t_bot2, t_short2 = route_times(self._n_top, self._n_bot, self._n_short)174 mean_t = (175 self._n_top * t_top2 + self._n_bot * t_bot2 + self._n_short * t_short2176 ) / N_DRIVERS177 self.history.append({178 "round": self.now,179 "n_top": self._n_top,180 "n_bot": self._n_bot,181 "n_short": self._n_short,182 "t_top": t_top2,183 "t_bot": t_bot2,184 "t_short": t_short2,185 "mean": mean_t,186 })187 188 return (RoutingGame,)189 190 191@app.cell192def _(Environment, RoutingGame):193 def simulate(has_shortcut):194 history = []195 env = Environment()196 RoutingGame(env, has_shortcut, history)197 env.run()198 return history199 200 return (simulate,)201 202 203@app.cell204def _(CAPACITY, CONST_DELAY, N_DRIVERS, SEED, pl, random, simulate):205 random.seed(SEED)206 hist_no = simulate(has_shortcut=False)207 hist_yes = simulate(has_shortcut=True)208 df_no = pl.DataFrame(hist_no)209 df_yes = pl.DataFrame(hist_yes)210 eq_no = hist_no[-1]["mean"]211 eq_yes = hist_yes[-1]["mean"]212 n_half = N_DRIVERS / 2213 t_theory_no = n_half / CAPACITY + CONST_DELAY214 t_theory_yes = N_DRIVERS / CAPACITY + N_DRIVERS / CAPACITY215 return df_no, df_yes, eq_no, eq_yes, t_theory_no, t_theory_yes216 217 218@app.cell(hide_code=True)219def _(220 CAPACITY,221 CONST_DELAY,222 N_DRIVERS,223 eq_no,224 eq_yes,225 mo,226 t_theory_no,227 t_theory_yes,228):229 mo.md(f"""230 ## Results231 232 - Nash equilibrium **without** shortcut: **{eq_no:.2f}**233 - Nash equilibrium **with** shortcut: **{eq_yes:.2f}**234 - Adding the shortcut increased travel time by **{eq_yes - eq_no:.2f}** units235 ({100 * (eq_yes / eq_no - 1):.1f}% worse for every driver)236 237 Theory without shortcut (50/50 split): {t_theory_no:.2f}238 239 Theory with shortcut (all on SA→AB→BT): {t_theory_yes:.2f}240 241 Parameters: {N_DRIVERS} drivers, capacity={CAPACITY:.0f}, constant delay={CONST_DELAY}242 """)243 return244 245 246@app.cell247def _(alt, df_no, df_yes, pl):248 df_no_plot = df_no.select(["round", "mean"]).with_columns(249 pl.lit("without shortcut").alias("scenario")250 )251 df_yes_plot = df_yes.select(["round", "mean"]).with_columns(252 pl.lit("with shortcut").alias("scenario")253 )254 df_plot = pl.concat([df_no_plot, df_yes_plot])255 chart = (256 alt.Chart(df_plot)257 .mark_line()258 .encode(259 x=alt.X("round:Q", title="Round"),260 y=alt.Y("mean:Q", title="Mean travel time"),261 color=alt.Color("scenario:N", title="Network"),262 tooltip=["round:Q", "scenario:N", "mean:Q"],263 )264 .properties(title="Braess's Paradox: Convergence to Nash Equilibrium")265 )266 chart267 return268 269 270@app.cell(hide_code=True)271def _(mo):272 mo.md(r"""273 ## Understanding the Math274 275 ### Nash equilibrium276 277 A Nash equilibrium is a situation where every player has chosen a strategy and no single player can improve their own outcome by switching to a different strategy so long as everyone else stays put. Think of it as a stable fixed point: if you woke up one morning in a Nash equilibrium, you would have no reason to change what you are doing. Crucially, a Nash equilibrium need not be the best possible outcome for everyone collectively.278 279 ### The paradox, step by step280 281 Label the number of cars $N$ and suppose the congested links have delay $\alpha \cdot n$ where $n$ is the number of cars currently using that link. Without the shortcut, traffic splits evenly: $N/2$ cars use each route. Each driver's travel time is $(N/2)\alpha + c$, where $c$ is the fixed delay on the non-congested link. Neither route is faster than the other, so no driver wants to switch — that is Nash equilibrium.282 283 Now add the shortcut $A \to B$ with near-zero travel time $\varepsilon$. A single driver considering a switch reasons: "Link $AB$ is essentially free. If I take $SA$, cross to $B$, and take $BT$, I avoid the fixed cost $c$." If that driver is the only one to switch, it looks cheaper. But every driver makes the same calculation simultaneously. At the new equilibrium, all $N$ drivers pile onto $SA$ and $BT$:284 285 $$t_{\text{shortcut}} = N\alpha + \varepsilon + N\alpha = 2N\alpha + \varepsilon$$286 287 Since $2N\alpha > (N/2)\alpha + c$ for typical parameters, everyone is worse off than before the shortcut was built.288 289 ### The price of anarchy290 291 The social optimum would split traffic evenly at cost $(N/2)\alpha + c$, but selfish routing delivers $2N\alpha + \varepsilon$. The price of anarchy exceeds 1, meaning individual rationality destroys collective welfare.292 293 The [Prisoner's Dilemma](https://en.wikipedia.org/wiki/Prisoner's_dilemma) is the best-known example of this tension. Two suspects each choose independently to cooperate or defect. Defecting is a dominant strategy: it is better for you regardless of what the other person does. Yet if both defect, both get a worse outcome than if both had cooperated. Braess's paradox is the same logic scaled to $N$ drivers.294 295 ### The logit model296 297 The simulation uses a probabilistic choice rule: the probability a driver picks route $r$ is proportional to $\exp(-\beta \cdot t_r)$, where $t_r$ is the expected travel time on route $r$ and $\beta$ is a sensitivity parameter. When $\beta$ is large, drivers strongly prefer the fastest route and the outcome approaches the pure Nash equilibrium. When $\beta$ is small, drivers choose nearly randomly and the paradox weakens. The parameter $\beta$ captures how responsive real drivers are to time differences.298 """)299 return300 301 302if __name__ == "__main__":303 app.run()304