  Today's wireless networks are increasingly crowded with an explosion of
wireless users, who have greater and more diverse quality of service (QoS)
demands than ever before. However, the amount of spectrum that can be used to
satisfy these demands remains finite. This leads to a great challenge for
wireless users to effectively share the spectrum to achieve their QoS
requirements. This paper presents a game theoretic model for spectrum sharing,
where users seek to satisfy their QoS demands in a distributed fashion. Our
spectrum sharing model is quite general, because we allow different wireless
channels to provide different QoS, depending upon their channel conditions and
how many users are trying to access them. Also, users can be highly
heterogeneous, with different QoS demands, depending upon their activities,
hardware capabilities, and technology choices. Under such a general setting, we
show that it is NP hard to find a spectrum allocation which satisfies the
maximum number of users' QoS requirements in a centralized fashion. We also
show that allowing users to self-organize through distributed channel
selections is a viable alternative to the centralized optimization, because
better response updating is guaranteed to reach a pure Nash equilibria in
polynomial time. By bounding the price of anarchy, we demonstrate that the
worst case pure Nash equilibrium can be close to optimal, when users and
channels are not very heterogenous. We also extend our model by considering the
frequency spatial reuse, and consider the user interactions as a game upon a
graph where players only contend with their neighbors. We prove that better
response updating is still guaranteed to reach a pure Nash equilibrium in this
more general spatial QoS satisfaction game.
