Marketplace dispatch

Driver-to-rider dispatch is Kantorovich's transportation problem: move drivers per zone (supply) to riders per zone (demand) at least travel cost. The dual potentials are the market-clearing prices: the demand dual is the surge signal — higher where demand outstrips supply — and it comes free as the dual of the same optimisation, which no dispatch heuristic gives. It is solved by entropic, log-domain Sinkhorn, which is differentiable, so pricing can itself be optimised; as the entropic regularisation goes to zero it recovers the exact linear program.

The script builds a synthetic city and compares the transport plan with two naive dispatchers: a local one that strands the demand it cannot reach, and a locally greedy one that serves everyone at a higher cost. It then applies the surge prices as a driver incentive — drivers best-respond toward high-price zones — and reports the supply-demand imbalance before and after.

uv run python scripts/run_marketplace_demo.py

What it printed when this site was built:

== marketplace dispatch: Kantorovich optimal transport vs naive (synthetic city) ==
Kantorovich OT: 100% served at min cost 10.64 + surge prices.
naive local-only dispatch strands 5.7 of 21.2 riders (27%) where demand exceeds local supply.
naive reroute (100% served): cost 14.27 -> OT is 25.4% cheaper.
surge -> driver reallocation cuts imbalance 11.49 -> 8.40 (27%).
Kantorovich-Rubinstein duality gap = 9.70e-03 (surge = free dual).

Code: chc.matching.