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.