Deep Learning for Two-Sided Matching
This work addresses the problem of designing matching mechanisms for economists and market designers, offering a new target for economic theory and machine learning pipelines, though it appears incremental in applying deep learning to an existing domain.
The paper tackles the automated design of two-sided matching mechanisms by using deep learning to explore tradeoffs between strategy-proofness and stability, which cannot be achieved simultaneously. The result shows that learned mechanisms achieve a substantially better efficient frontier than convex combinations of baseline methods like deferred acceptance and top trading cycles.
We initiate the study of deep learning for the automated design of two-sided matching mechanisms. What is of most interest is to use machine learning to understand the possibility of new tradeoffs between strategy-proofness and stability. These properties cannot be achieved simultaneously, but the efficient frontier is not understood. We introduce novel differentiable surrogates for quantifying ordinal strategy-proofness and stability and use them to train differentiable matching mechanisms that map discrete preferences to valid randomized matchings. We demonstrate that the efficient frontier characterized by these learned mechanisms is substantially better than that achievable through a convex combination of baselines of deferred acceptance (stable and strategy-proof for only one side of the market), top trading cycles (strategy-proof for one side, but not stable), and randomized serial dictatorship (strategy-proof for both sides, but not stable). This gives a new target for economic theory and opens up new possibilities for machine learning pipelines in matching market design.