13 braess paradox

%23%20%2F%2F%2F%20script%0A%23%20requires-python%20%3D%20%22%3E%3D3.13%22%0A%23%20dependencies%20%3D%20%5B%0A%23%20%20%20%20%20%22altair%22%2C%0A%23%20%20%20%20%20%22asimpy%22%2C%0A%23%20%20%20%20%20%22marimo%22%2C%0A%23%20%20%20%20%20%22polars%22%2C%0A%23%20%5D%0A%23%20%2F%2F%2F%0A%0Aimport%20marimo%0A%0A__generated_with%20%3D%20%220.20.4%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22)%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20import%20math%0A%20%20%20%20import%20random%0A%0A%20%20%20%20import%20altair%20as%20alt%0A%20%20%20%20import%20polars%20as%20pl%0A%0A%20%20%20%20from%20asimpy%20import%20Environment%2C%20Process%0A%0A%20%20%20%20return%20Environment%2C%20Process%2C%20alt%2C%20math%2C%20mo%2C%20pl%2C%20random%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Braess's%20Paradox%0A%0A%20%20%20%20%23%23%20*Adding%20a%20Road%20Makes%20Traffic%20Worse*%0A%0A%20%20%20%20A%20city%20has%20two%20routes%20from%20source%20%24S%24%20to%20destination%20%24T%24%3A%0A%0A%20%20%20%20-%20**Top%20route**%20%24S%20%5Cto%20A%20%5Cto%20T%24%3A%20link%20%24SA%24%20is%20congestion-dependent%3B%20link%20%24AT%24%20has%20a%20fixed%20travel%20time.%0A%20%20%20%20-%20**Bottom%20route**%20%24S%20%5Cto%20B%20%5Cto%20T%24%3A%20link%20%24SB%24%20has%20a%20fixed%20travel%20time%3B%20link%20%24BT%24%20is%20congestion-dependent.%0A%0A%20%20%20%20The%20network%20is%20symmetric.%20A%20city%20planner%20proposes%20adding%20a%20new%20shortcut%20link%20%24A%20%5Cto%20B%24%20with%20near-zero%20travel%20time%2C%20creating%20a%20third%20route%20%24S%20%5Cto%20A%20%5Cto%20B%20%5Cto%20T%24.%20To%20her%20surprise%2C%20adding%20the%20shortcut%20makes%20everyone's%20travel%20time%20longer%20at%20the%20selfish-routing%20Nash%20equilibrium.%0A%0A%20%20%20%20%23%23%23%20Without%20the%20shortcut%0A%0A%20%20%20%20Both%20routes%20are%20symmetric.%20In%20equilibrium%2C%20traffic%20splits%20evenly.%20If%20%24N%2F2%24%20drivers%20use%20each%20route%20and%20the%20congested%20links%20have%20delay%20%24%5Calpha%20%5Ccdot%20n%24%20(where%20%24n%24%20is%20the%20number%20of%20cars)%3A%0A%0A%20%20%20%20%24%24t_%7B%5Ctext%7Btop%7D%7D%20%3D%20%5Cfrac%7BN%7D%7B2%7D%5Calpha%20%2B%20c%20%3D%20t_%7B%5Ctext%7Bbottom%7D%7D%24%24%0A%0A%20%20%20%20%23%23%23%20With%20the%20shortcut%20%24A%20%5Cto%20B%24%0A%0A%20%20%20%20Each%20driver%20thinks%2C%20%22Link%20%24AB%24%20is%20free%3B%20I%20can%20use%20%24SA%24%2C%20slip%20across%20to%20%24B%24%2C%20then%20take%20%24BT%24%20instead%20of%20the%20slow%20constant%20link%20%24AT%24.%22%20All%20%24N%24%20drivers%20make%20this%20choice.%20The%20Nash%20equilibrium%20has%20everyone%20on%20%24S%20%5Cto%20A%20%5Cto%20B%20%5Cto%20T%24%3A%0A%0A%20%20%20%20%24%24t_%7B%5Ctext%7Bshortcut%7D%7D%20%3D%20N%5Calpha%20%2B%20%5Cvarepsilon%20%2B%20N%5Calpha%20%3D%202N%5Calpha%20%2B%20%5Cvarepsilon%24%24%0A%0A%20%20%20%20Since%20%242N%5Calpha%20%3E%20%5Cfrac%7BN%7D%7B2%7D%5Calpha%20%2B%20c%24%20for%20typical%20parameters%2C%20travel%20times%20*increase*%20after%20the%20road%20is%20added.%20This%20is%20the%20paradox%3A%20individually%20rational%20decisions%20produce%20a%20collectively%20worse%20outcome.%20The%20ratio%20of%20Nash%20equilibrium%20cost%20to%20the%20socially%20optimal%20cost%20is%20called%20the%20*%5Bprice%20of%20anarchy%5D(https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FPrice_of_anarchy)*.%0A%0A%20%20%20%20%5BBraess's%20paradox%5D(https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FBraess%2527s_paradox)%20is%20not%20theoretical.%20Seoul%2C%20Stuttgart%2C%20and%20New%20York%20all%20observed%20traffic%20*improvements*%20after%20closing%20roads.%20Conversely%2C%20new%20roads%20in%20highly%20congested%20networks%20have%20sometimes%20worsened%20average%20travel%20times.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Implementation%0A%0A%20%20%20%20The%20simulation%20maintains%20a%20shared%20%60LinkCounts%60%20object%20tracking%20how%20many%20cars%20are%20currently%20on%20each%20link.%20Each%20%60Car%60%20process%3A%0A%0A%20%20%20%201.%20Observes%20current%20link%20counts%20and%20computes%20expected%20travel%20time%20for%20each%20available%20route.%0A%20%20%20%202.%20Greedily%20picks%20the%20route%20with%20minimum%20expected%20time.%0A%20%20%20%203.%20Traverses%20each%20link%20in%20sequence%2C%20incrementing%20the%20count%20on%20entry%20and%20decrementing%20on%20exit%3B%20the%20delay%20is%20fixed%20at%20the%20count%20observed%20on%20entry.%0A%0A%20%20%20%20Two%20runs%20are%20compared%3A%20one%20with%20only%20the%20top%20and%20bottom%20routes%2C%20one%20with%20the%20%24AB%24%20shortcut%20added.%20The%20simulation%20uses%20a%20probabilistic%20%5Blogit%5D(https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FLogit)%20choice%20rule%20so%20that%20convergence%20to%20Nash%20equilibrium%20is%20smooth%20rather%20than%20instant.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20n_rounds_slider%20%3D%20mo.ui.slider(%0A%20%20%20%20%20%20%20%20start%3D10%2C%0A%20%20%20%20%20%20%20%20stop%3D200%2C%0A%20%20%20%20%20%20%20%20step%3D10%2C%0A%20%20%20%20%20%20%20%20value%3D80%2C%0A%20%20%20%20%20%20%20%20label%3D%22Number%20of%20rounds%22%2C%0A%20%20%20%20)%0A%0A%20%20%20%20beta_slider%20%3D%20mo.ui.slider(%0A%20%20%20%20%20%20%20%20start%3D0.1%2C%0A%20%20%20%20%20%20%20%20stop%3D2.0%2C%0A%20%20%20%20%20%20%20%20step%3D0.1%2C%0A%20%20%20%20%20%20%20%20value%3D0.5%2C%0A%20%20%20%20%20%20%20%20label%3D%22Sensitivity%20(%CE%B2)%22%2C%0A%20%20%20%20)%0A%0A%20%20%20%20seed_input%20%3D%20mo.ui.number(%0A%20%20%20%20%20%20%20%20value%3D192%2C%0A%20%20%20%20%20%20%20%20step%3D1%2C%0A%20%20%20%20%20%20%20%20label%3D%22Random%20seed%22%2C%0A%20%20%20%20)%0A%0A%20%20%20%20run_button%20%3D%20mo.ui.button(label%3D%22Run%20simulation%22)%0A%0A%20%20%20%20mo.vstack(%5B%0A%20%20%20%20%20%20%20%20n_rounds_slider%2C%0A%20%20%20%20%20%20%20%20beta_slider%2C%0A%20%20%20%20%20%20%20%20seed_input%2C%0A%20%20%20%20%20%20%20%20run_button%2C%0A%20%20%20%20%5D)%0A%20%20%20%20return%20beta_slider%2C%20n_rounds_slider%2C%20seed_input%0A%0A%0A%40app.cell%0Adef%20_(beta_slider%2C%20n_rounds_slider%2C%20seed_input)%3A%0A%20%20%20%20N_ROUNDS%20%3D%20int(n_rounds_slider.value)%0A%20%20%20%20BETA%20%3D%20float(beta_slider.value)%0A%20%20%20%20SEED%20%3D%20int(seed_input.value)%0A%20%20%20%20N_DRIVERS%20%3D%204000%0A%20%20%20%20CAPACITY%20%3D%20100.0%0A%20%20%20%20CONST_DELAY%20%3D%2045.0%0A%20%20%20%20return%20BETA%2C%20CAPACITY%2C%20CONST_DELAY%2C%20N_DRIVERS%2C%20N_ROUNDS%2C%20SEED%0A%0A%0A%40app.cell%0Adef%20_(CAPACITY%2C%20CONST_DELAY)%3A%0A%20%20%20%20def%20route_times(n_top%2C%20n_bot%2C%20n_short)%3A%0A%20%20%20%20%20%20%20%20n_sa%20%3D%20n_top%20%2B%20n_short%0A%20%20%20%20%20%20%20%20n_bt%20%3D%20n_bot%20%2B%20n_short%0A%20%20%20%20%20%20%20%20t_top%20%3D%20n_sa%20%2F%20CAPACITY%20%2B%20CONST_DELAY%0A%20%20%20%20%20%20%20%20t_bot%20%3D%20CONST_DELAY%20%2B%20n_bt%20%2F%20CAPACITY%0A%20%20%20%20%20%20%20%20t_short%20%3D%20n_sa%20%2F%20CAPACITY%20%2B%20n_bt%20%2F%20CAPACITY%0A%20%20%20%20%20%20%20%20return%20t_top%2C%20t_bot%2C%20t_short%0A%0A%20%20%20%20return%20(route_times%2C)%0A%0A%0A%40app.cell%0Adef%20_(BETA%2C%20math)%3A%0A%20%20%20%20def%20logit_split(times)%3A%0A%20%20%20%20%20%20%20%20vals%20%3D%20%5Bmath.exp(-BETA%20*%20t)%20for%20t%20in%20times%5D%0A%20%20%20%20%20%20%20%20total%20%3D%20sum(vals)%0A%20%20%20%20%20%20%20%20return%20%5Bv%20%2F%20total%20for%20v%20in%20vals%5D%0A%0A%20%20%20%20return%20(logit_split%2C)%0A%0A%0A%40app.cell%0Adef%20_(N_DRIVERS%2C%20N_ROUNDS%2C%20Process%2C%20logit_split%2C%20route_times)%3A%0A%20%20%20%20class%20RoutingGame(Process)%3A%0A%20%20%20%20%20%20%20%20def%20init(self%2C%20has_shortcut%2C%20history)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.has_shortcut%20%3D%20has_shortcut%0A%20%20%20%20%20%20%20%20%20%20%20%20self.history%20%3D%20history%0A%20%20%20%20%20%20%20%20%20%20%20%20self._n_top%20%3D%20N_DRIVERS%20%2F%2F%202%0A%20%20%20%20%20%20%20%20%20%20%20%20self._n_bot%20%3D%20N_DRIVERS%20-%20N_DRIVERS%20%2F%2F%202%0A%20%20%20%20%20%20%20%20%20%20%20%20self._n_short%20%3D%200%0A%0A%20%20%20%20%20%20%20%20async%20def%20run(self)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20_%20in%20range(N_ROUNDS)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20await%20self.timeout(1.0)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20t_top%2C%20t_bot%2C%20t_short%20%3D%20route_times(self._n_top%2C%20self._n_bot%2C%20self._n_short)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20self.has_shortcut%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20probs%20%3D%20logit_split(%5Bt_top%2C%20t_bot%2C%20t_short%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self._n_top%20%3D%20round(N_DRIVERS%20*%20probs%5B0%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self._n_bot%20%3D%20round(N_DRIVERS%20*%20probs%5B1%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self._n_short%20%3D%20N_DRIVERS%20-%20self._n_top%20-%20self._n_bot%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20probs%20%3D%20logit_split(%5Bt_top%2C%20t_bot%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self._n_top%20%3D%20round(N_DRIVERS%20*%20probs%5B0%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self._n_bot%20%3D%20N_DRIVERS%20-%20self._n_top%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self._n_short%20%3D%200%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20t_top2%2C%20t_bot2%2C%20t_short2%20%3D%20route_times(self._n_top%2C%20self._n_bot%2C%20self._n_short)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20mean_t%20%3D%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self._n_top%20*%20t_top2%20%2B%20self._n_bot%20*%20t_bot2%20%2B%20self._n_short%20*%20t_short2%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%20%2F%20N_DRIVERS%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.history.append(%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22round%22%3A%20self.now%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22n_top%22%3A%20self._n_top%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22n_bot%22%3A%20self._n_bot%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22n_short%22%3A%20self._n_short%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22t_top%22%3A%20t_top2%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22t_bot%22%3A%20t_bot2%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22t_short%22%3A%20t_short2%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22mean%22%3A%20mean_t%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D)%0A%0A%20%20%20%20return%20(RoutingGame%2C)%0A%0A%0A%40app.cell%0Adef%20_(Environment%2C%20RoutingGame)%3A%0A%20%20%20%20def%20simulate(has_shortcut)%3A%0A%20%20%20%20%20%20%20%20history%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20env%20%3D%20Environment()%0A%20%20%20%20%20%20%20%20RoutingGame(env%2C%20has_shortcut%2C%20history)%0A%20%20%20%20%20%20%20%20env.run()%0A%20%20%20%20%20%20%20%20return%20history%0A%0A%20%20%20%20return%20(simulate%2C)%0A%0A%0A%40app.cell%0Adef%20_(CAPACITY%2C%20CONST_DELAY%2C%20N_DRIVERS%2C%20SEED%2C%20pl%2C%20random%2C%20simulate)%3A%0A%20%20%20%20random.seed(SEED)%0A%20%20%20%20hist_no%20%3D%20simulate(has_shortcut%3DFalse)%0A%20%20%20%20hist_yes%20%3D%20simulate(has_shortcut%3DTrue)%0A%20%20%20%20df_no%20%3D%20pl.DataFrame(hist_no)%0A%20%20%20%20df_yes%20%3D%20pl.DataFrame(hist_yes)%0A%20%20%20%20eq_no%20%3D%20hist_no%5B-1%5D%5B%22mean%22%5D%0A%20%20%20%20eq_yes%20%3D%20hist_yes%5B-1%5D%5B%22mean%22%5D%0A%20%20%20%20n_half%20%3D%20N_DRIVERS%20%2F%202%0A%20%20%20%20t_theory_no%20%3D%20n_half%20%2F%20CAPACITY%20%2B%20CONST_DELAY%0A%20%20%20%20t_theory_yes%20%3D%20N_DRIVERS%20%2F%20CAPACITY%20%2B%20N_DRIVERS%20%2F%20CAPACITY%0A%20%20%20%20return%20df_no%2C%20df_yes%2C%20eq_no%2C%20eq_yes%2C%20t_theory_no%2C%20t_theory_yes%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(%0A%20%20%20%20CAPACITY%2C%0A%20%20%20%20CONST_DELAY%2C%0A%20%20%20%20N_DRIVERS%2C%0A%20%20%20%20eq_no%2C%0A%20%20%20%20eq_yes%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20t_theory_no%2C%0A%20%20%20%20t_theory_yes%2C%0A)%3A%0A%20%20%20%20mo.md(f%22%22%22%0A%20%20%20%20%23%23%20Results%0A%0A%20%20%20%20-%20Nash%20equilibrium%20**without**%20shortcut%3A%20**%7Beq_no%3A.2f%7D**%0A%20%20%20%20-%20Nash%20equilibrium%20**with**%20shortcut%3A%20**%7Beq_yes%3A.2f%7D**%0A%20%20%20%20-%20Adding%20the%20shortcut%20increased%20travel%20time%20by%20**%7Beq_yes%20-%20eq_no%3A.2f%7D**%20units%0A%20%20%20%20%20%20(%7B100%20*%20(eq_yes%20%2F%20eq_no%20-%201)%3A.1f%7D%25%20worse%20for%20every%20driver)%0A%0A%20%20%20%20Theory%20without%20shortcut%20(50%2F50%20split)%3A%20%7Bt_theory_no%3A.2f%7D%0A%0A%20%20%20%20Theory%20with%20shortcut%20(all%20on%20SA%E2%86%92AB%E2%86%92BT)%3A%20%7Bt_theory_yes%3A.2f%7D%0A%0A%20%20%20%20Parameters%3A%20%7BN_DRIVERS%7D%20drivers%2C%20capacity%3D%7BCAPACITY%3A.0f%7D%2C%20constant%20delay%3D%7BCONST_DELAY%7D%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(alt%2C%20df_no%2C%20df_yes%2C%20pl)%3A%0A%20%20%20%20df_no_plot%20%3D%20df_no.select(%5B%22round%22%2C%20%22mean%22%5D).with_columns(%0A%20%20%20%20%20%20%20%20pl.lit(%22without%20shortcut%22).alias(%22scenario%22)%0A%20%20%20%20)%0A%20%20%20%20df_yes_plot%20%3D%20df_yes.select(%5B%22round%22%2C%20%22mean%22%5D).with_columns(%0A%20%20%20%20%20%20%20%20pl.lit(%22with%20shortcut%22).alias(%22scenario%22)%0A%20%20%20%20)%0A%20%20%20%20df_plot%20%3D%20pl.concat(%5Bdf_no_plot%2C%20df_yes_plot%5D)%0A%20%20%20%20chart%20%3D%20(%0A%20%20%20%20%20%20%20%20alt.Chart(df_plot)%0A%20%20%20%20%20%20%20%20.mark_line()%0A%20%20%20%20%20%20%20%20.encode(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3Dalt.X(%22round%3AQ%22%2C%20title%3D%22Round%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3Dalt.Y(%22mean%3AQ%22%2C%20title%3D%22Mean%20travel%20time%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20color%3Dalt.Color(%22scenario%3AN%22%2C%20title%3D%22Network%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20tooltip%3D%5B%22round%3AQ%22%2C%20%22scenario%3AN%22%2C%20%22mean%3AQ%22%5D%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20.properties(title%3D%22Braess's%20Paradox%3A%20Convergence%20to%20Nash%20Equilibrium%22)%0A%20%20%20%20)%0A%20%20%20%20chart%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Understanding%20the%20Math%0A%0A%20%20%20%20%23%23%23%20Nash%20equilibrium%0A%0A%20%20%20%20A%20Nash%20equilibrium%20is%20a%20situation%20where%20every%20player%20has%20chosen%20a%20strategy%20and%20no%20single%20player%20can%20improve%20their%20own%20outcome%20by%20switching%20to%20a%20different%20strategy%20so%20long%20as%20everyone%20else%20stays%20put.%20Think%20of%20it%20as%20a%20stable%20fixed%20point%3A%20if%20you%20woke%20up%20one%20morning%20in%20a%20Nash%20equilibrium%2C%20you%20would%20have%20no%20reason%20to%20change%20what%20you%20are%20doing.%20Crucially%2C%20a%20Nash%20equilibrium%20need%20not%20be%20the%20best%20possible%20outcome%20for%20everyone%20collectively.%0A%0A%20%20%20%20%23%23%23%20The%20paradox%2C%20step%20by%20step%0A%0A%20%20%20%20Label%20the%20number%20of%20cars%20%24N%24%20and%20suppose%20the%20congested%20links%20have%20delay%20%24%5Calpha%20%5Ccdot%20n%24%20where%20%24n%24%20is%20the%20number%20of%20cars%20currently%20using%20that%20link.%20Without%20the%20shortcut%2C%20traffic%20splits%20evenly%3A%20%24N%2F2%24%20cars%20use%20each%20route.%20Each%20driver's%20travel%20time%20is%20%24(N%2F2)%5Calpha%20%2B%20c%24%2C%20where%20%24c%24%20is%20the%20fixed%20delay%20on%20the%20non-congested%20link.%20Neither%20route%20is%20faster%20than%20the%20other%2C%20so%20no%20driver%20wants%20to%20switch%20%E2%80%94%20that%20is%20Nash%20equilibrium.%0A%0A%20%20%20%20Now%20add%20the%20shortcut%20%24A%20%5Cto%20B%24%20with%20near-zero%20travel%20time%20%24%5Cvarepsilon%24.%20A%20single%20driver%20considering%20a%20switch%20reasons%3A%20%22Link%20%24AB%24%20is%20essentially%20free.%20If%20I%20take%20%24SA%24%2C%20cross%20to%20%24B%24%2C%20and%20take%20%24BT%24%2C%20I%20avoid%20the%20fixed%20cost%20%24c%24.%22%20If%20that%20driver%20is%20the%20only%20one%20to%20switch%2C%20it%20looks%20cheaper.%20But%20every%20driver%20makes%20the%20same%20calculation%20simultaneously.%20At%20the%20new%20equilibrium%2C%20all%20%24N%24%20drivers%20pile%20onto%20%24SA%24%20and%20%24BT%24%3A%0A%0A%20%20%20%20%24%24t_%7B%5Ctext%7Bshortcut%7D%7D%20%3D%20N%5Calpha%20%2B%20%5Cvarepsilon%20%2B%20N%5Calpha%20%3D%202N%5Calpha%20%2B%20%5Cvarepsilon%24%24%0A%0A%20%20%20%20Since%20%242N%5Calpha%20%3E%20(N%2F2)%5Calpha%20%2B%20c%24%20for%20typical%20parameters%2C%20everyone%20is%20worse%20off%20than%20before%20the%20shortcut%20was%20built.%0A%0A%20%20%20%20%23%23%23%20The%20price%20of%20anarchy%0A%0A%20%20%20%20The%20social%20optimum%20would%20split%20traffic%20evenly%20at%20cost%20%24(N%2F2)%5Calpha%20%2B%20c%24%2C%20but%20selfish%20routing%20delivers%20%242N%5Calpha%20%2B%20%5Cvarepsilon%24.%20The%20price%20of%20anarchy%20exceeds%201%2C%20meaning%20individual%20rationality%20destroys%20collective%20welfare.%0A%0A%20%20%20%20The%20%5BPrisoner's%20Dilemma%5D(https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FPrisoner's_dilemma)%20is%20the%20best-known%20example%20of%20this%20tension.%20Two%20suspects%20each%20choose%20independently%20to%20cooperate%20or%20defect.%20Defecting%20is%20a%20dominant%20strategy%3A%20it%20is%20better%20for%20you%20regardless%20of%20what%20the%20other%20person%20does.%20Yet%20if%20both%20defect%2C%20both%20get%20a%20worse%20outcome%20than%20if%20both%20had%20cooperated.%20Braess's%20paradox%20is%20the%20same%20logic%20scaled%20to%20%24N%24%20drivers.%0A%0A%20%20%20%20%23%23%23%20The%20logit%20model%0A%0A%20%20%20%20The%20simulation%20uses%20a%20probabilistic%20choice%20rule%3A%20the%20probability%20a%20driver%20picks%20route%20%24r%24%20is%20proportional%20to%20%24%5Cexp(-%5Cbeta%20%5Ccdot%20t_r)%24%2C%20where%20%24t_r%24%20is%20the%20expected%20travel%20time%20on%20route%20%24r%24%20and%20%24%5Cbeta%24%20is%20a%20sensitivity%20parameter.%20When%20%24%5Cbeta%24%20is%20large%2C%20drivers%20strongly%20prefer%20the%20fastest%20route%20and%20the%20outcome%20approaches%20the%20pure%20Nash%20equilibrium.%20When%20%24%5Cbeta%24%20is%20small%2C%20drivers%20choose%20nearly%20randomly%20and%20the%20paradox%20weakens.%20The%20parameter%20%24%5Cbeta%24%20captures%20how%20responsive%20real%20drivers%20are%20to%20time%20differences.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A