Stability, Optimality and Complexity of Network Games with Pricing and Player Dropouts

Abstract

We study basic properties of a class of noncooperative games whose players are selfish, distributed users of a network and the game's broad objective is to optimize Quality of Service (QoS) provision. This class of games was previously introduced by the authors and is a generalization of well-studied network congestion games.

The overall goal is to determine a minimal set of static game rules based on pricing that result in stable and near optimal QoS provision.

We show the following. (i) Standard techniques for exhibiting stability or existence of Nash equilibria fail for these games—specifically, neither are the utility functions convex, nor does a generalized potential function exist. (ii) The problem of finding whether a specific game instance in this class has a Nash equilibrium is NP-complete.

To offset the apparent instability of these games, we show positive results. (iii) For natural subclasses of these games, although generalized potential functions do not exist, approximate Nash equilibria do exist and are easy to compute. (iv) These games perform well in terms of price of stability and price of anarchy. I.e., all of these approximate Nash equilibria nearly optimize a communal (or social) welfare function, and there is atleast one Nash equilibrium that is optimal.

Finally, we give computer experiments illustrating the basic dynamics of these games which indicate that price thresholds could speed up convergence to Nash equilibria.