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

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

cs.LGOct 9, 2026

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

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

Organizations: University of Hong Kong · National University of Singapore · Guangming Laboratory · University of Science and Technology of China

Abstract

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 δ {\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.

Figures & tables

Figure 1: Unknown-gap Priority-Search on the fixed priority-star class. The horizontal axis is

\ell=\log(1/\delta)

on a logarithmic scale; the ordinate is mean new certification rounds divided by

\ell

. Dashed lines show the asymptotic information-load constant

L_{\star}(p,c)

, not a finite-confidence lower bound. Blue open circles with dashed lines use

d=0

; orange squares with solid lines use the audited

d=\lfloor\sqrt{\ell}\rfloor

regime. Error bars are percentile 95% intervals from 10,000 bootstrap resamples of the 100 per-configuration seeds. The curves are numerically distinct but close at the displayed scale; paired differences are audited in Appendix C .

$N$	Budget	RLR-P	Width-P	PCOS-A4	RLR	Width
3	30k	18/30; 18095	16/30; 20005	13/30; 24107	17/30; 19374	13/30; 20935
3	100k	23/30; 38130	22/30; 41841	20/30; 55573	23/30; 42815	22/30; 44280
5	30k	6/30; 27152	4/30; 28585	1/30; 29917	4/30; 27877	3/30; 28705
5	100k	7/30; 82101	7/30; 86256	2/30; 95918	7/30; 84005	7/30; 87581
8	30k	0/30; 30000	0/30; 30000	0/30; 30000	0/30; 30000	0/30; 30000
8	100k	0/30; 100000	0/30; 100000	0/30; 100000	0/30; 100000	0/30; 100000

Table 1: E5 same-instance finite-budget comparison. Each cell gives correct certificates/30 and mean capped rounds. All cells retain censored paths; PCOS-A4 is native and PSM-P is separate.

Certification and readiness time (rounds)
Method	Init cert	Init ready	Update cert	Update ready	Total cert	Total ready
RLR	115238	115238	112978	112978	228216	228216
RLR-P	90799	90803	105471	105475	196271	196278
Width	99305	99305	114025	114025	213330	213330
Width-P	92760	92764	109909	109912	202669	202676

Table 2: Quality-shift replay under a fixed two-epoch budget (30 paired trajectories). “Init” is epoch 0, “update” starts at notification, and “total” is the per-trajectory sum before averaging. Censored paths remain; CPU is cumulative oracle decision time in seconds.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Delayed edges	Hybrid	Published PSM oracle
None	-787 [-1,412, -178]	-1,108 [-1,742, -494]
Changed	-559 [-1,156, 24]	-880 [-1,495, -284]
Unchanged	-1,897 [-2,509, -1,293]	-2,226 [-2,853, -1,612]

Appendix

Table 3: Four-epoch cyclic repairs. Paired total-regret difference (retain minus reset), with descriptive 95% bootstrap intervals over 30 seeds. All Hybrid and PSM repairs complete.

Protocol	Method	Immediate		Measured delay
		Cert.	$\mathcal{R}_{T}$	Cert.	$\mathcal{R}_{T}$
Binary	Forced	0/30	25,321 $\pm$ 3,432	0/30	25,430 $\pm$ 3,464
Binary	Hybrid	0/30	25,321 $\pm$ 3,432	0/30	25,430 $\pm$ 3,464
Binary	Prefix	0/30	25,321 $\pm$ 3,432	0/30	25,430 $\pm$ 3,464
Ten-class	Forced	0/30	26,680 $\pm$ 1,780	0/30	26,704 $\pm$ 1,782
Ten-class	Hybrid	2/30	26,537 $\pm$ 1,807	2/30	26,564 $\pm$ 1,809

Appendix

Table 4: Empirical training-feedback replay: certified trials out of 30 and mean total regret

\pm

SE across ten split-level averages (three reward seeds each). The two task protocols use different utility scales; regret magnitudes should not be compared across protocols.

Delay	Oracle	Retain complete	Reset complete	Regret difference [95% CI]
Immediate	Forced	23/30	23/30	-8,990 [-13,944, -3,988]
Immediate	Hybrid	23/30	23/30	-7,605 [-12,845, -2,670]
Measured	Forced	23/30	23/30	-8,989 [-13,944, -3,981]
Measured	Hybrid	23/30	23/30	-7,604 [-12,845, -2,665]

Appendix

Table 5: Empirical provider revision with EB intervals, two epochs of

300{,}000

rounds. Each difference is retain minus reset, averaged within each of ten splits before constructing a paired 95% bootstrap interval. Both-epoch completion counts include every run and failure.

Figure 2: Left: the cyclic family, with unsuccessful runs capped at

10^{5}

rounds. Right: paired total-regret differences across four epochs; bars are descriptive 95% bootstrap intervals over 30 seeds. Negative values favor retention. The published PSM oracle benefits from the same reuse protocol.

Size	Method	Certified	Capped rounds	$\mathcal{R}_{T}$
$3\times 3$	Forced-P	19/30	19,607 $\pm$ 1,881	16,423 $\pm$ 1,902
	Hybrid-P	20/30	18,838 $\pm$ 1,893	15,918 $\pm$ 1,936
	PSM-P	21/30	18,590 $\pm$ 1,764	15,658 $\pm$ 1,773
	PCOS-A4	17/30	19,585 $\pm$ 1,926	19,031 $\pm$ 2,348
	C-UCB	–	–	585 $\pm$ 141
	C-ETC	–	–	801 $\pm$ 256

Appendix

Table 6: Native stationary comparison,

T=30{,}000

. Mean

\pm

SE over 30 independent markets per size; failed identification is capped at

T

. C-UCB/C-ETC do not certify. PSM-P is an oracle ablation; PCOS-A4 is a full sampling baseline.

Delay	Oracle	Retain complete	Reset complete	Regret difference [95% CI]
Immediate	Forced	20/30	20/30	-6,190 [-9,061, -3,538]
Immediate	Hybrid	20/30	20/30	-6,283 [-9,386, -3,462]
Measured	Forced	20/30	20/30	-6,188 [-9,055, -3,541]
Measured	Hybrid	20/30	20/30	-6,275 [-9,374, -3,463]

Appendix

Table 7: Controlled label-quality revision with EB intervals, two epochs of

300{,}000

rounds. Each difference is retain minus reset, averaged within each of ten splits before constructing a paired 95% bootstrap interval. Both-epoch completion counts include every run and failure.

Family	Setting	Method	Rounds	Regret	Complete
irrelevant	0	trace-P	100000	52429	0/30
irrelevant	0	outcome-P	230	102	30/30
irrelevant	0	outcome-S	644	660	30/30
irrelevant	0	prefix-P	100000	52429	0/30
irrelevant	0.001	trace-P	100000	52429	0/30
irrelevant	0.001	outcome-P	230	102	30/30

Appendix

Table 8: All new matching configurations, 30 seeds each. Costs are mean learning rounds, capped at

10^{5}

in stationary cases; dynamic costs sum four repairs. Total regret includes commitment and incomplete runs.

Online Resource Allocation

Online resource allocation studies how to assign scarce capacity to arriving requests under uncertainty while balancing reward, cost, fairness, and feasibility.

See all 95 papers

Learn to Match: Two-Sided Matching with Temporally Extended Feedback
Jun 4, 2026Haijing Zong, Yancheng Liang, Boyang Zhou +1Multi-Agent Reinforcement Learning
Department of Economics, University of Washington, Seattle, United States · Paul G. Allen School of Computer Science & Engineering, University of Washington, Seattle, United States
Probably Correct Optimal Stable Matching under Two-Sided Uncertainty
Jul 6, 2026Andreas Athanasopoulos, Anne-Marie George, Christos DimitrakakisMulti-Armed Bandits Preference Learning
University of Neuchâtel, Neuchâtel, Switzerland · University of Oslo, Oslo, Norway
When Is a Cheap Fairness Edit Safe? Screening Post-Hoc Edits in Two-Sided Matching Markets
Oct 27, 2026Moirangthem Tiken Singha, Rabinder Kumar PrasadaFair Resource Allocation Debiased ML
Department of Computer Science and Engineering, Dibrugarh University Institute of Engineering and Technology, Dibrugarh University, Dibrugarh, Assam, India

Jun 4, 2026J/K move · Enter open · S save

Learn to Match: Two-Sided Matching with Temporally Extended Feedback

Haijing Zong, Yancheng Liang, Boyang Zhou, Natasha Jaques

Department of Economics, University of Washington, Seattle, United States · Paul G. Allen School of Computer Science & Engineering, University of Washington, Seattle, United States

Multi-Agent Reinforcement Learning

Open paper AskPDF arXiv

Two-sided matching markets often involve information that unfolds over time through interviews, repeated interaction, learning, and separation. Existing matching models typically reduce this process to immediate sub-Gaussian feedback about fixed preferences, missing settings where payoff-relevant information is revealed gradually and changes future matching decisions. We introduce a framework with temporally extended feedback, that formulates two-sided matching as a partially observable Markov game with costly pre-match screening, noisy post-match observations, evolving latent profiles, and endogenous continuation or dissolution. We instantiate this framework in Learn2Match, a multi-agent reinforcement-learning benchmark for dynamic matching markets. Learn2Match supports decentralized decision making over whom to interview, whom to match with, and when to dissolve a match, while evaluating policies using regret, social welfare, and an information-friction loss that measures the welfare gap caused by incomplete revelation of latent preferences. We find that independent PPO achieves higher cumulative social welfare and lower cumulative regret than the bandit-style CA-ETC baseline under temporally extended feedback, demonstrating the promise of MARL for dynamic matching markets. However, PPO still incurs higher information-friction loss, revealing that end-to-end MARL does not yet provide the coordinated exploration structure of matching-bandit methods. These results position Learn2Match as a benchmark for developing the next generation of matching-market algorithms: methods that are adaptive like RL agents, statistically disciplined like bandit algorithms, and structurally aware like stable-matching mechanisms. Please refer to https://sites.google.com/view/learn-to-match/home for the official website and the code link.

Abstract

Online Resource Allocation

Explore similar work

Learn to Match: Two-Sided Matching with Temporally Extended Feedback

Probably Correct Optimal Stable Matching under Two-Sided Uncertainty

When Is a Cheap Fairness Edit Safe? Screening Post-Hoc Edits in Two-Sided Matching Markets