用超稳定理论提升双边匹配中的学习效率
Competing Bandits in Matching Markets via Super Stability
- 基于超稳定概念改进戈尔-沙普利算法，应对信息不全的匹配问题
- 中央化算法实现对数级最坏稳定遗憾，依赖实例相关的容许间隙参数
- 首次建立二元稳定遗憾的实例相关下界，揭示匹配复杂性本质
我们研究双边奖励不确定下的匹配市场中的带宽学习问题，扩展了以往主要关注单边不确定性的研究。借助Irving（1994）提出的‘超稳定’概念，我们证明了扩展戈尔-沙普利（Extended GS）算法在不完全信息下实现真正稳定匹配的优势。通过采用扩展GS算法，我们的集中式算法实现了依赖于实例相关容许间隙参数的对数级最坏稳定遗憾。该算法进一步被适配到去中心化场景，仅带来常数级别的遗憾增加。最后，我们建立了全新的集中式实例相关下界，阐明了容许间隙与超稳定匹配在带宽反馈下稳定匹配复杂性中的作用。
原文摘要 · Abstract (English)
We study bandit learning in matching markets with two-sided reward uncertainty, extending prior research primarily focused on single-sided uncertainty. Leveraging the concept of `super-stability' from Irving (1994), we demonstrate the advantage of the Extended Gale-Shapley (GS) algorithm over the standard GS algorithm in achieving true stable matchings under incomplete information. By employing the Extended GS algorithm, our centralized algorithm attains a logarithmic pessimal stable regret dependent on an instance-dependent admissible gap parameter. This algorithm is further adapted to a decentralized setting with a constant regret increase. Finally, we establish a novel centralized instance-dependent lower bound for binary stable regret, elucidating the roles of the admissible gap and super-stable matching in characterizing the complexity of stable matching with bandit feedback.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。