Congestion Games With Player-Specific Utility Functions and Its Application to NFV Networks

Abstract

In this paper, a variation of the congestion situation is considered and a new game, the congestion game with player-specific (CGPS) utility functions, is proposed. This paper is motivated by some application scenarios that rule out the possibility of employing the existing game model to study such congestion situations. The CGPS game is characterized by adding a player-specific term and a weighted parameter with respect to the utility function. By using the semitensor product of matrices, the algebraic representation of the CGPS game is given and the existence of the weighted potential function is proved. Finally, the results are applied to solve the service chain composition problem in network function virtualization (NFV) and to analyze the effect of player-specific function on service chain configuration in NFV. Note to Practitioners-This paper is motivated by resource allocation problems in congestion networks where strategic users behave selfishly and aim at optimizing their own individual utility in the absence of a central controller. Compared with the centralized algorithms of poor reliability and scalability, game-theoretic control provides a promising distributed approach for resource allocation. In the game-theoretic framework, the existence and seeking of the desired solution are important issues. In this paper, a novel model is established to extend the utility functions space guaranteeing the existence of the solution. The developed utility design is used to capture users' different sensitivities to the effects of the network system. Simultaneously, it is more meaningful from the view of engineering to design the utility functions so that the desirable behavior is reachable. We also give an explicit scheme to seek the desired solution. The proposed model is finally applied to the service chain composition problem in NFV, of which the aim is to find the best service chain of users that accommodates their individual requirements. The proposed model shows reliable and effective.