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
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
(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.