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

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.

We study a sequential learning problem for stable matchings in two-sided markets where preferences on both sides are initially unknown. We focus on a centralized setting where an algorithm matches agents at each time step and receives noisy rewards that reflect the preferences of the matched agents, following a semi-bandit feedback structure. We adopt a pure exploration perspective, aiming to efficiently identify the optimal stable matching with high probability. Our work extends prior results by handling two-sided uncertainty and by exploiting partial preference information. A central ingredient is the notion of pervasive stable matching, which enables the identification of optimal stable matchings under partial preferences. We propose elimination-based algorithms whose stopping criteria exploit the structure of the learned partial preferences, and provide a refined sample-complexity analysis. Beyond pure exploration, we extend our approach to regret minimization and establish regret bounds with respect to the optimal stable matching that avoid dependence on the minimum reward gap $Δ_{\min}$.

Two-sided matching systems, such as admissions pipelines, allocate opportunities jointly. Reducing a protected at tribute's influence usually requires encoder retraining. We study a closed-form linear projector that does this at inference time. For markets that stay vertically ordered before and after the edit, we bound the mean welfare change by the edit-induced appeal shift and an explicit remainder. A probabilistic refinement replaces worst-case constants with a data-dependent deviation term. A pre-deployment screen combines a verticality test with a welfare sweep and returns PASS, KILL, or OUT-OF-SCOPE. An exact tier requires every opportunity to rank applicants by appeal, and a graded tier admits near-vertical markets. On 30 held-out synthetic markets, the screen agrees with every pre-specified regime verdict, with no observed false PASS. On 60 exactly vertical markets, no bound is violated, and the probabilistic bound is informative in 69% to 87% of configurations. On 2700 configurations from three realistic markets, which do not reach the exact tier, no plug-in bound expression is violated. A closed-form factorization stays within graded scope in 90% to 100% of instances, whereas two-tower and graph neural network encoders fall outside it in every instance. Architecture choice thus appears to affect whether a post-hoc edit is admissible.