A note on the convergence of asynchronous greedy algorithm with relaxation in a multiclass queueing environment

In this letter, we consider the convergence of an asynchronous greedy algorithm with relaxation for Nash equilibrium in a noncooperative multiclass queueing environment. The process of an asynchronous greedy algorithm is equivalent to the iteration of the Jacobi method in solving a linear system. However, it has been proved that the algorithm converges only for some particular range of queueing parameters. Here we propose the asynchronous greedy algorithm with relaxation, which is in principle equivalent to solving a linear system by the Jacobi method with relaxation. We propose also some relaxation parameters such that our algorithm converges very fast.