arXiv:2502.08898v1 类型: cross 摘要：网络中的路由器使用简单的学习算法来找到将数据包传递到目标的最佳路径。这种简单、短视且分布式决策系统使得大型排队系统易于操作，但同时系统需要比所有流量集中协调所需的空间更多的容量。最近，Gaitonde 和 Tardos（EC 2020 和 JACM 2023）开始研究这类系统，将它们建模为一个无限重复的游戏，在这个游戏中，路由器竞争服务器，并且系统维护一种状态（每个队列持有数据包的数量），该状态源自之前轮次的结果。队列在每一步向其中一个服务器发送一个数据包，服务器尝试处理其中一个到达的数据包，模拟路由器。然而，他们的模型假设服务器完全没有任何缓冲区，所以队列必须重传所有未成功处理的数据包。他们表明，即使相对于集中协调所需的空间，服务器容量大幅增加，确保系统稳定也需要使用时间戳和优先级来处理较老的数据包。我们考虑了一个系统的两个重要变化，使得模型更加现实：首先，我们为每个服务器添加了一个非常小的缓冲区，允许它保留一个数据包以供以后处理（即使未能处理它）；其次，我们不要求时间戳或较老数据包的优先级。我们的主要结果是，当队列在学习时，与集中协调所需的空间相比，只需小小的常数因子增加的服务器容量就足以保持系统的稳定，即便服务器在同时到达的数据包中随机选择。这项工作为越来越受到关注的带有跨轮次影响系统的自私学习影响的研究做出了贡献：当前轮次的结果会影响未来游戏的结果。