PaperlayerView exact revision on arXiv

Source-linked AI summary

DataCupid: Stable Matching Repair for Training Data Acquisition with Delayed Feedback

He Sun, Junyuan Mao, Wenhao Jiang, Mingjun Xiao, Shinan Liu

arXiv:2610.12960v1cs.LGcs.ITmath.IT

TL;DR

After utility updates, matching platforms must certify a stable allocation while respecting capacity and handling delayed evaluations. The paper develops repair and certification methods, and shows Priority-Search attains the history-adjusted information-load constant on fixed priority-star markets under stated conditions.

  • Problem

    How retained observations, matching capacity, and delayed reporting jointly determine the time to certify an updated allocation remains the central repair question.

    Source: §1 · p. 2

  • Method

    RLR schedules unequal sample deficits through feasible matching batches, while Priority-Search tests candidates in public priority order on fixed priority-star markets.

    Source: §1 · p. 2

  • Results

    On fixed priority-star markets, Priority-Search attains the history-adjusted information-load constant for expected certification time as δ ↓ 0 under linear hypothesis-independent histories and sublogarithmic delays.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Endpoint congestion and report barriers determine how residual evidence becomes repair time, while general matching-instance optimality remains open.

    Source: §8 · p. 10

    RLR meets prescribed precision but may oversample outcome-irrelevant edges and is not generally statistically optimal.

    Source: §7 · p. 9

Abstract

from arXiv · show

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. Residualload 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 cb < 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, PrioritySearch attains the history-adjusted first-order constant for expected certification time as {\delta} {\sim} 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.

1 INTRODUCTION

Matching platforms must learn uncertain utilities under coupled capacity constraints, since requester favorites may not form a stable matching (Liu et al., 2020; Basu et al., 2021). DataCupid studies repair after announced invalidations, reusing valid observations while new evaluations return asynchronously.

Why the location of missing evidence matters

  • Equal sample totals can require different repair times: disjoint endpoints permit Nb observations in b rounds, while pairs sharing one requester require at least Nb rounds.This motivates residual endpoint load, the largest total sample deficit incident to any requester or provider; reward-dependent delays also make early-arriving results potentially biased.Source: §1 · p. 2

Outcome certificates

  • Outcome certificates stop repair once every utility matrix within current confidence bounds yields the same requester-optimal matching.The repair protocol organizes how evidence is collected and incorporated; prior partial-preference, PCOS, and pervasive-matching methods can certify outcomes without resolving every preference comparison.Source: §1 · p. 2

Residual-load repair

  • RLR packs unequal deficits into feasible matchings with doubling targets and one feedback barrier per phase, attaining an issue-round bound of cb times terminal residual endpoint load, where cb < 1.607.Reporting delay adds a separate term for each nonempty phase, and an evidence-lifetime analysis bounds cumulative new samples across updates while observations remain valid.Source: §1 · p. 2

Prefix-monitored RLR

  • RLR-P checks certificates whenever complete issue-order prefixes become available, preserving valid confidence bounds under reward-dependent delays without changing RLR’s sampling plan before certification.For a deterministic pure oracle and one repair from the same drained initial state, it certifies no later, issues no more observations, and receives all issued feedback no later than RLR; outstanding results remain reusable.Source: §1 · p. 2

Information-load bounds and PrioritySearch

  • A change-of-measure lower bound credits historical evidence while imposing endpoint capacities on new samples; PrioritySearch attains the history-adjusted information-load constant on fixed priority-star markets as δ ↓ 0.The guarantee assumes unknown Bernoulli utilities with nonzero fallback gaps, hypothesis-independent history scaling linearly with log(1/δ), and sublogarithmic reporting delays; paired simulations and measured-feedback replay examine certification-versus-computation trade-offs.Source: §1 · p. 2

2 RELATED WORK

The related work frames repair as a distinct problem of reusing retained evidence under residual matching-capacity constraints after announced invalidations, while drawing on established matching, inference, and delayed-learning ideas.

2 RELATED WORK

  • Stable matching and competing-bandit methods establish allocation and exploration, while inference and partial-preference methods supply stopping logic; this work schedules residual multiplicities across delayed phases and evidence lifetimes.Bipartite edge coloring is classical and also appears in PCOS.Source: §2 · p. 2
  • Crowdsensing data-trading work combines privacy, stable matching, competing bandits, and decentralized conflict mitigation, whereas this work studies retained evidence and matching capacity in repair after announced invalidations.Source: §2 · p. 2
  • Unlike statistical allocation, batch-complexity, and historical-information work, this analysis assumes announced invalidations and exact mean preservation on retained edges, adding matching-capacity load to residual information.Priority-Search builds on threshold identification and ordered good-arm search; cascading and satisficing bandits use related stopping ideas under different feedback and objectives.Source: §2 · p. 3
  • Prior delayed-learning and asynchronous-thresholding work has established guarantees; RLR-P handles reward-dependent return order using complete issue-order prefixes and changes planning state only at the original barrier.The setting assumes sufficient time between updates for each nonfinal repair to complete.Source: §2 · p. 3

3 PROBLEM FORMULATION

The formulation studies requester-proposing deferred acceptance under epoch-wise utility changes, delayed reward feedback, and announced invalidations. Repair performance is measured by positive-part dynamic stable regret and stability violations.

3 PROBLEM FORMULATION

  • The market has N requesters and K providers (1 ≤ N ≤ K), a fixed public feasible graph and strict provider priorities, and at most one match per participant each round.Provider acceptability is known through the graph, while requester acceptability is unknown; the outside option has utility zero.Source: §3 · p. 3
  • Within each epoch, edge means are fixed before learning and rewards are bounded in [−1, 1] with conditionally σ-sub-Gaussian noise; bounded reporting delays may depend on rewards.Decisions use only feedback that has arrived, and pending evaluations do not occupy future matching capacity.Source: §3 · p. 3
  • At each epoch start, a public invalidation set covers every changed edge; false positives are allowed, and valid observations outside the set are retained.Multi-update guarantees require each nonfinal repair to be certified and drained before the next notification; earlier interruption follows a fallback, not a completed-repair guarantee.Source: §3 · p. 3
  • The target outcome is requester-proposing deferred acceptance with a fixed provider-ID tie rule and the outside option preferred at utility zero.This is the requester-optimal outcome under the chosen refinement.Source: §3 · p. 3
  • Repair performance uses positive-part dynamic stable regret and stability violations, which count ε-blocking pairs and requesters assigned utility below −ε.Provider rationality is built into the graph.Source: §3 · pp. 3–4

4 CERTIFICATES AND VALID EVIDENCE

This section defines sound outcome certificates and valid evidence for stopping decisions, while leaving evaluation selection to the repair protocol. It also describes oracle variants and the evidence assumptions used within each validity lifetime.

Certificates and valid evidence

  • A sound oracle returns unresolved or a matching equal to DA(ν) for every ν in B, while the repair protocol selects evaluations.A resolution radius ρ_h guarantees acceptance of boxes containing μ_h once their maximum width is at most ρ_h; it supports the repair-time bound but is not a policy input.Source: §4 · p. 4
  • Forced-P combines canonical trace checking with mutual-first-choice contraction; Hybrid adds exhaustive possible-weak-stability testing, and PSM-P uses the published pervasive oracle on certified-positive complete markets.When the true weakly stable matching is unique, its exclusion margin gives ρ_h = β/3; exhaustive enumeration is exponential and restricted to small markets.Source: §4 · p. 4
  • Within each validity lifetime, intervals start at [−1, 1] or a valid prior and use complete issue-order prefixes; empirical Bernstein additionally assumes an unchanged i.i.d. bounded stream.The empirical Bernstein condition applies within each lifetime.Source: §4 · p. 4

5 PREFIX-MONITORED RESIDUAL REPAIR

RLR-P monitors completed issue-order prefixes while preserving RLR’s sampling plan, with guarantees for evidence validity, repair cost, and reusable checkpoints. On a restricted priority-star class, Priority-Search attains a history-adjusted first-order certification-time constant, alongside a general information-load lower bound.

5 PREFIX-MONITORED RESIDUAL REPAIR

  • Exactly L(x) rounds are necessary and sufficient to issue integer quota deficits as feasible matchings, and all prescribed feedback arrives within d further rounds after the final issue.Here x_e = [z_e − m_e]+, with m_e the valid completed count; the delay bound assumes each issued observation reports within d rounds.Source: §5 · p. 4
  • With probability at least 1 − δ, every issue-ordered complete-prefix interval contains its current mean under adaptive sampling and reward-dependent bounded delays.The guarantee requires predictable designation of learning observations and a confidence-record horizon covering the lifetime indices and prefixes used.Source: §5 · p. 5
  • From the same drained initial state, RLR-P’s issue sequence is a prefix of RLR’s and it does not increase certification time, issued observations, or time to a reusable checkpoint.The coupling applies to one repair; on the T-Prefix event, every RLR-P output is correct.Source: §5 · p. 5
  • The dyadic plan has a sharp issue-round coefficient below 1.607 relative to terminal residual endpoint load, with separate delay and evidence-lifetime bounds.The coefficient is sharp for complete execution of the prescribed plan, while successful certification may stop it earlier; the bounds require an unchanged epoch and a covering confidence-record envelope.Source: §5 · pp. 5–6

5.1 A STRUCTURED UNKNOWN-GAP CHARACTERIZATION

  • On each fixed priority-star instance, mean-blind Priority-Search is uniformly δ-correct and achieves limδ↓0 Eτδ/log(1/δ) = L⋆(p, c).The result assumes hypothesis-independent initial-history sizes scaling with log(1/δ), no pending reports, and sublogarithmic reporting delays; draining after certification preserves the first-order limit, and no general matching instance-optimality is claimed.Source: §5.1 · p. 7
  • For general markets, minimizing the residual-load objective under different-outcome information constraints yields a necessary elapsed-time bound, while delay may add further cost.The lower bound assumes independent Bernoulli edge rewards and compared markets with a common conditional reporting channel; historical pending feedback must be absent or uninformative as specified.Source: §5.1 · p. 7

6 EXPERIMENTS

The experiments test residual-load scheduling, unknown-gap PrioritySearch, monitored certificate comparisons, and measured-feedback replay. The reported findings are scoped to these settings and do not establish universal dominance or general matching instance optimality.

Prescribed-load and prefix checks

  • Exact decomposition reached the endpoint-load lower bound on all 900 frozen-quota instances, while greedy decomposition tied exact issue time on 895/900, with a largest observed ratio of 1.0922.These evaluator-controlled scheduling tests support an exact resource identity, not a broad CPU or regret advantage for exact packing.Source: §6 · p. 8

Unknown-gap structured characterization

  • At ℓ = 300 with zero history, unknown-gap PrioritySearch had normalized certification time 197.487 versus the first-order constant 183.719 on the fixed priority-star class.The 5,600-trial run had no observed wrong output; positive empirical time remained after history removed first-order load, reflecting testing and finite-sample overhead, not evidence of nominal error probabilities or general matching instance optimality.Source: §6 · p. 8

Native certificate comparison with monitoring

  • For N = 3, RLR-P, Width-P, and PCOS-A4 completed 18, 16, and 13 paths at budget 30,000, and 23, 22, and 20 at budget 100,000.The E5 suite covered 120 paired markets and 1,680 branches, retaining every capped path; the finite-budget comparison does not establish universal dominance or computational speedup.Source: Table 1 · p. 9, §6 · p. 9

Independent histories and measured feedback

  • RLR-P reduced update-certification time by 4,437 rounds versus Width-P but increased cumulative oracle CPU by 4.48 seconds in the measured-feedback replay.RLR-P minus Width-P update-regret difference was +811; 95% CIs were [−8, 856, −148] for update-certification, [−1, 023, 3, 111] for update regret, and [1.35, 7.49] for cumulative oracle CPU. These finite-budget comparisons do not imply deployment speedup or uncensored stopping-time dominance.Source: Table 2 · p. 9, §6 · p. 9

Interpretation

  • The interpretation reports that monitoring can reduce one repair’s certification cost under the fixed planner, while PrioritySearch matches its constant only on the priority-star family.The evidence establishes neither RLR-P dominance nor general matching instance optimality.Source: §6 · p. 9
  • The phase excess Ω is a bottleneck change, distinct from the shadow suffix and drain.The appendix separates these components; the evidence does not establish general matching instance optimality.Source: §6 · p. 9

7 LIMITATIONS

The guarantees rely on restrictive repair and oracle assumptions, while the measured replay is finite and uses a supported PSM-P stopping oracle rather than full E-PSM.

7 LIMITATIONS

  • RLR meets prescribed precision but may oversample outcome-irrelevant edges and is not generally statistically optimal; its repair theory is delimited by announced invalidations, nonoccupying jobs, and sufficient dwell.Source: §7 · p. 9
  • T-Monitor assumes a deterministic pure oracle and covers only one repair, so it gives no multi-update or CPU-time dominance.Source: §7 · p. 9
  • T-Star requires a fixed priority-star graph, independent Bernoulli streams, hypothesis-independent histories, a common report channel, and sublogarithmic delay.Source: §7 · p. 9
  • The measured replay is a finite empirical distribution, and its supported PSM-P stopping oracle is not full E-PSM.Source: §7 · p. 10

8 CONCLUSION … A.4 DYADIC LOAD, WAITING, AND LIFETIME PROOFS

RLR’s complete dyadic schedule has a sharp issue-round bound, while RLR-P preserves valid complete-prefix evidence and can export drained checkpoints. The proofs establish limits and conditions for matching schedules, prefix validity, monitor coupling, and repair bounds.

8 CONCLUSION

  • RLR-P acts only on complete prefixes and exports checkpoints after drainage, while RLR follows the full dyadic schedule.If monitoring succeeds, RLR-P cancels only the unissued suffix; its issue sequence is therefore a prefix of RLR’s.Source: §8 · p. 10, §A.3 · p. 13, §A.4 · p. 14

A.1 PROOF OF LEMMA 1

  • A multigraph edge-coloring gives a feasible issue schedule of length L(x), and endpoint demand makes that length necessary; bounded delays add at most d rounds before returns are available.With a common deterministic delay, neither the issue-round nor return-availability lower bound can be shortened.Source: §A.1 · p. 13

A.2 PROOF OF T-PREFIX

  • Simultaneous confidence coverage holds for every existing issue-ordered prefix, including report-time-selected complete prefixes, but not for arbitrary sets of arrived observations.The anytime alternative requires exogenous lifetime indices and does not automatically cover reward-adaptive reset times; the empirical Bernstein construction assumes i.i.d. bounded observations within a lifetime.Source: §A.2 · p. 13

A.3 PROOF OF T-MONITOR

  • From the same drained initial state, RLR-P’s deterministic stateless-oracle coupling guarantees no increase in certification time, issued observations, or time to a reusable checkpoint.The guarantee relies on shared environment-indexed rewards and issue-time report dates; it need not hold for stateful or call-order-randomized oracles or retroactive reporting changes.Source: §A.3 · p. 13

A.4 DYADIC LOAD, WAITING, AND LIFETIME PROOFS

  • The complete dyadic schedule has sharp issue-round coefficient cb < 1.607 relative to terminal residual endpoint load; requester-centered stars attain coordinate bounds, with ratio 19/12 at b = 4.The conclusion also identifies Priority-Search’s information constant on a structured unknown-gap class and leaves general matching instance optimality open.Source: §8 · p. 10, §A.4 · p. 14
  • The sufficient history-independent dwell condition is bh∆E + dBh, while the history-sensitive repair bound is cbhL(Dh) + dBh.The report-drain contribution is at most dBh rounds.Source: §A.4 · p. 14
  • Across repairs, retaining complete drained records lets lower targets issue nothing and higher targets telescope from retained counts, avoiding repeated delay-sized suffixes.Discarding pending observations at every early stop would invalidate the telescope and can repay a delay-sized suffix after each update.Source: §A.4 · p. 14

A.5 SERVICE ALLOCATION AND CAPPED-LOSS PROOF · A.6 CORRECT RESTRICTED COSTS AND PAIRED EVALUATION · B EARLIER PUBLIC-GAP FALLBACK BENCHMARK

These sections establish bounds for repair costs and monitoring, define how capped outcomes are evaluated, and present a separate public-gap fallback benchmark. The results include conditions on when monitoring saves work and when added history reduces residual load.

A.5 SERVICE ALLOCATION AND CAPPED-LOSS PROOF

  • Before certification, exploratory matching changes at most 2mt additional assignments and incurs positive-part regret at most 2ah + 4mt; capped losses and violations use universal bounds off the confidence event.The violation bound is (K + 2N + 1)(ah + 2mt); the universal caps are 2NT for regret and N(K + 1)T for violations.Source: §A.5 · p. 15
  • For the complete dyadic schedule, phase-bottleneck overhead satisfies Ω ≤ (cb − 1)L(D), with equality exactly when one endpoint maximizes every phase..Source: §A.5 · p. 15
  • Under the single-repair coupling, a shadow monitor’s accepted output allows deletion of the remaining canonical learning suffix, with nonnegative regret difference when that output is correct.The issued-observation difference through budget B equals the size of the unissued suffix after the earlier of monitor acceptance, certification, and B.Source: §A.5 · p. 15
  • Valid added history reduces the fixed residual load, and the reduction is strict exactly when every endpoint maximizing the original load loses positive residual..Source: §A.5 · p. 15
  • Caching answers for exactly equal complete inputs to a deterministic pure oracle preserves responses, actions, certification, readiness, and loss while retaining every logical query.The equivalence does not permit width-, count-, rounded-, or skipped-box cache keys.Source: §A.5 · p. 15

A.6 CORRECT RESTRICTED COSTS AND PAIRED EVALUATION

  • Restricted mean completion time is the area under the non-completion curve; a capped path contributes B, and pre-B process failures remain incomplete with identification intervals.Fixed-budget regret is identified when the service-block ledger reaches B; otherwise it is reported with its observed prefix and deterministic loss bound.Source: §A.6 · p. 16

B EARLIER PUBLIC-GAP FALLBACK BENCHMARK

  • With public two-point means and d(δ) = o(log(1/δ)), a uniformly δ-correct fallback procedure attains a reference-market first-order time whose limit inferior lower-bounds every uniformly correct procedure.The result assumes public gaps and concerns the all-negative reference instance; it is not the unknown-gap PrioritySearch theorem or an optimality result for RLR-P.Source: B EARLIER PUBLIC-GAP FALLBACK BENCHMARK · p. 16

B.1 FINITE-CONFIDENCE FALLBACK BENCHMARK … C.4 FIRST-PASSAGE ASYMPTOTICS WITH ARBITRARY LINEAR HISTORY

The fallback benchmark establishes finite-confidence information and sampling bounds while showing why warm-history placement matters; the priority-star analysis then connects stable outcomes to information-load lower bounds and time-uniform sign tests with first-passage guarantees.

B.1 FINITE-CONFIDENCE FALLBACK BENCHMARK

  • For cold starts, the one-phase fallback benchmark’s upper/lower ratio is O(log(|Ec|/δ)/log(1/δ)); the same order holds when me ≤ ae/2.The benchmark uses public gap magnitudes, not RLR; arbitrary warm starts have no multiplicative guarantee, and resetting can waste evidence when only dispersed edges need new observations.Source: §B.1 · p. 17

B.2 FULL FINITE-CONFIDENCE FALLBACK PROOF

  • On the reference market, a fixed-quota test uses initial evidence and scheduled deficits to obtain uniformly δ-correct fallback signs, with the proof deriving its lower bound by change of measure.For each edge, (me + E N_new_e)κe ≥ kl(1−δ, δ); Hoeffding bounds and a union bound establish the upper guarantee, without a multiplicative claim for arbitrary warm histories.Source: §B.2 · p. 17

B.3 PROOF OF THEOREM 5

  • The phase-based sign test freezes edges at likelihood thresholds, has error at most δ/2 by a maximal inequality and union bound, and terminates almost surely.Its proof also matches upper- and lower-limit load arguments, including critical and oversupplied histories.Source: §B.3 · pp. 17–18

C.1 MARKET STRUCTURE

  • In each priority-star group, the shared provider goes to the highest-priority requester whose mean exceeds θ; the outcome-relevant set is exactly the prefix through that requester.Each requester in the prefix has a one-coordinate alternative that changes the outcome, while later coordinates need not be identified.Source: §C.1 · p. 18

C.2 INFORMATION-LOAD LOWER BOUND

  • The information-load lower bound is pointwise for each fixed nonthreshold instance, while correctness is uniform over the priority-star class.It counts issued rewards even when pending, and excludes history counts or reporting channels that depend on the hypothesis.Source: §C.2 · pp. 18–19

C.3 A TIME-UNIFORM, MEAN-BLIND SIGN TEST

  • The time-uniform, mean-blind test controls error over all M potential tests, covering adaptive entry into later priority positions and reward-dependent report order.It scans completed historical prefixes in order, caching out-of-order returns until gaps close.Source: §C.3 · p. 19

C.4 FIRST-PASSAGE ASYMPTOTICS WITH ARBITRARY LINEAR HISTORY

  • For each candidate with k = kl(p, θ) > 0, the first-passage time scales as ℓ/k, with normalized convergence also holding in L1 across undersupplied, critical, and oversupplied histories.The expectation argument establishes uniform integrability, with E[T_δ^2] = O(ℓ^2).Source: §C.4 · p. 19

C.5 PRIORITY-SEARCH EXECUTION AND UPPER BOUND · D REFERENCE CERTIFICATES AND WIDTH-GREEDY REPAIR

These sections establish Priority-Search’s expected-certification bound under delayed feedback and distinguish outcome certification from trace identification. They also present sound reference certificates and a feasibility-based parallel repair schedule.

C.5 PRIORITY-SEARCH EXECUTION AND UPPER BOUND

  • Priority-Search scans edge histories, issues candidates in public priority order, and runs disjoint groups as physical matchings without using gaps, signs, or true prefixes.A negative decision activates the next candidate; the first positive decision ends the group.Source: §C.5 · p. 20
  • Priority-Search is uniformly δ-correct and finishes any finite graph almost surely.Off the error event, each group visits exactly its true candidate prefix and outputs correctly.Source: §C.5 · p. 20
  • Reporting delay changes availability and first-passage rounds, not reward sequences; when d=o(log(1/δ)), it does not change the asymptotic constant.The delay audit treats d=0 and d=⌊ℓ⌋ as finite-run schedule diagnostics.Source: §C.5 · p. 20
  • Theorem 4’s expected-certification upper bound matches the lower bound under the stated fixed-market conditions.The result relies on a fixed finite graph, i.i.d. Bernoulli candidate streams, hypothesis-independent history sizes, nonoccupying pending work, and sublogarithmic reporting delays.Source: §C.5 · p. 20

D REFERENCE CERTIFICATES AND WIDTH-GREEDY REPAIR

  • A unique stable outcome need not determine a unique DA trace, and identifying a differing first proposal can require Ω(log(1/δ)/η^2) observations.In the stated two-market example, the outcome is the same while the first canonical proposals differ; requester 2’s strict preference and requester 1’s acceptability of b certify the allocation at fixed precision.Source: D REFERENCE CERTIFICATES AND… · pp. 20–21
  • A forced-pair reduction gives a sound polynomial-cost outcome oracle that certifies Proposition 5 without resolving requester 1’s initial ordering.Its comparison cost is O((N + 1)(|E| + N)(K + 1)); it is sufficient rather than complete, and stronger partial-preference certificates exist.Source: D REFERENCE CERTIFICATES AND… · p. 21
  • When a matching is the unique possible weakly stable matching, it is the refined DA outcome throughout the box; positive β gives a width threshold of β(µ)/3.β(µ)>0 exactly when M⋆ is the unique weakly stable matching, and every sound box of maximum width at most β(µ)/3 has exactly one passing matching.Source: D REFERENCE CERTIFICATES AND… · p. 21
  • O-CGR batches wide edges in a greedily selected matching, doubles their sample counts, and waits for all issued rewards before updating intervals or launching another group.It executes concurrent independent batches, uses the old matching while waiting, and is a feasibility-based schedule rather than an optimal experiment allocation; it may sample edges irrelevant to the eventual certificate.Source: D REFERENCE CERTIFICATES AND… · p. 22

E REFERENCE LIFETIME AND INFORMATION RESULTS · F DETAILS OF OUTCOME CERTIFICATION AND MODULAR REPAIR · G EXCLUSION CERTIFICATES, SCOPE, AND INFORMATION ACCOUNTING

These parts develop reusable certificate-lifetime accounting, sound outcome-certification details, and information-load constraints on what retained history and matching capacity can achieve. They also delimit the guarantees: information-load constraints can limit parallel speedup independently of certification needs, the greedy schedule is feasible but not proved optimal under adaptive evidence reuse, and updates reset prior counts only where validity was lost.

E REFERENCE LIFETIME AND INFORMATION RESULTS

  • Completed O-CGR repairs are requester-optimal with probability at least 1−δ, with lifetime accounting charging doubling batches and bounded reporting delays.The accounting applies to sound oracles with positive resolution radii, but gives no universal factor-N speedup; frequent updates or vanishing radii can prevent sublinear regret bounds.Source: E REFERENCE LIFETIME AND INFORMATION… · pp. 22–23

F DETAILS OF OUTCOME CERTIFICATION AND MODULAR REPAIR

E REFERENCE LIFETIME AND INFORMATION RESULTS

  • An optional empirical-Bernstein extension gives simultaneous lifetime coverage for i.i.d. edge rewards using complete chronological prefixes, even with reward-dependent reporting delays.It requires i.i.d. rewards within each lifetime and does not replace the main martingale assumption or guarantee arbitrary martingale rewards.Source: E REFERENCE LIFETIME AND INFORMATION… · p. 23
  • For identical pre-update histories, any uniformly δ-correct repair needs at least log(1/δ)/(64η^2) fresh pulls in the pivotal construction when δ ≤ .1.The lower bound assumes shared reporting and no uncharged historical pending information; repeated pivotal updates yield the per-repair bound by summation.Source: E REFERENCE LIFETIME AND INFORMATION… · p. 24

F DETAILS OF OUTCOME CERTIFICATION AND MODULAR REPAIR

  • Contracting certified mutual first-choice pairs and extending them back preserves a bijection of stable matchings and requester-optimality; the resolution radius is not a minimal identification statistic.The oracle’s trace check preserves accepted boxes, but this acceptance-region dominance does not establish that its sampler dominates query-directed CGR.Source: F DETAILS OF OUTCOME CERTIFICATION AND… · pp. 24–25

G EXCLUSION CERTIFICATES, SCOPE, AND INFORMATION ACCOUNTING

  • The exhaustive oracle certifies an outcome when exactly one allocation passes its possible-set test, while Hybrid first tries forced pairs and otherwise enumerates possible allocations.Enumeration can grow exponentially: complete 3 × 3 and 5 × 5 markets have 34 and 1,546 feasible matchings, respectively; partial enumeration cannot justify a certificate.Source: G EXCLUSION CERTIFICATES, SCOPE, AND… · p. 26
  • The capacity-constrained information bound combines alternative-specific information demands with per-endpoint round loads, but is necessary rather than sufficient for delayed stopping time.Shared endpoints can force additive elapsed time for competing demands, whereas disjoint endpoints may require only the larger demand; delayed arrival can add further waiting.Source: G EXCLUSION CERTIFICATES, SCOPE, AND… · p. 27
  • Identifying a prescribed first proposal can have divergent information cost as η shrinks, although sound outcome certification retains a positive uniform resolution radius in the stated construction.The comparison concerns distinct certification objectives and does not establish dominance over prior outcome-based methods or match expected stopping lower bounds to finite-horizon upper bounds.Source: G EXCLUSION CERTIFICATES, SCOPE, AND… · p. 28
  • Observations already below the selection-threshold confidence width need no new pulls, and an update resets the prior count only where validity was lost.Source: G EXCLUSION CERTIFICATES, SCOPE, AND… · p. 28
  • Information-load capacity constraints can limit parallel speedup despite many available participants, and the feasible greedy schedule is not proved to attain the bound under adaptive evidence reuse.These constraints are distinct from the information needed to certify an outcome.Source: G EXCLUSION CERTIFICATES, SCOPE, AND… · p. 28

H REVISION EXPERIMENTS AND REPRODUCIBILITY … I.2 KNOWN-HYPOTHESIS LIKELIHOOD BENCHMARK

The revision evaluates reproducibility and empirical training-feedback repairs, compares residual-load schedules with width-based policies, and benchmarks a known-hypothesis likelihood policy across confidence levels and history fractions.

H REVISION EXPERIMENTS AND REPRODUCIBILITY

  • The revision reports 810 paired tasks, 2,250 method trajectories, 4,350 epoch records, and 9,000 newly executed training/evaluation jobs; new runs were local CPU runs, not GPU runs.Training-replay uncertainty uses ten split-level averages rather than treating 30 policy seeds as independent datasets; split variation does not imply independent population samples.Source: H REVISION EXPERIMENTS AND… · pp. 28–29
  • Binary and ten-class training protocols used fixed utility scales, and both result sets were retained after binary failure without claiming a preregistered study.The protocols used different tasks, feature views, anchor counts, and utility scales; the replay used ten stratified digits splits and 30 bootstrap trials per buyer–offer pair, with no held-out scores selecting offers or model parameters.Source: H REVISION EXPERIMENTS AND… · pp. 29–30
  • Training replay sampled stored reward–duration pairs together, preserving their within-pool dependence, while a 1 ms decision slot converted measured job durations into feedback delays.Rewards were bounded in [−1, 1], and the empirical maximum delay bounds this replay only, not future training jobs; the ten-class EB ablation reused pools and seeds without new training jobs.Source: H REVISION EXPERIMENTS AND… · p. 30
  • The annotation revision replaced 24 of 120 labels with 20% symmetric noise, changing the target allocation in five of ten splits; the fresh-offer revision changed it in one of ten.The annotation corruption was fixed across trials and designed as a specified quality-shift stress, not naturally occurring commercial deterioration; the fresh-offer condition primarily tests outcome revalidation.Source: H REVISION EXPERIMENTS AND… · pp. 30–31
  • Implementation checks covered stability equivalence, matching feasibility, cyclic perturbations, and capped baselines, but finite checks do not establish statistical coverage for every instance.The trajectory audit found no incorrect output among 2,583 completed epochs and verified pathwise loss bounds in 2,565 completed batch-protocol epochs; proofs remain necessary.Source: H REVISION EXPERIMENTS AND… · p. 31

I RESIDUAL-LOAD EXPERIMENT PROTOCOL

  • Residual-load experiments paired four scheduling rules across 8-, 16-, and 32-market sizes, and reused ten-split empirical quality-shift pools to compare stopping rules, schedules, and retention versus reset.All failures were charged through the horizon; the empirical revision used two 300,000-round epochs, with failed first epochs triggering unmatched fallback.Source: I RESIDUAL-LOAD EXPERIMENT PROTOCOL · p. 31

I.1 WIDTH-ADAPTIVE FOLLOW-UP AND LIMITS OF THE GUARANTEE

  • In measured-delay Hybrid replay, RLR-W retain minus Width retain was +5,280 (95% interval [2,686, 8,264]) and dyadic RLR retain minus Width retain was +3,999 ([1,412, 7,220]); neither improved over Width.Retain-minus-reset regret differences were −8,102 for RLR-W and −9,384 for dyadic RLR, both with intervals excluding zero; the intervals are descriptive, and the replay reuses the same ten splits.Source: §I.1 · p. 32

I.2 KNOWN-HYPOTHESIS LIKELIHOOD BENCHMARK

  • Across 28 configurations and 2,800 reference runs, expected-time estimates were normalized by log(1/δ) and compared with analytic first-order load; no incorrect sign was observed.The runs used seven log-inverse-error values and four history fractions, with immediate feedback; finite-confidence overhead remained visible, and the simulations cannot verify error probabilities such as exp(−3000).Source: §I.2 · pp. 32–33

J PREVIOUS CERTIFICATE AND REUSE EXPERIMENTS … P.3 A CERTIFICATE NEED NOT LEARN EVERY LOSING COMPARISON

This section examines how certificates for deferred-acceptance proposal traces support evidence-retaining repair after announced preference changes, combining certificate and reuse experiments with guarantees on confidence, repair cost, identification, stability, and delay. It distinguishes identifying a pivotal preference from resolving every comparison a certificate requires.

J PREVIOUS CERTIFICATE AND REUSE EXPERIMENTS

  • At the exact tie, Forced-P completed 0/30 trials, while Hybrid-P and PSM-P each completed 30/30.Across reuse epochs every Hybrid/PSM repair completed, whereas Forced-P failed initially; at size three, Hybrid-P, PSM-P, and PCOS-A4 certified 20/30, 21/30, and 17/30. Signed-Jester completion was 5/30 versus 4/30; ten-class empirical-Bernstein stream completion was 21/30 for Hybrid and Forced versus 12/30 for Prefix. Low regret from C-UCB/C-ETC did not imply certification, and the repair protocols were not competitive stationary-regret policies.Source: J PREVIOUS CERTIFICATE AND REUSE… · pp. 33–34, Table 6 · p. 34
  • 40,545 versus 46,820 mean regret: Hybrid-retain improved on reset by 6,275 (95% interval [−9,374, −3,463]), and both completed 20/30 double-epoch runs.These controlled label-quality revisions used measured delays and empirical Bernstein intervals; they are not commercial-deployment results.Source: J PREVIOUS CERTIFICATE AND REUSE… · p. 34, Table 7 · p. 34

K A CERTIFICATE FOR THE PROPOSAL TRACE

  • Certifying every query in a completed canonical trace fixes the requester-optimal DA outcome throughout the interval box, with a full check costing O((|E| + N)(K + 1)) comparisons.The certificate fixes winner-versus-competitor comparisons, permits ties among losers, and is sufficient rather than a characterization of every box with a common outcome; minimum-certificate discovery is not solved.Source: K A CERTIFICATE FOR THE PROPOSAL TRACE · p. 35

L CERTIFICATE-GUIDED REPAIR

  • CGR retains valid edge evidence, replays DA from the empty state, and doubles samples on the widest real possible winner until the trace is certified.It invalidates only notified edges, waits for each whole batch before updating, and executes modified old matchings during pulls and the old matching while waiting; this is statistical reuse, not a claimed sublinear-time dynamic matching algorithm.Source: L CERTIFICATE-GUIDED REPAIR · pp. 35–36

M.1 CONFIDENCE AND SELECTIVE SAMPLING

  • With probability at least 1 − δ, every CGR interval contains its current edge mean despite adaptive edge choice and reward-dependent bounded delays.The selective-sampling results bound lifetime pulls, batches, and waiting rounds, and give a sufficient repair duration before the next notification; the confidence argument uses complete batches rather than selectively early arrivals.Source: §M.1 · p. 36

M.2 REGRET AND STABILITY DURING REPAIR

  • On the confidence event, CGR bounds repair regret and stability violations using exploratory and waiting rounds, while statistical locality and allocation locality can differ substantially.The regret and violation bounds also incur failure-event expectation costs; waiting is charged to queried edges, not automatically to the slowest edge, though CGR is not delay-optimal.Source: §M.2 · p. 37

N SEPARATIONS AND LOWER BOUNDS

  • One requester’s utility change can shift all N DA partners, while identifying a pivotal edge requires at least log(1/δ)/(64η^2) expected pulls and incurs at least (1 − 2δ)(d_c + 1) expected reward rounds.These are identification lower bounds, not matching-regret bounds or proof that CGR’s batch waits are necessary; the repair guarantees require announced changes because stale intervals may exclude a new truth after unannounced changes.Source: N SEPARATIONS AND LOWER BOUNDS · pp. 37–38

O.2 THE WIDEST-CANDIDATE ARGUMENT; O.3 DOUBLING, LIFETIME REUSE, AND DWELL TIME

  • On the confidence event, the widest sampled candidate has a relevant comparison gap at most twice its interval width, and doubling limits lifetime batches while each batch adds at most d_e waiting rounds.Retained counts persist across epochs, so lifetime sample bounds use the maximum threshold rather than summing across epochs; without retained evidence, each epoch’s work is bounded by its sufficient duration.Source: §O.2 · p. 38, §O.3 · p. 39

O.3 DOUBLING, LIFETIME REUSE, AND DWELL TIME

  • Sound prior intervals may exclude an edge before new sampling, so an edge with large d_e can incur no waiting charge after an update.The passage also states a bound of at most 2n⋆e,h additional samples when samples are needed, but the supplied text is truncated around that expression.Source: §O.3 · p. 39

O.4 FULL STABILITY AND EXPECTATION ACCOUNTING

  • If q requesters differ from a stable matching, at most (K + 2N)q blocking pairs and q individual-rationality violations arise.Expectation guarantees charge the failure event G^c, where regret is bounded by 2NT and violations by N(K + 1)T; deterministic caps are used for Eq. (49).Source: §O.4 · p. 39

P.1 A CONNECTED REJECTION CASCADE

  • One requester’s preference swap changes every partner in a connected rejection cascade, yet retained intervals can certify all subsequent queries so only that requester needs fresh samples.The example’s two outcomes are requester-optimal DA matchings; unchanged-edge intervals of radius at most 0.05 certify the comparisons 0.8 > 0.3 and 0.3 > 0.Source: §P.1 · p. 40

P.2 TESTING A PIVOTAL PREFERENCE

  • Correctly identifying the pivotal preference requires transcript KL of at least 1/2 log(1/δ), while delayed pivotal feedback imposes at least (1 − 2δ)(d_c + 1) expected reward rounds before output.The pivotal KL is at most 32η²; with delay d_c, the feedback cannot be observed before d_c + 1 reward rounds, and the delay argument concerns correct identification rather than positive-part regret.Source: §P.2 · p. 40

P.3 A CERTIFICATE NEED NOT LEARN EVERY LOSING COMPARISON

  • At η = 0, the trace theorem still applies, but a procedure requiring strict certification of the order between losing arms 0.2 and 0.2 + η has no finite certificate.The true trace compares 0.8 with 0.2, 0.2 + η, and zero; this is not an impossibility result for algorithms that explicitly model indifference.Source: §P.3 · p. 40

Q BASELINE STABILITY REDUCTION AND ITS LIMITATION · R DEFERRED ACCEPTANCE AND IMPLEMENTATION DETAILS

Score-based deferred acceptance can bound deviation incentives and recover the true DA matching under a strict error-gap condition, but stability does not guarantee proximity to the requester-optimal outcome. The section also specifies a finite deferred-acceptance procedure and establishes its stability and requester-optimality properties.

Q BASELINE STABILITY REDUCTION AND ITS LIMITATION

  • The measure g captures deviation incentives—blocking-pair gains and requester individual-rationality shortfalls—not optimal stable regret.The score-DA example shows why those notions differ: its outcome can have g = 0 despite substantial requester regret.Source: Q BASELINE STABILITY REDUCTION AND ITS… · pp. 40–41
  • Each provider-willing pair’s positive deviation gain is at most e_i,j + e_i,cM(i), and each requester’s individual-rationality shortfall is at most e_i,cM(i).Here e_i,j bounds the score error for pair (i,j), and cM(i) is requester i’s assigned provider.Source: Q BASELINE STABILITY REDUCTION AND ITS… · p. 41
  • If the maximum feasible-pair score error e satisfies 2e < ∆t, score-DA returns the true DA matching because no alternatives, including the outside option, can reverse order.Identical strict preference lists lead deferred acceptance to the same matching.Source: Q BASELINE STABILITY REDUCTION AND ITS… · p. 41
  • For arbitrarily small uniform score error e, score-DA can incur requester regret of at least 4/5 in one round while producing an exactly stable matching (g = 0).This disproves a uniform Lipschitz regret bound for the DA map, but is not a minimax lower bound on every learning algorithm.Source: Q BASELINE STABILITY REDUCTION AND ITS… · p. 41

R DEFERRED ACCEPTANCE AND IMPLEMENTATION DETAILS

  • Deferred acceptance lets unmatched requesters propose to their highest remaining acceptable provider, which retains its favorite proposal or incumbent; each feasible pair is proposed at most once, requiring at most |E| messages.Rejected requesters delete that provider, and termination occurs when no unmatched requester has an acceptable untried provider.Source: R DEFERRED ACCEPTANCE AND… · p. 41
  • The procedure’s final matching has no score-blocking pair, and requesters receive score-individually-rational partners by proposing only above the outside option.The rejection argument shows that a pair rejected by a provider cannot block the final matching.Source: R DEFERRED ACCEPTANCE AND… · p. 41
  • No edge belonging to any stable matching is rejected, so each requester obtains its best achievable stable partner, including under the specified tie refinement.The proof uses the first rejection of an edge in a stable matching to derive a contradiction.Source: R DEFERRED ACCEPTANCE AND… · pp. 41–42

S NEW EXPERIMENT DETAILS AND COMPLETE SUMMARIES

This section documents the implementation and scope of the new experiments, including a sound Prefix-P stopping condition and separate Jester and optical-digit data benchmarks. It also reports reproducibility checks and defines the matching-configuration costs summarized in Table 8.

Reproducible implementation

  • The paired runner used four local CPU workers for 240 tasks, producing 1,110 method trajectories and 2,730 epoch runs; all 2,160 dynamic outputs were correct and complete.The common sufficient dwell bound was 1,593,800 rounds at ρ = .1, below the fixed 5,000,000-round epoch; that calculation is separate from observed finite-seed completion.Source: S NEW EXPERIMENT DETAILS AND COMPLETE… · p. 42

Implementation checks

  • Implementation checks covered dynamic regret, feasibility, interval completions, ties, signed outside options, parallel conflicts, and delayed truncation, but do not prove the theorems.Configurations and data/source hashes accompany raw outputs.Source: S NEW EXPERIMENT DETAILS AND COMPLETE… · p. 42

Prefix comparison

  • Prefix-P fixes every completion’s DA partner prefixes using disjoint intervals for alternatives scoring at least as high as the midpoint-DA partner.The outside option is [0, 0]; matched-width scheduling and a common horizon-dependent radius replace the source algorithm’s elimination schedule and radius, so Prefix-P is not presented as the best published PCOS or pervasive-matching algorithm.Source: S NEW EXPERIMENT DETAILS AND COMPLETE… · p. 42

Jester preprocessing

  • The Jester benchmark uses ten universal-query items, disjoint three-user seed groups, shuffled with seed 202709, and signed rewards with mean equal to the unchanged rating scaled by 1/10.Provider priorities are independently permuted per seed; this generator is distinct from the controlled affine suite and its results are not pooled with that suite.Source: S NEW EXPERIMENT DETAILS AND COMPLETE… · p. 42

Actual data-training jobs

  • The optical-digit benchmark trains binary logistic models on 1,797 observations, using three digit-pair tasks and four offers of 20–120 additional samples.Each buyer has a fixed balanced ten-observation anchor; 30 seeded bootstrap trials per buyer–offer pair train from zero weights for 150 full-batch steps. Utility is held-out accuracy gain, which may be negative; timing includes training and validation but excludes queueing, and is hardware/load dependent.Source: S NEW EXPERIMENT DETAILS AND COMPLETE… · pp. 42–43

Matching configurations

  • Table 8 covers all new matching configurations over 30 seeds; stationary learning-round costs are capped at 105, while dynamic costs sum four repairs.Total regret includes commitment and incomplete runs.Source: Table 8 · p. 43

Related papers

Loading 2610.12960v1…