Is load balancing a congestion price?

What it found

Capacity-constrained expert routing is a softmax with a per-expert price, the Lagrange multiplier of its capacity, and the dual is smooth and concave. Any price vector gives a computable upper bound and, after repair toward the uniform assignment, a feasible lower bound, so a verifier certifies near-optimality from prices alone (gap below 10⁻⁴ at the optimum, always above the true suboptimality). Sign-update balancing has a sampling floor of about 2.5/√B in max relative overload that no step size removes, plus a step-proportional limit cycle on a fixed batch (22.6% at γ=0.2, 1.2% at 0.01). Two-expert Gaussian price of balance is closed form with price shift equal to the median gap; a Hoeffding audit of ln(2N/δ)/(2ε²) tokens covered 400 of 400 trials. Synthetic scores only. Stylised.

A figure from its own output

Paper, code and results

• README and method
• White paper
• Experiments and results
• Code
• Tests

More in Markets as routers

• Is risk tolerance the learning rate of a wealth market?Fractional-Kelly wealth markets as expert routers: risk-tolerance-weighted price, ln(1/s)/λ regret bound, growth-optimal λ*=(π−p)/(q−p), manipulation cost V·χ² vs LMSR b·KL (7.5× stiffer at p=0.99), and a switching-truth trade-off where λ≈0.1–0.2 beats full Kelly 3–7×.
• How should a router pick k distinct experts?Top-k MoE routing as a capped Hedge market: price min(1, λ w_i) with exact KL projection, regret vs the best fixed k-set held under k ln(N/k)/η+ηTk/2 in every run (41–58% of it), plain normalisation prices experts above 1 (282/300 rounds, loss understated 3.2×), and systematic sampling gives exactly k distinct experts with 8–14× lower variance.
• How should a router treat modules that are usually asleep?A self-financed wealth ledger for specialist modules that sleep: total wealth conserved exactly, sleeping wealth frozen (one private ledger per regime), regret ≤ ln(1/π_i)/η + η·n_i in the module's *own* awake time, entry of a module with wealth ε costs incumbents ln(1/(1−ε))/η; matches the regime oracle (0.1004 vs 0.1000) where forced-to-report Hedge sits at 0.30 and fixed share is worse.
• Can a module game a ledger by choosing when to sleep?When may a module choose to sleep? The ledger pays exactly leave-one-out savings ηW_A(1−p_i)S_i; sleeping *after* seeing losses gains wealth ηp_Bθ(1−θ)/2 (best 1/8) and takes the market in ~130 rounds with the router's loss unchanged; committed *before* serving it is a real saving; the deterring tax ηp_B/2 is a fixed share that halves honest specialists in 6 rounds.
• What does it cost to route between models with conditional markets, and what does a stake do to the answer?Conditional markets that route between models: inverse-propensity Brier is proper even when the router reads the report, exploration costs exactly 1+(K−1)e^{ω²/2τ²} in payment variance (probit: infinite for τ ≤ ω), and a stake gap distorts the reported gap by a closed-form fixed point with second-order harm.
• What share of the mass should a new module get?Admitting new modules to a Hedge/LMSR router: regret certificates obey a Kraft identity Σ e^{−c_i}=1, so uniform entry 1/(n+1) is the unique minimax rule; prior-optimal shares P_j/S_j cost H(P); the price of entry is exactly ln(1/π)/η independent of the quality gap.

All 13 Markets as routers projects →

Other research topics

Proper scoring & elicitation28Effort & peer prediction9Verification games & slashing19Detection & tolerances14Markets as routers13Prediction-market design9Paying contributors8Decentralised training systems23Digital twins & sim-to-real164LLM chip design loops40Robot manufacturing loops53Ambient AI assistant46Self-replicating manufacturing34Simulation-first design64Engineered clothing45Task-specific AI accelerators40Algorithmic chip-design loops42Open-source purpose-built robots44The software-engineering loop43Adversarial human imitation41Open-source residential construction41Autonomous multi-angle capture34Sensing, imaging and 3D31Energy supply and dense energy storage39Robot societies among people31Agentic co-design of low-cost robots27Laundry-hanging robots25Machine learning on qualitative data23Robots on the building site27Civilizations & group psychology1History & human sciences1

Produced with AI assistance (Claude). Results are from the code in this repository and are simulated or stylised unless the abstract says otherwise; nothing here implies affiliation with or endorsement by any lab, researcher or company cited. MIT licensed.