Distribution Games: A New Class of Games With Application to User Provided Networks

Abstract

User Provided Network (UPN) is a promising solution for sharing the limited network resources by utilizing user capabilities as a part of the communication infrastructure. In UPNs, it is an important problem to decide how to share the resources among multiple clients in decentralized manner. Motivated by this problem, we introduce a new class of games termed distribution games that can be used to distribute efficiently and fairly the bandwidth capacity among users. We show that every distribution game has at least one pure strategy Nash equilibrium (NE) and any best response dynamics always converges to such an equilibrium. We consider social welfare functions that are weighted sums of bandwidths allocated to clients. We present tight upper bounds for the price of anarchy and price of stability of these games provided that they satisfy some reasonable assumptions. We define two specific practical instances of distribution games that fit these assumptions. We conduct experiments on one of these instances and demonstrate that in most of the settings the social welfare obtained by the best response dynamics is very close to the optimum. Simulations show that this game also leads to a fair distribution of the bandwidth.

Keywords

• Congestion games
• distributed welfare games
• user provided networks