Online Stochastic Matching: A Polytope Perspective
Céline Comte (TU/e, CNRS, LAAS-SARA), Fabien Mathieu (NPA), Sushil Mahavir Varma (ARGO), Ana Bušić (DI-ENS, LINCS, DYOGENE, ARGO)
随机动态匹配问题最近因其多样化的应用而引起随机建模社区的关注,例如供应链管理和肾脏交换计划。 在本文中,我们研究了一个匹配的问题,即不同类别的项目根据独立的Poisson过程到达。 不匹配的项目存储在队列中,项目之间的兼容性由一个简单的图形表示,如果它们的类是连接的,可以匹配项目。 我们在稳定性、延迟和长期匹配率优化方面分析匹配策略。 我们的方法依赖于保护方程,它确保了在任何稳定系统中到达和离开之间的平衡。 我们的主要贡献如下。 我们在稳定策略的存在、保护方程的求值集的维度和兼容性图的结构之间建立了联系。 我们描述了由保护方程的非负解形成的凸多顶,我们设计的策略可以实现或接近这个多顶点的顶点。 最后,我们讨论我们的结果超出本文主要假设的潜在扩展。
Stochastic dynamic matching problems have recently gained attention in the stochastic-modeling community due to their diverse applications, such as supply-chain management and kidney exchange programs. In this paper, we study a matching problem where items of different classes arrive according to independent Poisson processes. Unmatched items are stored in a queue, and compatibility between items is represented by a simple graph, where items can be matched if their classes are connected. We anal...