Skip to content

chc.games

Stability tier: experimental.

Game-theoretic control: agent equilibria + differentiable Stackelberg (leader) control.

Marketplaces have strategic, mobile agents, so SUTVA fails -- the platform is a Stackelberg leader over the agents' equilibrium, and its action is optimised accounting for the induced best response. These are the reusable methods (equilibrium solver + bilevel allocator); the benchmark task that scores them (the zone-incentive game) lives in causaldyn-bench.

The solver is a certified fixed point, not a fixed iteration count. fixed_point runs to a tolerance under lax.while_loop and differentiates by the implicit function theorem, so (a) non-convergence is reported in EquilibriumSolution instead of returned silently, (b) the backward pass costs one adjoint solve rather than a tape over every iterate, and (c) congestion_contraction_certificate certifies both passes at once: the adjoint iteration w <- w_bar + (dT/dx)^T w is the Neumann series for (I - dT/dx)^{-1}, so it converges exactly when the forward map contracts.

EquilibriumSolution

Bases: Module

A solved fixed point together with the evidence that it is one.

converged is a traced boolean, so it cannot raise inside jit -- checking it (or feeding it to a certificate) is the caller's job. That is the point: a non-equilibrium can no longer leave this module disguised as an equilibrium.

CongestionContractionCertificate dataclass

Numeric evidence that the certified Jacobian bound holds at the solved equilibrium.

EquilibriumMonotonicityCertificate dataclass

Global strong monotonicity of F = I - S, and the finite-perturbation bound it licenses.

Result 39 (b) bounds ||(I - S')^{-1}|| at the equilibrium -- an implicit-function derivative, so it prices infinitesimal perturbations and says as much. These are the global quantities: a modulus that holds at every point of a box, and a displacement measured at a perturbation of finite size.

EquilibriumTransferCertificate dataclass

Result 39: the equilibrium layer transfers the estimation-error ORDER and is non-expansive.

conditioning is the ambient ||(I - S')^{-1}||_2 for the UNDAMPED best response S -- the local (implicit-function) constant relating an infinitesimal operator perturbation to the equilibrium displacement. It is exactly 1 for every kappa, but only because the softmax Jacobian annihilates the constants: the value is attained in the mass direction 1, which equilibria never move along (sum x = mass is conserved). tangent_conditioning is the number that actually binds -- the same operator restricted to the fixed-mass tangent space 1^perp, equal to 1 / (1 + kappa * lambda_min^+(J)) and strictly below 1 for an interior distribution, though it approaches 1 as the equilibrium degenerates toward a vertex.

The contraction modulus of the damped solver is a different quantity again; naive_bounds records 1/mu and looseness how far it overstates the ambient truth (infinite once the solver stops contracting, while the equilibrium itself does not move).

project_simplex(v, z)

Euclidean projection of v onto {u >= 0, sum u = z} (Duchi et al. 2008).

fixed_point(f, params, x_init, *, tol=1e-06, max_iter=500)

Solve x = f(params, x) to a tolerance, differentiable in params (implicit, not tape).

tol is on the RELATIVE residual (see _relative_residual); the default sits an order of magnitude above the float32 rounding floor, so a converged solve is never reported as failed. Reverse-mode only: custom_vjp defines no JVP, so jax.jacfwd through the solve will fail. The gradient is the exact one at the fixed point, independent of how many iterations the forward solve took -- which is what makes the tolerance-based lax.while_loop usable at all, since JAX has no reverse rule for it.

softmax_congestion_equilibrium(attract, u, congestion, mass, beta=2.5, *, damping=0.5, tol=1e-06, max_iter=500)

Agent best-response equilibrium: the damped softmax congestion fixed point of the mass.

Agents flow toward higher value attract + u - congestion*x/mass (crowding lowers it); the iteration T(x) = (1-d)*x + d*mass*softmax(beta*value) converges to the Wardrop/logit equilibrium (sum x = mass, since the softmax Jacobian annihilates the constants). The uniform Jacobian bound certifies contraction when 0 < damping < 4/(2 + beta*congestion) -- at the default d = 1/2 that is exactly beta*congestion < 6. Above it the iteration may 2-cycle (the bound is sufficient, not necessary), which is why the result carries its own residual; the remedy is a smaller damping, not a different game, since the equilibrium itself stays non-expansive to operator perturbations (equilibrium_transfer_certificate). congestion_damping returns the fastest contracting choice for a given game.

congestion_damping(beta, congestion)

Modulus-optimal damping 4/(4 + beta*congestion) for the logit congestion iteration.

The two extreme eigenvalues of T' are 1-d and 1 - d*(1 + kappa/2); equalising their magnitudes gives d* = 4/(4+kappa), and any 0 < d < 4/(2+kappa) clears the uniform bound. So EVERY game has a contracting damping -- the kappa < 6 ceiling is a property of the hard-coded d = 1/2, not of the game. Kept opt-in: the default stays 1/2 so shipped numbers do not move.

congestion_contraction_modulus(beta, congestion, damping=0.5)

Certified contraction modulus mu = 1 - ||T'||_2 of the damped logit congestion map.

T'(x) = (1-d)*I - d*beta*c*(diag(s) - s s^T), and v^T (diag(s) - s s^T) v = Var_s(v), so by Popoviciu the softmax Jacobian has spectrum in [0, 1/2] (sharp at s = (1/2,1/2,0..)). T' is symmetric, hence ||T'||_2 <= max(1-d, d*(1 + beta*c/2) - 1), and that UNIFORM bound leaves a positive modulus iff 0 < d < 4/(2 + beta*c) -- at d = 1/2 exactly beta*c < 6. Both sides of the interval bind: at d = 0 the map is the identity and the 1-d branch is already 1. Sharp over the class, SUFFICIENT for a fixed game: the worst-case eigenvalue is attained only at a two-point uniform s; measured, the default map still converges at beta*c = 7 and 2-cycles from 8. Derived in validation/congestion_contraction.mac, cross-checked in .py, proved in proofs/congestion_contraction.v.

This is the SOLVER's rate, not the equilibrium's conditioning -- see equilibrium_transfer_certificate, where using 1/mu as a sensitivity constant is measured to overstate the truth by up to 200x.

congestion_contraction_certificate(beta=2.5, congestion=2.0, n_zones=12, seed=0, damping=0.5)

Solve one congestion equilibrium and confirm the contraction bound at the point returned.

equilibrium_monotonicity_certificate(beta=2.5, congestion=2.0, n_zones=6, mass=6.0, samples=400, perturbations=24, seed=0)

Measure the GLOBAL modulus Result 39 (b) left open, and the bound it buys.

F'(x) = I + kappa*J(s(x)) with J = diag(s) - s s^T a covariance matrix, so F' >= I at every x, not only at the equilibrium: F is 1-strongly monotone globally, and 1 cannot be improved because J annihilates the constants. The direction that saturates it is the one mass conservation forbids, so on the fixed-mass tangent space the modulus is strictly larger, bounded below by 1 + kappa*n*s_min^2 -- exactly attained at the two-point uniform s, the same configuration that makes Result 39 (a)'s Popoviciu bound sharp (validation/equilibrium_monotonicity.mac, proofs/equilibrium_monotonicity.v; z3 and cvc5 both return unsat on the negation at n = 3).

Measurements, each able to fail. ambient_modulus and tangent_modulus are minimised over a box rather than evaluated at a point; tangent_bound and box_bound are the certified lower bounds, the second needing neither a sample nor a solve. finite_monotonicity tests the definition itself on random pairs, which no derivative argument implies. displacement_ratio perturbs the operator by a finite amount and measures how far the equilibrium moves: strong monotonicity at mu caps it at 1/mu, one-for-one at mu = 1.

Reported at two scales on purpose, because the answers differ and only one of them is the headline. Over the whole box the tangent improvement evaporates: near a corner the softmax approaches a vertex, s_min collapses, and both the measured tangent modulus and its bound fall back to 1. The strictly-better constant of Result 39 (b) is a statement about a neighbourhood of an interior equilibrium, and local_tangent_modulus is where it has teeth -- quoting it globally is exactly the mistake this certificate exists to prevent.

equilibrium_transfer_certificate(n_zones=6, seed=0, incentive_cost=2.0, budget=3.0, steps=900, errors=(0.4, 0.2, 0.1, 0.05), kappas=(4.0, 5.0, 5.5, 5.8, 5.96))

Measure the two halves of Result 39 on the logit congestion Stackelberg game.

Half one, across kappas: the local conditioning ||(I - S')^{-1}||_2 -- both the ambient norm and its restriction to the fixed-mass tangent space, which is the one an equilibrium displacement can actually excite -- against the naive contraction constant 1/mu. Half two, across errors: perturb the agents' operator by e, re-solve the leader problem through the perturbed equilibrium, and score the resulting plan on the TRUE game -- the regret must be second order in e.

Both conditioning numbers are local: they are implicit-function derivatives at the equilibrium, so they bound the response to infinitesimal perturbations. The global inverse-Lipschitz statement -- strong monotonicity of F(x) = x - S(x) -- is equilibrium_monotonicity_certificate, which measures it over a box and at a finite perturbation size rather than deducing it from these derivatives.

The order half carries a binding regularity assumption, and the last two fields make it falsifiable rather than merely stated. The quadratic order needs the leader's optimum to move smoothly with the operator, which an active constraint destroys: with the budget constraint active the measured slope falls from 1.97 to 1.14, and at a vertex the argmax is locally constant, so the regret is identically zero across the whole sweep and the log-log slope does not exist. The vertex case is not a degraded rate but the absence of one, and any statement of the form "the equilibrium transfers the order" is vacuous there.

stackelberg_allocation(objective, n, budget, steps=400, lr=0.05)

Differentiable-bilevel leader allocation: maximise objective(u) over the budget simplex.

objective is evaluated through the equilibrium (so jax.grad differentiates the bilevel problem). Adam handles the scale; the plan is projected onto the budget simplex each step, and the best feasible allocation seen is returned.