论文标题
随机匹配中的广义最大策略
Generalized max-weight policies in stochastic matching
论文作者
论文摘要
我们考虑了一个匹配系统，其中项目根据Poisson流程在每个节点的每个节点上一个一个一个，然后在将它们与兼容项目匹配后立即离开。所考虑的匹配政策是一项广义的最大重量政策，决策可能是嘈杂的。此外，某些节点可能具有不耐烦，即在匹配之前离开系统。使用最大重量策略的特定属性，我们构建了几个Lyapunov函数，包括一个简单的二次功能。这使我们能够建立稳定结果，以构建系统中客户总量的固定均值和差异的界限，并证明指数的收敛速度向固定度量。我们最终使用玩具示例中的模拟说明了其中一些结果。
We consider a matching system where items arrive one by one at each node of a compatibility network according to Poisson processes and depart from it as soon as they are matched to a compatible item. The matching policy considered is a generalized max-weight policy where decisions can be noisy. Additionally, some of the nodes may have impatience, i.e. leave the system before being matched. Using specific properties of the max-weight policy, we construct several Lyapunov functions, including a simple quadratic one. This allows us to establish stability results, to construct bounds for the stationary mean and variances of the total amount of customers in the system, and to prove exponential convergence speed towards the stationary measure. We finally illustrate some of these results using simulations on toy examples.
