chc.matching¶
Stability tier: evolving.
Kantorovich optimal transport for marketplace matching -- dispatch plan + dual surge prices.
The discrete, marketplace-native sibling of the continuum chc.transport: driver->rider
dispatch is Kantorovich's transportation problem (1939; Nobel 1975) -- move drivers/zone
(supply) to riders/zone (demand) at least travel cost. The dual potentials are the
market-clearing prices: the demand dual g is the surge signal (higher where demand outstrips
supply), free as the dual of the same optimisation -- which no dispatch heuristic gives. Solved by
entropic (log-domain, differentiable) Sinkhorn so pricing is optimisable; eps -> 0 recovers the
exact LP (Octave glpk cross-check: Kantorovich-Rubinstein gap = 0). NumPy baselines, JAX OT core.
An experiment that treats some of the rows moves the prices every row faces, so the treated-minus-
control difference an A/B test reads is not what treating every row would do.
shadow_price_effect reads that global effect off the rows' rents in the experiment's own
matching instead, and shadow_price_interval says how far it is determined at eps = 0.
SinkhornResult
dataclass
¶
A solved entropic OT: plan, dual potentials (surge prices), cost, duality gap, and how far the plan is from the marginals it was asked to meet.
ShadowPriceEffect
dataclass
¶
What treating every randomised row would do to a matching's welfare, read off one experiment.
effect is the treated-minus-control difference of the rows' rents, and naive the same
difference of the surplus each row's matches earn it, which is what an A/B test reads. Both are
totals over the randomised mass. standard_error is the effect's over the assignment.
curvature estimates -f''(p), how concave welfare is in the treated share p, from the
same matching, less the noise the assignment puts into it; on a market of fixed types split into
treated and control copies, which has no such noise, it reads low. second_order_bias is
(1/2 - p) * curvature: what the effect misses the global effect by, to second order in the
treatment. nu_hat is how far the treatment would move the prices between no row treated and
every row, to first order, in units of eps. Above 1 the market is near the LP limit, where
the bias is first order; second_order_bias is then None, and reason says why.
MarketplaceMatching
dataclass
¶
Zones with driver supply, rider demand, and cost (travel) between them.
synthetic_city(n_zones=8, seed=0)
classmethod
¶
Drivers cluster centrally, riders spread to the suburbs -- a supply-demand mismatch.
optimal()
¶
The Kantorovich OT dispatch (100% served at min travel) + the dual surge prices.
surge_prices()
¶
Market-clearing surge = the demand-side dual potentials (high in undersupplied zones).
nearest_local()
¶
Naive local dispatch: (served_cost, coverage) -- strands demand it cannot reach.
nearest_reroute_cost()
¶
Myopic complete dispatch cost (100% served, but locally greedy -- costlier than OT).
surge_rebalance(step=0.5)
¶
Apply surge as a driver incentive; drivers best-respond toward high-price zones.
Returns supply-demand imbalance (before, after): the surge prices, projected onto the
supply simplex (a best-response via chc.games.project_simplex), pull drivers toward
high-price zones -- surge as an intervention whose equilibrium effect the dual predicts.
sinkhorn(cost, supply, demand, *, eps=0.05, iters=1000, tol=0.0001)
¶
Entropic (log-domain, stable) Kantorovich OT; returns the plan and dual potentials (surge).
cost is (m, n) dispatch cost; supply/demand are the marginals (equal totals).
Recovers the exact transportation LP as eps -> 0; the demand potentials g are the
market-clearing surge prices.
The iteration count is fixed, so that the solve stays a lax.scan and differentiable, and a
fixed count is a guess: at small eps the residual can sit on a plateau for thousands of
iterations before it falls. On MarketplaceMatching.synthetic_city(seed=3) at its own
eps = 0.02 it is still 2.2e-3 after 2000 iterations and 1.7e-15 after 16000 (float64).
SinkhornResult.marginal_residual says whether the guess was good, and a residual over
tol is logged as a warning, because potentials read off an unconverged plan are not the
market-clearing prices.
shadow_price_effect(cost, supply, demand, treated, *, eps, randomised=None, strata=None, iters=1000, tol=1e-06)
¶
The global effect of a treatment on a matching's welfare, from one experiment on its rows.
Experimental: it may change or be withdrawn in any release.
cost, supply and demand are the market the experiment runs, as sinkhorn
takes them, with the treatment already in the treated rows' costs. treated marks those rows,
and randomised the rows the experiment assigned at all: a row outside it, such as an idle
pool of supply, is priced but not counted. The rows are the randomised units; to randomise the
other side, pass the transposed market. Welfare is -(<P, cost> + eps KL(P | supply x
demand)) at the optimal plan P, and the effect is its change when every randomised row is
treated. strata, one label per row fixed before the assignment, such as the rows' types,
post-stratify the experiment: each stratum's treated-minus-control difference is weighted by the
stratum's mass, so the mix of each stratum the coins dealt either arm no longer moves the
effect, and the standard error, the curvature and nu_hat are read the same way. Every
stratum needs two rows in each arm, and second_order_bias takes every row to have had the
same chance of treatment.
Each row's rent is the derivative of welfare in its own mass, so the treated-minus-control
difference of rents is the derivative f'(p) of welfare in the treated share. By concavity
f'(1) <= f(1) - f(0) <= f'(0), and f'(p) misses the global effect by
(1/2 - p) (-f''(p)) to second order in the treatment, where the naive difference misses it
at first order by the displacement it prices. -f''(p) = eps g' C^+ g is read off the same
plan, with g the treated-minus-control difference of the rows' plans and C the
Jacobian of their demand in the prices. Design at p = 1/2, where the second-order term
vanishes whatever the curvature; averaging two experiments at p = 1/2 -+ 1/(2 sqrt 3) leaves
a bias of fifth order.
Measured over 400 assignments at treated shares 0.2 and 0.5, on six markets (80 units against
80 others at three balances of supply and demand, and 80, 320 or 1280 units against three
zones), the effect's spread was 0.90--1.06 of its standard_error, and 0.39--0.89 of the
naive difference's. The curvature from one experiment is noisy: its spread over assignments
was 2.1--4.2 times its value on 80 and 320 units against zones, 0.8--1.1 times on 1280, and
1.3--5.8 times on 80 units against 80 others, its mean within 1.7 standard errors of the value
throughout. At p = 0.2 the bias it prices was 0.4--7% of the effect's standard error on
those markets, so it matters where the standard error is small. It does not price the part of
the bias that shrinks with the number of rows: under 0.3% of the standard error on five of the
markets, but 2--3% where demand is short on 80 units against 80 others, which at p = 1/2 is
most of the bias there.
Post-stratified by the rows' four types, those too small for two rows an arm merged before the assignment, the effect's spread on the same markets was 0.52--0.78 of the plain effect's, and 0.85--1.04 of its standard error. Fix the strata before the assignment, each large enough that an arm short of two of its rows is unlikely: merging the strata an assignment left short into another after it moved the effect by up to a quarter of the global effect on average, and falling back to the plain difference on such assignments moves it about as much.
Near the LP limit the second-order law fails, and the bias saturates at the LP's first-order
bias instead. Over twenty markets swept towards that limit, the law gave the bias to within 10%
in nine cases of ten where nu_hat was below 0.5, and within 33% below 1; past 1 the median
miss was 24--70%. nu_hat above 1 leaves second_order_bias at None and logs why, and
so does a solve whose marginal residual is over tol. Read off one experiment, nu_hat
carries the assignment's noise, which raises it on average, so where an arm has few rows it
withholds the claim far from the limit too: in 1--7% of the experiments on 80 units against
three zones, in none on 320 or 1280, and in 4--100% on 80 units against 80 others, whose 80
prices it reads one by one. Post-stratified, it withheld the claim in at most 1% of the
experiments on 80 units against three zones, and nearly as often as before on 80 units against
80 others. A float32 solve moved every number by about 1e-7 relative against float64 on those
markets, at eps = 0.3.
Raises:
| Type | Description |
|---|---|
ValueError
|
on an |
shadow_price_interval(cost, supply, demand, treated, *, randomised=None, strata=None)
¶
The effect shadow_price_effect reads, at eps = 0: an interval, not a point.
Experimental: it may change or be withdrawn in any release.
The exact matching LP has many optimal duals wherever it is degenerate, and every one of them
is a supergradient of welfare in the treated share. So the treated-minus-control difference of
the rows' rents ranges over [f'(p+), f'(p-)] across the optimal dual face, and this returns
that range, from two LPs over the face (HiGHS). A solver's own dual is one end of it. At a
breakpoint of welfare in the treated share the interval is wide; between breakpoints it is a
point, and it is the effect's limit as eps -> 0. Its bias against the global effect is
first order in the treatment: the LP has no second-order regime. Arguments and refusals are
shadow_price_effect's.
Raises:
| Type | Description |
|---|---|
ValueError
|
as |
RuntimeError
|
when HiGHS does not solve an LP a balanced market always has a solution to. |
marketplace_report(matching)
¶
Kantorovich OT dispatch vs two naive failure modes, plus the surge/equilibrium win.