用有限面试实现匹配市场的稳定学习,降低长期错误决策。
Two-Sided Time-Independent Regret for Matching Markets with Limited Interviews
- 引入策略性延迟机制,允许企业临时空缺职位修正早期录用错误。
- 每轮仅需常数次面试即可实现与时间无关的后悔值,优于已知对数级保证。
- 适用于企业偏好不确定的场景,适合研究匹配市场或平台设计者。
双侧匹配平台依赖双方偏好,但参与者只能评估少量潜在伙伴。实践中,通过低成本预匹配筛选(如面试、浏览资料或试任务)形成有噪声的印象后再提交申请与邀约。本文研究带面试的匹配市场中的多臂赌博机学习问题,将这些互动建模为查询的‘提示’(hints),揭示部分偏好信息并限制后续申请。框架还允许企业侧不确定性:企业如个体一样学习自身偏好,可能犯早期录用错误。为此,我们提出战略延后(strategic deferral),一种企业端动作,允许临时空缺职位,纠正过早承诺,并在粗粒度匿名反馈下实现去中心化学习。我们设计了集中式和去中心式算法,证明每轮常数次面试即足以实现与时间无关的后悔率,优于无面试时已知的 $O(\ ext{log} T)$ 保证。上界近乎最优:集中式结果距离信息论下界仅差一个因子 $m$;去中心式算法在结构化市场中与之匹配,且在一般市场中仍保持时间无关性。
原文摘要 · Abstract (English)
Two-sided matching platforms rely on preferences from both sides, yet participants can evaluate only a small fraction of potential partners. In practice, they use low-cost pre-match screening, e.g., interviews, profile views, or trial tasks, to form noisy impressions before committing to applications and offers. We study bandit learning in matching markets with interviews, modeling these interactions as queried \emph{hints}~\citep{DBLP:conf/innovations/BhaskaraGIKM23} that reveal partial preference information to both sides while constraining subsequent applications. Our framework also allows firm-side uncertainty: firms, like agents, learn their preferences and may make early hiring mistakes. To address this, we introduce strategic deferral, a firm-side action that permits temporary vacancy, corrects premature commitments, and enables decentralized learning under coarse anonymous feedback. We design algorithms for centralized and decentralized markets and show that a constant number of interviews per round suffices for horizon-independent regret, improving over the $O(\log T)$ guarantees known without interviews. Our bounds are near-optimal: the centralized guarantee is within a factor $m$ of an information-theoretic lower bound, while decentralized algorithms match it up to polynomial factors in structured markets and remain horizon-independent in general markets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。