随机网络效用最大化在战略排队系统中的应用：一种博弈论方法

《Proceedings of the ACM on Measurement and Analysis of Computing Systems》：Stochastic Network Utility Maximization in Strategic Queueing Systems: A Game-Theoretic Approach

本文提出基于策略性漂移加惩罚的算法（SDP），解决随机网络效用最大化（NUM）问题，在满足队列稳定性的同时实现近似广义纳什均衡，并保证期望队列长度为O(1/ε3)，显著优于传统 primal-dual 方法。

　　

摘要人工智能摘要

要查看此由人工智能生成的摘要，您必须具有高级访问权限。

了解更多登录

摘要

摘要

随机网络效用最大化（NUM）一直是许多排队网络资源分配和控制问题的主要框架。其原始模型旨在优化社会福利，这通常表现为参与实体的局部效用之和。然而，这种集中式的效用最大化方法不适用于许多现代的多智能体系统，在这些系统中，每个智能体可能会自私地优化其局部效用，而不考虑整体效用。在本文中，我们将随机NUM问题在战略排队系统中表述为一个具有排队稳定性约束的重复博弈。具体来说，智能体反复做出决策，以满足它们的局部约束和它们之间共享的全局约束，同时保持排队稳定性。目标是设计一种策略，该策略构成博弈的广义纳什均衡（GNE）。

我们首先通过静态一次性博弈的表述推导出战略排队NUM问题的流体模型特征。这种特征激发了一种原始-对偶算法，该算法通过确保最后一次迭代收敛到规范化静态一次性博弈的解来构成一个近似的GNE。然而，与为经典NUM问题开发的原始-对偶方法类似，这种方法在决策过程中没有利用实时队列长度，导致实际中的排队延迟不佳，并且没有明确的性能保证。为此，我们提出了战略漂移加惩罚（SDP）算法，并证明它构成一个ε-GNE，并且对于任何ε > 0，预期的队列长度都有统一的上界，即O(1/ε^3)。在另一个适用于广泛问题类别的温和假设下，我们证明我们的算法实现的长期平均社会福利任意接近于福利最大化GNE策略的社会福利。仿真验证了我们的理论，并展示了我们算法的良好性能。

人工智能摘要

人工智能生成的摘要（实验性）

此摘要是使用自动化工具生成的，并非由文章作者撰写或审阅的。它旨在帮助发现、帮助读者评估相关性，并协助来自相关研究领域的读者理解这项工作。它旨在补充作者提供的摘要，后者仍然是文章的主要摘要。完整文章仍然是权威版本。点击这里了解更多。

点击这里对摘要的准确性、清晰度和实用性进行评论。这样做将有助于改进和未来重新生成的版本。

要查看此由人工智能生成的通俗语言摘要，您必须具有高级访问权限。