文件名称：限时动态随机匹配-研究论文
文件大小：8.55MB
文件格式：PDF
更新时间：2024-06-29 08:42:36
Dynamic Matching Approximation
在中心化的匹配市场中，例如肾脏交换计划和拼车平台，新参与者不断进入市场，并在有限的时间内保持潜在匹配。 为了实现有效的分配，匹配决策的“时机”是平台运营的一个关键方面。在增加市场厚度和降低参与者放弃市场的风险之间存在根本性的权衡。然而，匹配的动态特性市场在经典算法文献中大多被忽视。在本文中，我们介绍了边加权图上的通用动态匹配模型，其中代理的到达和放弃是随机和异构的。虽然由此产生的马尔可夫决策过程在计算上难以处理，我们设计了新的简单匹配算法，允许强大的最坏情况性能保证。我们为满足类度量属性的图上的成本最小化问题设计了 3-近似算法。相比之下，我们展示了广泛使用的批处理算法的性能可以是任意糟糕的。我们进一步设计了一个 (e-1)/(2e)-近似算法任意二部图上的 d 最大化问题。 我们的方法涉及开发一系列技术，包括线性规划基准、价值函数近似和连续时间马尔可夫链的代理，这些技术可能会引起更广泛的兴趣。 在广泛的实验中，我们使用真实世界的出租车需求数据模拟拼车平台的匹配操作。 与广泛使用的批处理算法相比，新开发的算法有可能显着提高成本效率。