Existence and uniqueness of the Nash equilibrium in the non-cooperative QoS routing

Abstract

Researchers dealing with game theoretic issues are well aware that the definition of a model capturing some physical behaviours such as the routing, the pricing, the flow and congestion control, the admission control just to mention some examples in the telecommunication field, is a difficult task, but it is only half of the overall effort. As a matter of fact, a key aspect is the analysis of the equilibrium (or equilibria) towards which the game will (hopefully) converge. The existence, the uniqueness, the efficiency and the structure of the equilibrium are some of the typical properties which are investigated. In this article, we propose a game theoretic model for quality of service (QoS) routing in networks implementing a Differentiated Service model for the QoS support. In particular, we focus on a parallel link network model and we consider a non-cooperative joint problem of QoS routing and dynamic capacity allocation. For this model, we demonstrate that the Nash equilibrium exists, so overcoming a typical problem in the existence proofs appeared in many papers in the area of routing game since 1990s, and we explicitly obtain a suitable set of relations characterising its structure. Moreover, we prove that Nash equilibrium uniqueness cannot be guaranteed in general.

Keywords:

• quality of service routing
• capacity assignment
• game theory
• non-cooperative game
• Nash equilibrium
• existence
• uniqueness

Notes

Notes

1. All the vectors have to be considered as column vectors. As far as the notation adopted is concerned, normal letters denote vectors, while italic letters denote scalars.

2. It can be noted that the set of capacity players coincides with the set of parallel links. The reason is that each capacity player is associated with (and controls) a given link. In what follows, the notations and will be used interchangeably. will be preferred when considering the player controlling the link while will be used to indicate just the communication link.

3. Each individual user i has to solve an optimisation problem with a convex function to be minimised, linear inequality constraint functions with and linear equality constraint functions with . Under these hypotheses, the KKT conditions are necessary and sufficient for to be a global optimal solution.

4. Since the capacity players solve their minimisation problem over the same (coupled) constraint set considered by the individual users, the consideration about the KKT conditions presented in endnote 3 holds even in this case. So, the KKT conditions are necessary and sufficient for c*l to be a global optimal solution of the minimisation problem to be solved by the capacity player.