Certificate-Guided Learning and Residual-Load Repair in Matching Markets with Delayed Feedback

Matching repair after utility changes can reuse valid observations, but new evaluations must respect matching capacity and may return out of order. We study announced invalidations with bounded, possibly reward-dependent reporting delays and pending evaluations that do not occupy future matching capacity. Residual-load repair (RLR) combines sound outcome certificates with batched matching schedules for unequal sample deficits. Its complete dyadic quota schedule admits a sharp issue-round bound with coefficient $c_b<1.607$ relative to the terminal residual endpoint load, together with separate delay and evidence-lifetime bounds. RLR-P monitors complete issue-order prefixes without changing the sampling plan before acceptance. With a deterministic pure oracle, a single-repair coupling from the same drained initial state guarantees no increase in certification time, issued observations, or time to a reusable checkpoint. We also derive an information-load lower bound. On fixed priority-star markets with unknown Bernoulli gaps, Priority-Search attains the history-adjusted first-order constant for expected certification time as $\delta \downarrow 0$, under hypothesis-independent linear history scaling and sublogarithmic reporting delays. Paired simulations and measured-feedback replay quantify the trade-offs: in the replay, RLR-P has lower mean capped update-certification time than a monitored width-based baseline, at higher oracle CPU cost.