Skip to content
Crypto.world

Research

Constrained Policy Optimization for Provably Fair Order Matching

Matching engines execute millions of orders per session, and small systematic asymmetries in latency, order size and market access compound into persistent execution disparities that erode…

Constrained Policy Optimization for Provably Fair Order Matching
arXiv
2604.06522
Published
2026-04-07
Authors
Zehua Cheng, Zhipeng Wang, Wei Dai, Wenhu Zhang, Vadzim Mahilny, David Shi, Elena Jia, Jiahao Sun

AI summary

Overview

Research area: Algorithmic game theory and constrained reinforcement learning applied to financial market microstructure (automated order matching / limit order books), with a supporting on-chain verification layer.

Technical level: Advanced. The paper combines Constrained Markov Decision Processes, trust-region policy optimization on the Fisher information manifold, discrete-time PID control theory (Jury stability, Final Value Theorem), spectral normalization, and Ethereum settlement mechanics.

Scope (one sentence): The paper formulates fair order matching as a constrained optimization problem and proposes CPO-FOAM, a two-loop algorithm that separates an analytic trust-region policy update from a PID-controlled safety-margin controller, with stability and asymptotic-feasibility proofs and evaluations on LOBSTER NASDAQ data, crypto LOB data under MEV injection, and Safety-Gymnasium.

What This Paper Is About

Matching engines execute millions of orders per session, and small systematic asymmetries in latency, order size and market access compound into persistent execution disparities that erode participant trust. The authors argue that fairness should be an explicit, enforceable constraint inside the matching policy rather than an after-the-fact reporting metric, and they formalize this as a Constrained Markov Decision Process whose reward captures market quality and whose cost vector encodes group fairness (demographic parity, equalized odds) and individual Lipschitz fairness. The goal is an algorithm that keeps per-update constraint feasibility across multiple simultaneous fairness constraints while still making monotone progress on market quality, with stable multiplier dynamics and tractable computation.

Key Contributions

  1. CMDP formulation for auditable fair matching. Fair order matching is cast as a discounted CMDP whose cost vector encodes demographic-parity gaps, equalized-odds-type conditional disparities, and Lipschitz individual-fairness violations computed over rolling windows, giving an auditable interface between microstructure telemetry and enforceable constraints. Because execution outcomes are discrete, the authors derive differentiable, importance-weighted fairness surrogates.

  2. The CPO-FOAM algorithm. A two-stage update combines an analytic trust-region improvement step (solving a low-dimensional dual over the Fisher information manifold), a KL-nearest fairness projection, and PID-controlled adaptive safety margins; a pure recovery step is used when the feasible set is empty. The authors prove BIBO stability of the closed loop and asymptotic feasibility under bounded stochastic disturbances, plus a descent guarantee on cumulative violation energy during recovery.

  3. Empirical validation stack. A reproducible evaluation covering LOBSTER NASDAQ reconstructions across six non-stationary market regimes, scalability profiling up to K=500 action dimensions and M=8 simultaneous constraints, on-chain output-verifiable Ethereum settlement with gas-cost analysis, and domain-agnostic generalization on Safety-Gymnasium.

  4. On-chain proof system. An output-verifiable settlement design submitting market-state hashes, model-version hashes, allocation Merkle roots, fairness metrics (ΔDP, ΔEO, Lipschitz) and net token balances, with challenge-response adjudication; the paper also discusses process-verifiable alternatives (open replay with weights on IPFS/Arweave, permissioned replay via threshold key-sharing committees with BLS multi-signatures).

Main Findings

  • Throughput retained under constraints (equities): On LOBSTER NASDAQ data across six market regimes, CPO-FOAM recovers 95.9% of unconstrained throughput at a 2.5% constraint violation frequency (CVF).

  • Performance under adversarial order flow (crypto): On crypto-asset LOB data with MEV injection, the method captures 98.4% of the reward envelope at 3.2% CVF.

  • Pareto dominance over baselines: CPO-FOAM reports 0.95 bps spread, 2.5% CVF, and a violation transient length of 5 steps, described as strict Pareto dominance over the nearest baseline.

  • Rule-based engines fail on both axes: FIFO achieves only 4,200 orders/s throughput with effective spreads of 2.45 basis points and 100% constraint violation frequency.

  • Lagrangian and interior-point methods oscillate: Lagrangian PPO and RCPO produce transient recovery lengths exceeding 145 optimization steps with large violation area under the curve; vanilla CPO handles per-update near-feasibility but struggles with noisy constraint estimates and combinatorial action spaces; IPO introduces barrier-coefficient tuning sensitivity without bounding transient violations.

  • Unconstrained RL violates everything: PPO reaches theoretical efficiency ceilings but violates all fairness constraints.

  • Scaling: The method scales sub-linearly to M=8 simultaneous constraints, and cross-metric contamination remains below 0.022, supporting the weak-coupling assumption used to treat the multi-constraint controller as parallel single-input-single-output loops. Scalability is profiled up to K=500 action dimensions.

  • Robustness under regime shocks: Even under 5× news shocks, which substantially violate stationarity, CVF remains below 6.8%; the BIBO bound degrades gracefully, scaling linearly with the disturbance bound rather than diverging.

  • Domain-agnostic generalization: CPO-FOAM yields a 2.1× reward improvement on SafetyAntVelocity (Safety-Gymnasium) over the nearest baseline.

  • On-chain viability: Settlements clear within one Ethereum block (stated as ≤12 seconds finality) at ≤725k gas per batch, with false challenge rates driven below 0.001% by rapid off-chain recomputation.

  • Theoretical results: Lemma 5.5 bounds the surrogate approximation error by (L_H/μ)·δ; Proposition 5.6 gives a mixing-time concentration bound scaling with √(τ_mix ln(1/ζ)/T) where τ_mix = (1+ρ)/(1−ρ); Theorem 5.8 shows closed-loop BIBO stability and zero steady-state violation under gains α_I > 0, α_P < 1, 2α_P + α_I < 4 via the Jury criterion and the Final Value Theorem; Lemma 5.10 proves strict descent on cumulative violation energy; Proposition 5.11 shows spectral normalization yields deterministic (L, ℓ₂)-individual fairness.

Methodology in Plain English

The authors treat the matching engine as a learner that repeatedly decides how to allocate incoming orders across available counterparties, and they split the problem into two independent feedback processes so that neither has to do the other's job.

Inner loop — the geometry. Each update is chosen to maximize a linear approximation of market-quality reward, subject to linear approximations of the fairness constraints and a step-size limit measured in the Fisher information metric (the same trust region used in CPO). Because the resulting dual problem has only M+1 variables, it can be solved analytically and cheaply with a Newton-CG routine; the paper gives a closed-form direction in terms of the inverse Fisher matrix.

Outer loop — the control. Instead of trusting the noisy per-batch fairness estimates, a discrete-time PID controller watches the realized violation e = J_C − d and raises or lowers a safety margin ξ. Raising ξ tightens the constraint the inner loop must satisfy, creating a buffer zone proportional to estimation noise. This is the paper's answer to the "sawtooth" pattern of Lagrangian methods, which alternate between violating and over-correcting. If the margin becomes so tight that the trust region and constraints no longer intersect, a pure recovery step ignores the reward and moves purely downhill on constraint violation.

Architectural fairness. Individual (Lipschitz) fairness is not a probabilistic constraint at all: it is enforced by spectral-normalizing every layer of the policy network after each gradient step, so the bound holds regardless of what the optimizer does.

Differentiable surrogates. Because whether an order fills is discrete, group fairness costs are written as squared disparities in expected fill mass, using the policy's predicted allocation and exponential moving averages of group arrival rates (decay β = 0.999) as control variates; the trajectory-level aggregate is what the CMDP constrains.

Verification. Settlement outputs are committed on-chain as hashes, Merkle roots and fairness metrics, so participants can challenge inconsistencies without re-running the model.

Evaluation. The pipeline uses the JAX-LOB GPU simulator, LOBSTER NASDAQ reconstructions across six regimes, crypto LOB data with injected MEV, and Safety-Gymnasium for cross-domain checks, comparing against FIFO, Pro-Rata, PPO, Lagrangian PPO, RCPO, IPO and PID-Lagrangian baselines.

Why This Matters

Impact on research. The paper's distinctive move is to separate the memoryless geometric projection of CPO from the memoryful noise-robustness of PID control, then prove that the combination is stable and asymptotically feasible. This gives constrained RL a stability argument that neither CPO (which assumes accurate constraint estimates) nor PID-Lagrangian methods (which lack geometric projection guarantees) provides on their own, and it does so under a mixing-time concentration analysis rather than an i.i.d. assumption — a better fit for autocorrelated financial data. It also treats individual fairness as an architectural property and group fairness as a probabilistic constraint, a clean split that other sequential-fairness work could adopt.

Real-world applications (from the paper's framing):

  • Equity exchange matching engines needing auditable, regulator-facing fairness guarantees alongside throughput targets.
  • Crypto exchanges and dark pools where MEV extraction creates adversarial, non-stationary order flow.
  • On-chain settlement venues requiring output-verifiable execution with fairness metrics committed alongside allocation roots.
  • General safety-critical sequential control (demonstrated on Safety-Gymnasium) where multiple simultaneous constraints must hold with bounded transient violations.

Industry relevance. Regulatory emphasis is shifting toward auditable algorithmic governance, and the paper targets exactly that interface: fairness becomes an enforceable constraint with a named threshold and a verifiable on-chain record, rather than a post-hoc diagnostic. The reported gas cost (≤725k per batch) and one-block settlement are framed as economically viable, which speaks directly to deployment feasibility.

Future Directions

  • Handling regime breaks more rigorously. The paper's geometric-ergodicity assumption can be transiently violated during flash crashes, circuit breakers or stablecoin depegs. The authors suggest resetting the integral accumulator on a detected regime change (e.g., a CUSUM test on violation energy); whether that preserves the stability guarantees is left open.
  • Validating the weak-coupling assumption at larger M. The multi-constraint stability argument relies on off-diagonal Jacobian entries being small relative to diagonal ones. This held empirically at M=8 (contamination below 0.022), but the regime where fairness metrics genuinely interact is not characterized theoretically.
  • Extending the verification layer. The paper distinguishes output-verifiable settlement from stronger process-verifiable designs (open replay, threshold committees). A full treatment of the proof system's completeness, challenge economics, and gas scaling is a natural continuation.
  • Testing whether the fairness surrogates match real microstructure fairness. The reported fairness metrics are computed on differentiable expected-fill surrogates; validating them against realized discrete execution outcomes across more venues and asset classes is a clear next empirical step.

Target Audience

Researchers in constrained reinforcement learning and safe RL who want a worked example of combining trust-region projections with control-theoretic multiplier dynamics; algorithmic-trading and market-microstructure engineers interested in formal fairness guarantees for matching engines; mechanism-design and algorithmic-game-theory researchers working on auditable market governance; and blockchain engineers building verifiable ML settlement systems. Readers need comfort with CMDPs, KL trust regions and basic control theory (transfer functions, pole placement) to follow the proofs, though the problem framing and empirical results are accessible to a broader quantitative-finance audience.

Authors’ abstract

Automated matching engines execute millions of orders per session, yet systematic asymmetries in latency, order size, and market access compound into persistent execution disparities that erode participant trust. We formulate provably fair order matching as a Constrained Markov Decision Process and propose CPO-FOAM (Constrained Policy Optimization with Feedback-Optimized Adaptive Margins). An inner loop computes an analytic trust-region step on the Fisher information…

The full abstract on arXiv
Read the original paper