标题： 通过状态无关策略实现动态匹配的常数遗憾 显示英文标题

标题： Achieving constant regret for dynamic matching via state-independent policies

摘要： 我们研究一个具有有限代理类型集中式离散时间动态双向匹配模型。代理随机地随时间到达，并加入其类型专用队列等待匹配。我们关注状态无关的贪心策略，这些策略通过仅根据跨类型的代理可用性做出匹配决策，而不是需要完整的队列长度信息，在所有时间点都能实现常数遗憾。这种策略在生命拯救应用如肾脏交换中特别有吸引力，因为与状态相关策略相比，它们需要更少的信息并提供更多的透明度。首先，对于无环匹配网络，我们分析了Kerimov等人[2023]提出的一种确定性优先级策略，该策略在匹配上遵循静态优先级顺序。我们推导了第一个关于一般位置差距（GPG）参数$\epsilon$的显式遗憾界限，该参数衡量流体松弛远离退化性的距离。其次，对于一般的双向匹配网络，我们设计了一种随机的状态无关贪心策略，该策略以最优尺度$O(\epsilon^{-1})$实现常数遗憾，与Kerimov等人[2024]建立的现有下限相匹配。 显示英文摘要

摘要： We study a centralized discrete-time dynamic two-way matching model with finitely many agent types. Agents arrive stochastically over time and join their type-dedicated queues waiting to be matched. We focus on state-independent greedy policies that achieve constant regret at all times by making matching decisions based solely on agent availability across types, rather than requiring complete queue-length information. Such policies are particularly appealing for life-saving applications such as kidney exchange, as they require less information and provide more transparency compared to state-dependent policies. First, for acyclic matching networks, we analyze a deterministic priority policy proposed by Kerimov et al. [2023] that follows a static priority order over matches. We derive the first explicit regret bound in terms of the general position gap (GPG) parameter $\epsilon$, which measures the distance of the fluid relaxation from degeneracy. Second, for general two-way matching networks, we design a randomized state-independent greedy policy that achieves constant regret with optimal scaling $O(\epsilon^{-1})$, matching the existing lower bound established by Kerimov et al. [2024].