Stochastic Network Utility Maximization in Strategic Queueing Systems: A Game-Theoretic Approach

Abstract

Stochastic Network Utility Maximization (NUM) has been a dominant framework for many queueing network resource allocation and control problems. Its original model seeks to optimize social welfare, which usually takes the form of the sum of local utilities of participating entities. However, such a centralized utility maximization approach is unsuitable for many modern multi-agent systems, in which each agent may selfishly optimize its local utility without regard to the overall utility. In this paper, we formulate the stochastic NUM problem in strategic queueing systems as a repeated game with queue stability constraints. In particular, the agents repeatedly make decisions to satisfy both their local constraints and global constraints, shared among them, while maintaining queue stability. The goal is to design a policy that constitutes a generalized Nash equilibrium (GNE) for the game.

We first derive the fluid model characterization of the strategic queueing NUM problem via a static one-shot game formulation. This characterization motivates a primal-dual algorithm that constitutes an approximate GNE by ensuring last-iterate convergence to a solution of the regularized static one-shot game. However, similar to primal-dual methods developed for the classical NUM problem, this approach does not leverage real-time queue lengths in decision making, leading to suboptimal queueing delay in practice, and has no explicit performance guarantees. To this end, we propose the Strategic Drift-plus-Penalty (SDP) algorithm and show that it constitutes an $\varepsilon$-GNE and has a uniformly bounded expected queue length of order $O\big(\frac{1}{\varepsilon^3} \big)$ for any $\varepsilon > 0$. Under an additional mild assumption that holds for a wide class of problems, we show that our algorithms achieve long-term average social welfare arbitrarily close to that of a welfare-maximizing GNE policy. Simulations validate our theory and demonstrate the favorable performance of our algorithms.