2021/07/07 by Sai Srivatsa Ravindranath, Zhe Feng, Ravindranath, Sai Srivatsa +9 · 1 citation
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Artificial Intelligence (cs.AI) #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Voting Systems #Machine Learning (cs.LG) #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.2107.03427
openalex publication_date 2021/07/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.