Game Theory and the Flat-Fading Gaussian

Interference Channel

Dick Maryopi

Seminar Advanced Topics in Wireless Communications

Heinrich-Hertz-Chair for Information Theory and Theoretical Information
Technical University of Berlin

5 January 2010
Outline

1 Motivation
2 Basic Game Theory
Noncooperative Game
Cooperative Game
3 Noncooperative Game on the Gaussian Interference Channel
SISO Game
MISO Game
MIMO Game
4 Summary

5 January 2010 2/29

Motivation

The fundamental resources in wireless communication e.g

bandwidth and power are limited.
Licensed spectrum has become expensive( i.e. 3G auction),
unlicensed spectrum has become overcrowded and at many
location so cluttered with interference ( i.e. WLAN).
In the situation, where the usage of the same spectrum is
allowed, there exist inherently a natural resource conict.
Game theory is an useful tool for analyzing this resource
conict.
E. Larsson, E. Jorswieck, J. Lindblom and R. Mochaourab, ƒGame
Theory and the Flat-Fading Gaussian Interference Channel,¨Signal
Processing Magazine, IEEE, vol. 26, no. 5, pp. 18-27, September 2009.

5 January 2010 3/29

Motivation

The fundamental resources in wireless communication e.g

bandwidth and power are limited.
Licensed spectrum has become expensive( i.e. 3G auction),
unlicensed spectrum has become overcrowded and at many
location so cluttered with interference ( i.e. WLAN).
In the situation, where the usage of the same spectrum is
allowed, there exist inherently a natural resource conict.
Game theory is an useful tool for analyzing this resource
conict.
E. Larsson, E. Jorswieck, J. Lindblom and R. Mochaourab, ƒGame
Theory and the Flat-Fading Gaussian Interference Channel,¨Signal
Processing Magazine, IEEE, vol. 26, no. 5, pp. 18-27, September 2009.

5 January 2010 3/29

Basic Game Theory

What is Game Theory? Game theory is a branch of mathematics

and provides a toolset for analyzing resource conicts, or more
generally, optimization problems with multiple conicting objective
functions.
A game has three components:
Players: Parties are involved in the resource conicts
(transceiver-receiver pairs).
Strategies: Actions or moves that can be taken by the players
belong to strategy space. (spectral bands, powers).
Utilities: Measurements of how much something is worth to
some players (rates at receiver).

5 January 2010 4/29

Basic Game Theory

What is Game Theory? Game theory is a branch of mathematics

and provides a toolset for analyzing resource conicts, or more
generally, optimization problems with multiple conicting objective
functions.
A game has three components:
Players: Parties are involved in the resource conicts
(transceiver-receiver pairs).
Strategies: Actions or moves that can be taken by the players
belong to strategy space. (spectral bands, powers).
Utilities: Measurements of how much something is worth to
some players (rates at receiver).

5 January 2010 4/29

Basic Game Theory

What is Game Theory? Game theory is a branch of mathematics

and provides a toolset for analyzing resource conicts, or more
generally, optimization problems with multiple conicting objective
functions.
A game has three components:
Players: Parties are involved in the resource conicts
(transceiver-receiver pairs).
Strategies: Actions or moves that can be taken by the players
belong to strategy space. (spectral bands, powers).
Utilities: Measurements of how much something is worth to
some players (rates at receiver).

5 January 2010 4/29

Basic Game Theory

A game G can be dened as follow:

Denition
G = (K, S K , U), where:
K = {1, ..., K } is a non empty set of player.
S K = " Sk is a strategy space, consist of all possible
k ∈K
strategies for all player in K, where Sk is the set of strategies
available for player k ∈ K.
U = {u1 , ..., uK } is a set of utility functions. uk : S K
<,
∀k ∈ K,

There is a conict, whenever some player choose strategy that

increasing their utility, but decreasing the other's.

5 January 2010 5/29

Basic Game Theory

The set of all possible outcomes in the game is called utility region.
The outcome or operating point is called pareto optimal if and only
if no other outcome would make all players better o.
Pareto boundary is the boundary that consist of pareto optimal
operating points.

5 January 2010 6/29

Noncooperative Game

Players strictly compete and can not strike deals, the goal of
each player is to maximize his utility function.
The only reasonable operating point in this game is the Nash
Equilibrium.
Denition
For game G = (K, S K , U) and for all sk∗ ∈ Sk , the strategy vector
s∗ = (s1∗ , ..., sk∗ , ..., sK∗ ), where s∗ in space S K , is said to be Nash
Equilibrium(NE) if:
uk (s1 , ..., s , ..., s ) ≥ uk (s1 , ..., sk , ..., s ) for every k ∈ K.
∗ ∗ ∗ ∗ ∗
k K K
or we can dene:
s∗ = (s1∗ , ..., sk∗ , ..., sK∗ ) = argmax uk (s1∗ , ..., sk , ..., sK∗ ) for every
sk ∈Sk
k ∈ K.

5 January 2010 7/29

Cooperative Game

In this game players can negotiate with another and form joint
strategies.
Although interested in maximizing the own outcome, the
players probably want to accept a bargaining solution that is
found to be good enough for all players.
This bargaining solution is modeled by Nash bargaining theory.
Theorem
Let R be the utility region and suppose R compact and convex.

∗
Let r1 , r2∗ be a so called threat point, the point if there is no

agreement on any bargaining outcome.

Let f : (R, r ∗ , q ∗ ) Z⇒ (r̄ , q̄ ) be a function that maps the set of

possible utility region and the possible threat points into bargaining

solution (r̄ q̄ , )

5 January 2010 8/29

Cooperative Game

continued
Theorem
under the following axioms:

1 , ) ≥ (r ∗ , q ∗ )
Feasibility: (r̄ q̄

2 Pareto optimal: (r , q ) ∈ R and , ) ≥ (r ∗ , q ∗ ) ⇒ (r , q ) = (r̄ , q̄ )

(r̄ q̄

3 Independence of irrelevant alternatives: if (r̄ q̄ , )∈τ ⊂R and

(r̄ q̄ =f
, ) (R, r ∗ , q ∗ ), then (r̄ q̄ =f
, ) (τ, r ∗ , q ∗ )
∗
4 Symmetrie: if R symmetric arround r =q then r = q ∗ ⇒ r̄ = q̄
5 , , , ∈ real number,
Invariance to linear transformation: Let a1 a2 b1 b2

a1 > 0, a2 > 0, if (a1 r ∗ + b1 , a2 q ∗ + b2 ) ∈ R then

∗ ∗ ∗ ∗
f (R, a1 r + b1 , a2 q + b2 ) = [a1 , a2 ]f (R, r , q ) + [b1 , b2 ].

then f exist and unique, given by:

f (R, r ∗ , q ∗ ) = (r̄ , q̄ ) = max (r − r ∗ )(q − q ∗ ).

(r ,q )∈R

5 January 2010 9/29

 1 Motivation

2 Basic Game Theory

Noncooperative Game
Cooperative Game

3 Noncooperative Game on the Gaussian Interference Channel

SISO Game
MISO Game
MIMO Game

4 Summary

5 January 2010 10/29

Noncooperative Game on the Gaussian Interference Channel

We observe next the gaussian interference channel in three cases;

SISO, MISO and MIMO, where hold these assumptions:
We restrict to two player games, K = 2.
The two player, transmitter-receiver pair, operate in the same
spectral band.
We treat the interference at receiver as noise (assume low
complexity, interference cancellation is not allowed).
We assume the transmitter use capacity achieving coding. The
achievable rate at receiver R = log(1 + SNR ).

5 January 2010 11/29

SISO Game

TX1 transmits x1 [n] using power P1 ,

TX2 transmits x2 [n] using power P2 .
The signals at two receiver:
[ ] = h11 x1 [n] + h21 x2 [n] + e1 [n],
y1 n

[ ] = h22 x2 [n] + h12 x1 [n] + e2 [n]

y2 n

hji , j , i ∈ {1, 2} is channel

beetween transmitter j und
receiver i.
e1 [n ] and e2 [n ] are samples of

noise process ∼ CN (0, σ 2 )

E [|xi [n]|2 ] = Pi

5 January 2010 12/29

SISO Game

we assume both system transmit continuously with power P1 , P2

and P1 ≤ P¯1 , P2 ≤ P¯2 , P¯1 = P¯2 = P̄
There is competition between two system: if one transmitter
increases its power to improve performance, then it will
simultaneously increases the amount of interference generated to
other system.
the rate at the receivers:
|h11 |2 |h22 |2
= log2 1 + P2P|h121 = log2 1 + P1P|h212
   
R1 2 2 R2 2 2
| +σ | +σ

and the rate utility region is:

[
R= (R1 , R2 )
P1 ≤P̄ ,P2 ≤P̄

5 January 2010 13/29

SISO Game

To achieve points outside R, time-sharing can be used. Split the

available time to τ using power (P1 , P2 ) and 1 − τ using power
(P10 , P20 ), where 0 ≤ τ ≤ 1.
For given τ the achievable rate pair
(τ R1 + (1 − τ )R10 , τ R2 + (1 − τ )R20 ), with:
 0
P1 |h11 |
2   0
P2 h22| |2

0
R1 = log2 1+ 0 2 2
, 0
R2 = log2 1+ 0 2 2
P2 |h21 | + σ P1 |h12 | + σ

the rate utility region becomes:

(τ R1 + (1 − τ )R10 , τ R2 + (1 − τ )R20 )
[
R̄ =
P1 ≤P̄ ,P2 ≤P̄
τ :0≤τ ≤1

R̄ convex hull of R

5 January 2010 14/29

SISO Game

The special case is the orthogonal tranmission, where there is no

interference. The utility region:

(τ R1 , (1 − τ )R2 )
[
R̄orth =
P1 ≤P̄ ,P2 ≤P̄
τ :0≤τ ≤1

The SISO game can be formally dened as:

GSISO = ({1, 2}, [0, P̄ ]2 × [0, 1], {R1 , R2 })

5 January 2010 15/29

SISO Game

Weak Interference Strong Interference

R is convex
time sharing R is not convex
time sharing

can not make it larger. enlarge the rate region.
5 January 2010 16/29
SISO Game

Consider no time sharing, then the Nash Equilibrium is the vector

(P1 , P2 ) for which:

 NE |h |2  
| |2

NE = log 1+
P1 11
≥ log2 1 +
P1 h11
R1 2 NE |h |2 + σ 2 NE
P2 21 P2 |h21 | + σ 2
2

 NE |h |2  
| |2

NE = log 1+
P2 11
≥ log2 1 +
P2 h11
R2 2 NE |h |2 + σ 2 NE
P1 21 P1 |h21 | + σ 2
2

for all P1 and P2 ≤ P̄

There is a trivial Nash Equilibrium, namely (P1 = P̄ , P2 = P̄ )
Proof: waterll the power over the noise and interference. If user
two transmits with constant power over all time slots, then
waterlling power allocation will give also a constant power for user
one.
5 January 2010 17/29
MISO Game

TX1 and TX2 have n transmit antennas. Each can be used with full
phase coherency.
Symbol-sampled complex baseband data at RX1 and RX2 :

y1
T w s + hT w s + e ,
= h11 T w s + hT w s + e
= h22
1 1 21 2 2 1 y2 2 2 12 1 1 2

s1 , s2 are transmitted symbols.

hij is complex valued n × 1 channel vector between TXi and RXj .
wi is beamforming vector used by TXi .

ei is noise term ∼ CN (0, σ ).

2

Each TXi can use maximum transmit power P̄ , but can not be
traded between them.
We take P̄ = 1, so that power constraint kwi k2 ≤ 1, for i = {1, 2}.
Each TXi has dierent channel state infomation (CSI).

5 January 2010 18/29

MISO Game

Well known beamformer techniques that someone can use:

Maximum ratio transmission: beamforming vectors maximize the
power of received desired signal components.
∗ ∗
w1
MRT = h11
, w2
MRT = h22

kh11 k kh22 k

Zero forcing: beamformers assure that the transmitter generates no

interference.
Q⊥ !∗ Q⊥ !∗
ZF = h12 h11 ZF = h21 h22
w1 w2
⊥h k
kh12 ⊥h k
kh21
11 22

where ⊥ H −1 H
X , I − X (X ) − X orthogonal projection onto the
Q
orthogonal complement of column space X .

5 January 2010 19/29

MISO Game

[Jorswieck et.al. 2008] All ecient, i.e. pareto optimal,

beamforming vectors can be parameterized by:
λ1 w1MRT + (1 − λ1 )w1ZF
w1 (λ1 ) =
kλ1 w1MRT + (1 − λ1 )w1ZF k
λ2 w2MRT + (1 − λ2 )w2ZF
w2 (λ2 ) =
kλ2 w2MRT + (1 − λ2 )w2ZF k
for 0 ≤ λ1 , λ2 ≤ 1
The achievable rates:
|w T (λ )h |2
 
R1 (λ1 , λ2 ) = log 1 + 2 1 T1 11 2
σ + |w2 (λ2 )h21 |
|w T (λ )h |2
 
R2 (λ1 , λ2 ) = log 1 + 2 2 T2 22 2
σ + |w2 (λ1 )h12 |
5 January 2010 20/29
MISO Game

λk , 0 ≤ λk ≤ 1 can be interpreted as selshness of user k .

The MISO game is dened as:

GMISO = ({1, 2}, [0, 1]2 , {R1 , R2 })

The Nash equlibrium in this game is a pair of vectors (w1NE , w2NE )

such that:

T
|w NE (λ )h |2 |w T (λ )h |2
! !
log 1 + 2 1 NE T1 11 2 ≥ log 1 + 2 1 NE1T 11
σ + |w2 (λ2 )h21 | σ + |w2 (λ2 )h21 |2
T
|w NE (λ )h |2 |w T (λ )h |2
! !
log 1 + 2 2 NE T1 11 2 ≥ log 1 + 2 2 NE1T 11
σ + |w1 (λ2 )h21 | σ + |w1 (λ2 )h21 |2
for all w1 with kw1 k2 ≤ 1 and w2 with kw2 k2 ≤ 1
5 January 2010 21/29
MISO Game

There is a unique and pure Nash Equilibrium. It is when both

users use their MRT beamforming vectors:
∗ ∗
w1
NE = h11
w2
NE = h22

kh11 k kh22 k

The proof is immediate: if user k uses wkNE then there is no

other wk that satises the power constraint and could yield a
larger Rk . Hence wkNE must be a Nash Equilibrium and must
be unique.
In generall NE doesn't lie on the pareto boundary, because the
avarage NE rates are bounded [Larsson and Jorswieck 2008].
The systems need to coorperate for achieving better rates for
the both.

5 January 2010 22/29

MIMO Game

Transmitters and receivers are equipted with multiple antennas

Baseband received signal at receiver i :

for 1 ≤ i 6= j ≤ 2, where:
X
y i = Hii xi + ji j + ei ,
H x

j 6=i

x i: vector transmitted by TXi

H : at-fading MIMO channel between TXj and RXi
ji
ei : Noise ∼ CN (0, σ ) at RXi
2
H
Qi = E [xi x ] : transmit covariancematrix associated with TXi
i
E [kxi k2 ] = trace (Qi ) ≤ P̄i
P̄i : individual power constraint

The maximum achievable information rate on link i :

( ,
R1 Q 1 Q 2
H Ψ−1 (Q )H Q ),
) = logdet (I + H11 1 2 11 1

5 January 2010 23/29

MIMO Game

with the noise plus interference matrix:

H
Ψ1 (Q2 ) , σ 2 I + H21 Q2 H21

The achievable rate region:

Di , {Q  0 : tr (Q ) ≤ P̄i }
[
R= {R1 (Q1 , Q2 ), R2 (Q1 , Q2 )},
Qi ∈Di

Di is constraint set, containts all feasible strategies for user i .

The game is formally dened by:

GMIMO = ({1, 2}, {D1 , D2 }, {R1 , R2 })

5 January 2010 24/29

MIMO Game

For MIMO Interference channel the NE is not necessarily

unique. Unique if the following condition is satised [Scutari
et.al. 2008]:

ρ HjiH Hii−H Hji if j 6= i ,

(  
ρ(S ) < 1 with [S ]ji =
0 otherwise
where ρ(A) is the largest eigenvalue of matrix A.

If NE exist, it can be approached using iterative

waterlling(IWF):

5 January 2010 25/29

MIMO Game

The rst user computes the transmit covariance matrix.

opt
Q1 (Q2 ) = U1 (µ1 I − D1−1 )+ U1H , where:

-
and D1 are obtained from the eigenvalue decomposition of
U1

the eective channel H11H ψ −1 (Q )H = U D U H .

1 2 11 1 1 1
- µ1 is choosen to satisfy tr [(µ1 I − D1−1 )+ ] = P1 , with
(x )+ , max (0, x ).
Then the second user computes the smilar
opt
Q2 (Q1 ) = U2 (µ2 I − D2−1 )+ U2H

The computations of Q1 and Q2 are then iterated.

5 January 2010 26/29

MIMO Game

The convergence of IWF for two user 2 × 2 MIMO IFC at SNR 15 dB.

5 January 2010 27/29

Summary

Game Theory is an usefull tool for analyzing resource conict in

wireless communication systems.
The Nash Equilibrium is one of the solutions in noncooperative
game, but it doesn't consistently give a good outcome.
In SISO IFC, we have a power allocation game, where the NE is
obtained, if each user uses his maximum power and doesn't do time
sharing.
The game setup in MISO IFC is how to choose the appropriate
beamforming vectors. There exist an unique and pure NE, it is
unfortunately not pareto optimal in general.
In contrast to SISO and MISO game, the NE in MIMO game is
unique only under given condition.
In the case, where NE doesn't give a good outcome, cooperation is
needed for better result.

5 January 2010 28/29

 Thank you for your attention!

5 January 2010 29/29