用学习方法找稳定匹配，兼顾效率与公平性。
Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning
- 基于稳定匹配结构设计学习算法，提升找到稳定解的概率。
- 理论证明达到稳定匹配所需样本数的上界，可量化学习成本。
- 实验证明稳定性与最优性存在权衡，适合关注公平性的场景。
双边匹配市场描述了众多问题，其中一方参与者需根据偏好匹配到另一方。在内容匹配或在线劳动力市场等真实场景中，偏好信息可能未知，需通过学习获取——即一方（代理）可能不了解其对另一方（臂）的偏好。近期在线研究主要聚焦于福利优化（如最小化总体遗憾），而忽视了博弈论性质，如最终匹配的稳定性。本文利用稳定解的结构设计算法，提升发现稳定解的可能性。首次研究了寻找稳定匹配的样本复杂度，并提供了以高概率达到稳定匹配所需样本数的理论边界。实验结果揭示所提算法在稳定性与最优性之间存在有趣的权衡，进一步验证了理论发现。
原文摘要 · Abstract (English)
Two-sided matching markets describe a large class of problems wherein participants from one side of the market must be matched to those from the other side according to their preferences. In many real-world applications (e.g. content matching or online labor markets), the knowledge about preferences may not be readily available and must be learned, i.e., one side of the market (aka agents) may not know their preferences over the other side (aka arms). Recent research on online settings has focused primarily on welfare optimization aspects (i.e. minimizing the overall regret) while paying little attention to the game-theoretic properties such as the stability of the final matching. In this paper, we exploit the structure of stable solutions to devise algorithms that improve the likelihood of finding stable solutions. We initiate the study of the sample complexity of finding a stable matching, and provide theoretical bounds on the number of samples needed to reach a stable matching with high probability. Finally, our empirical results demonstrate intriguing tradeoffs between stability and optimality of the proposed algorithms, further complementing our theoretical findings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。