Learn to Match: Two-Sided Matching with Temporally Extended Feedback
For researchers in matching markets and multi-agent RL, this work provides a new benchmark and reveals limitations of current MARL methods in handling temporally extended feedback, motivating future algorithm development.
This paper introduces a framework for two-sided matching with temporally extended feedback, formalized as a partially observable Markov game, and presents Learn2Match, a multi-agent RL benchmark. Experiments show that independent PPO achieves higher social welfare and lower regret than a bandit baseline, but incurs higher information-friction loss, highlighting the need for algorithms combining RL adaptivity, bandit discipline, and structural awareness.
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.