I

A route is an action

An action is one complete choice available to a learner. Here, that action is the commuter’s route from source to destination for one simulated day, not a separate turn at each junction.

Upper follows S → U → T, Lower follows S → V → T, and Shortcut follows S → U → V → T.

One simulated day is one episode. Each commuter selects exactly one complete route for that day. No central planner assigns routes, and no learning has started yet.

II

Everyone changes your reward

Edge load is the number of selected routes using an edge. Latency is travel time in this mathematical model. More users on either variable edge make that edge slower.

All physical latencies and route costs are measured in minutes. If x_U, x_L, and x_Z are route counts, Shortcut users raise both variable loads even though the central edge itself has zero latency.

Reward is negative perceived route cost. A shorter trip gives a less negative, therefore higher, reward. The normal view uses one consistent encoding: road width, color, and opacity all increase with the share of commuters using an edge. Thin green roads carry less traffic; thicker, brighter red roads carry more.

III

Each commuter learns alone

A Q value is one commuter’s current estimate of a route’s reward. Every commuter owns a separate row, experiences only the route it selected, and updates only that route in the episode.

An episode is one simulated commuting day in which all 100,000 commuters choose before any reward is evaluated. Their choices are simultaneous. They do not exchange travel times or observe everyone else’s costs.

The learning rate α = 0.15 controls how strongly one reward changes an estimate. Epsilon-greedy exploration usually chooses a route with the highest estimated value, but sometimes samples another. Gamma is zero because this repeated decision has one stage and no next state to value.

The environment is nonstationary from one learner’s perspective because the other commuters are adapting too. Shared congestion couples their private rewards even though the learners do not communicate. Classic theory for convergence of a single agent does not transfer unchanged.

IV

The game has a hidden landscape

A potential function assigns one height to every profile of route counts. A strict best response, one commuter switching to a cheaper route, moves downhill by exactly that commuter’s cost change.

The arrows show an asynchronous sequence of strict improvements. The final point is stable because no individual commuter can switch routes and lower their own private cost. The learners discover the shortcut because it is privately attractive.

Q-learning is not a monotone downhill path. Simultaneous choices and exploration can move its observed count profile in either direction.

V

Stable does not mean efficient

A Nash equilibrium is stable against one traveler switching alone. A social optimum minimizes total travel latency across everyone. Those are different questions.

Remove one Shortcut user before adding that same traveler to Upper. The candidate route is priced after the changed loads, so the deviator’s own traffic is counted exactly once.

Exploitability is the largest amount by which one agent could reduce its own route cost by switching alone.

The displayed profile in which everyone uses Shortcut is stable even though its total delay is not minimal. It is one of exact weak pure equilibria for this finite population: . No uniqueness is claimed.

selfish equilibrium

average minutes

social cost commuter minutes

an exact social optimum

average minutes

social cost commuter minutes

Price of Anarchy compares the worst equilibrium cost with the optimum. Here it is , approximately . Price of Stability compares the best equilibrium with the optimum; here it is , approximately .

VI

Remove a road. Everyone gets faster.

Closing the central shortcut removes one action. No traveler can use that edge, so Upper and Lower carry all 100,000 commuters. Removing the shortcut changes what every commuter can choose.

The closed equilibrium is , with average latency minutes. Relative to the displayed equilibrium in which everyone uses Shortcut, the average falls by 25 percent. This is a result for this Braess instance, not a claim that removing roads generally improves traffic.

VII

Price the externality

An externality is delay imposed on other travelers but not fully felt by the traveler choosing the route. A toll based on marginal cost adds that missing increment to private perceived cost.

The toll changes reward and route incentives. It does not change physical edge latency, and toll payments remain transfers outside the travel time objective. Edge color and thickness still represent traffic share, never payment. A toll changes private cost without changing the physical road itself.

The tolled potential therefore equals physical social cost. Its equilibrium reaches , which is an exact optimum for the selected population.

VIII

Three ways to adapt

Independent Q-learning sees only the reward for the route it selected.

Asynchronous strict best response receives exact switching costs for one agent.

Hedge receives every counterfactual route cost after each round, so it has fuller information.

External regret compares realized cumulative cost with the cost of always using one fixed route. Low regret does not imply that the last iterate, the final profile, is a pure Nash equilibrium.

The comparison below is the fully replicated study with 100 commuters. The 1,000 and 10,000 presets use one audited run across the full population. The 100,000 preset uses one audited sampled proxy and is not assigned the same uncertainty.

A representative medoid is the run whose final count profile has the smallest total distance to the others, with exploitability and seed breaking ties. It is not chosen for visual appeal.