在不确定偏好下，快速找到左侧最优稳定匹配的高效学习方法。
Probably Correct Optimal Stable Matching for Two-Sided Markets Under Uncertainty
- 基于带噪声反馈的在线平台，通过多臂赌博机算法探索偏好。
- 提出几种概率正确算法，在有限样本内识别左侧最优稳定匹配。
- 适合研究市场匹配机制或需高效决策的平台设计者。
我们研究了在左侧市场偏好未知情况下的稳定婚姻模型学习问题。在集中式场景中，每个时间步，一个在线平台对参与者进行匹配，并获得反映其偏好的噪声评估。目标是快速识别出左侧最优的稳定匹配，这构成一个带有赌博机反馈的纯探索问题。我们特别关注寻找概率正确的最优稳定匹配，并提出了若干赌博机算法来实现。研究结果为如何在不确定性下高效收集和利用偏好信息以识别最优稳定匹配提供了基础理解。对合成数据的实验分析补充了所提方法在样本复杂度上的理论结果。
原文摘要 · Abstract (English)
We consider a learning problem for the stable marriage model under unknown preferences for the left side of the market. We focus on the centralized case, where at each time step, an online platform matches the agents, and obtains a noisy evaluation reflecting their preferences. Our aim is to quickly identify the stable matching that is left-side optimal, rendering this a pure exploration problem with bandit feedback. We specifically aim to find Probably Correct Optimal Stable Matchings and present several bandit algorithms to do so. Our findings provide a foundational understanding of how to efficiently gather and utilize preference information to identify the optimal stable matching in two-sided markets under uncertainty. An experimental analysis on synthetic data complements theoretical results on sample complexities for the proposed methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。