匹配市场中玩家最优稳定遗憾的赌博学习
该研究考虑了单人和多人多臂老虎机模型的学习问题,提出了两种可分散策略,即E³ (立方)和E³-TS,它们显示出预期遗憾增长的上限为O(log^(1+ε)T),并解决了分散的在线学习所产生的附加成本问题。
May, 2015
本研究提出了一种统计学习模型,用于解决双边市场中的稳定匹配问题,其中一方需从随机奖励中学习另一方的偏好,该模型扩展了标准的多臂赌博机框架,并研究了集中式和分散式方法,发现与单人多臂赌博机设置相比,具有令人惊讶的探索-利用权衡。
Jun, 2019
研究马尔可夫匹配市场,提出强化学习框架,结合最大权匹配算法解决序列探索、匹配稳定性和函数逼近等问题,并证明算法可达到次线性的遗憾率。
Mar, 2022
在双边撮合市场中,我们研究了竞争环境下在线学习的问题,如一方的代理人必须通过重复互动了解对另一方的企业的偏好,并与其他代理人竞争成功匹配。我们提出了一类分散、不需要协调的算法,代理人可以使用该算法在结构化匹配市场中达到稳定匹配,其决策仅基于代理人自己的游戏历史,不需要预先了解企业的偏好。研究表明,在代理人和企业的底层偏好具有现实结构假设的情况下,所提出的算法在时间范围内具有最多对数增加的后悔成本。在匹配市场的情况下,我们的结果表明,竞争不会极大地影响分散、不需要通信和协调的在线学习算法的性能。
Jun, 2022
在这篇论文中,我们介绍了适应性的探索-延迟接受算法(AETDA)用于回应性设置,并得到了一个玩家最优稳定遗憾的 O(Nmin{N,K}ClogT/Δ²)上界,同时证明了它的激励兼容性保证。我们还考虑了更广泛的可替代偏好,在此设置中设计了一种在线DA(ODA)算法,并为其建立了一个 O(NKlogT/Δ²)的玩家最差稳定遗憾界限。
Jan, 2024
本研究针对双边匹配市场中的稳定性问题,提出了一种新的算法,通过利用稳定解的结构来提高找到稳定匹配的可能性。研究着重分析了达到高概率稳定匹配所需的样本复杂度,并通过实证结果揭示了所提算法在稳定性与最优性之间的有趣权衡,进而丰富了理论理解。
Oct, 2024
本文研究了带有平局的匹配市场问题,指出在这种情况下,市场一方对另一方成员的不严格偏好会导致无法找到唯一的稳定匹配。作者提出了一种通过随机不稳定匹配来实现对工人最佳稳定效用的近似,同时在有效性未知的情况下也提供了一种算法,能够在带有平局的参数环境中有效地选择匹配。这项研究的重要发现是,即使在存在平局的情况下,也能有效地最大化工人的效用分享。
Nov, 2024