论文标题
战略排队系统中耐心的优点
Virtues of Patience in Strategic Queuing Systems
论文作者
论文摘要
我们考虑离散时间排队系统中自私的代理商的问题，竞争排队的队列试图提供他们的数据包。在此模型中，队列将每个步骤发送到其中一台服务器，该服务器将尝试使用最古老的到达数据包，并将未加工的数据包返回到每个队列。我们将其建模为一个重复的游戏，排队竞争服务器的容量，但是游戏状态随着每个队列的长度而变化，导致高度依赖的随机过程。作者[EC'20]的早期工作表明，对于无需重新学习的人，该系统需要两倍的容量，尽管排队的自私行为，但在协调设置中所需的能力是确保队列长度保持稳定的。在本文中，我们证明了这种评估结果的方式是近视的：如果更多的患者队列选择自私地最大化其长期成功率的策略，则只需$ \ \\ frac {e} {e-1} {e-1} \约1.58 $ 1.58 $ 1.58 $ 1.58 $ 1.58 $ 1.58 $ 1.58 $ 1.58 $ 1.58 $倍，超越了假设无re-regret属性的可能性。 随着这些系统诱导高度依赖的过程，我们的分析在很大程度上借鉴了概率理论的技术。尽管这些系统在任何固定的策略下都是随机的，但我们表明，令人惊讶的是，这些系统具有确定性和明确的渐近行为。我们表明，队列的渐近增长率可以写为子模块和模块化功能的比例，该功能提供了重要的游戏理论特性。然后，我们的均衡分析依靠一个新的变形论证来实现更可分析的解决方案，该解决方案与以前的无政府状态结果显着不同。虽然中间点不是平衡，但这种分析结构将确保这种变形沿该连续路径是单调的。
We consider the problem of selfish agents in discrete-time queuing systems, where competitive queues try to get their packets served. In this model, a queue gets to send a packet each step to one of the servers, which will attempt to serve the oldest arriving packet, and unprocessed packets are returned to each queue. We model this as a repeated game where queues compete for the capacity of the servers, but where the state of the game evolves as the length of each queue varies, resulting in a highly dependent random process. Earlier work by the authors [EC'20] shows that with no-regret learners, the system needs twice the capacity as would be required in the coordinated setting to ensure queue lengths remain stable despite the selfish behavior of the queues. In this paper, we demonstrate that this way of evaluating outcomes is myopic: if more patient queues choose strategies that selfishly maximize their long-run success rate, stability can be ensured with just $\frac{e}{e-1}\approx 1.58$ times extra capacity, better than what is possible assuming the no-regret property. As these systems induce highly dependent processes, our analysis draws heavily on techniques from probability theory. Though these systems are random under any fixed policies by the queues, we show that, surprisingly, these systems have deterministic and explicit asymptotic behavior. We show that the asymptotic growth rates of queues can be written as a ratio of a submodular and modular function, which provides significant game-theoretic properties. Our equilibrium analysis then relies on a novel deformation argument towards a more analyzable solution that differs significantly from previous price of anarchy results. While the intermediate points will not be equilibria, this analytic structure will ensure that this deformation is monotonic along this continuous path.
