Cours Bachelier, Paris, France

Game Theory: Fundamentals andApplication to Wireless andElectricity Networks (Cours 1 à 4)
Samson Lasaulce
L2S (CNRS–CentraleSupelec-Univ. Paris Sud)lasaulce@l2s.centralesupelec.fr
May 18-June 15, 2018

Point of view• Start from scratch• Broad audience• Overview• Methodologies• Application-oriented• Channels: 1. Slides; 2. Speech; 3. Board
1

Outline
Class #1:
0. Introduction
1. Strategic form games
Classes #2 and #3:
2. Dynamic games
2.1. Repeated games
2.2. Case study 1: Wireless power control
2.3. Feasible utility region and Shannon theory
2.4. Stochastic games, mean-field games, differential games
2.5. Case study 2: Consumption power scheduling2Outline

Class #4:
3. More3.X. Coalition form games
3.X. Learning in games
3.X. More examples: Game theory and finance?
3.X. Case study, viral marketing strategies
3.X. Bayesian games, signalling games
3.X. Proofs?
3.4. Conclusion3

Game Theory: Fundamentals and Application to Wirelessand Electricity Networks

0. Introduction

4

Game Theory andGame Theory and Optimization...

5

Cambridge University, UK, winter 19796

A couple of details about one of the experiments• 33 ducks.
• Two observers/sites 20 m apart.
• Site 1: 12 items/min.
• Site 2: 24 items/min.

7

Observations

8

Ducks become drivers

9Stuttgart, Germany, 1969 [Braess 1969]

Input flow = 6
f (x) = x + 50, g(x) = 10xh(x) = +∞h(x) = x + 10
83 min92 min(x1, x2) = (3, 3)(x′1, x′2, x′3) = (4, 2, 2)
10

Observing Braess-type instances

In the real life
• Stuttgart 1969: investments into the road network ⇒ traffic ց. Sectionof newly-built road closed ⇒ traffic ր [Knödel 1969].
• NYC 1990: closing of 42nd street in New York City ⇒ amount ofcongestion in the area ր [New York Times 1990].
• Seoul 2003: one of the three tunnels shut down to restore a river and apark ⇒ traffic flow improved.
In many other situations: Wireless networks [Cohen and Kelly
1990][Perlaza et al 2009], energy networks [Baillieul et al 2015], ...

11About the paradox

Trivial inequality in standard optimization
max f (x) ≤ max f (x)
x∈A

x∈B

when A ⊆ B.
This inequality does not hold anymore ⇐ (partial control +multiple utility functions)x = (x1, ..., xK ).

12

Why only partial control?
Complexity issues. ① Smart grid example: charging instantselection 48 time-slots and 16 vehicles 4816 > 3216 > 1021.

13

Why only partial control?
Complexity issues. ② Wireless example: channel selection
with 16 channels and 16 users 1616 = 264 > 1018.

14

Why multiple utility functions?

• Main function decomposition,• several performance criteria,• several decision-makers, ...

15

Let’s recap. DO-GT-MOO◮ Distributed optimization (DO): typically about partial control
with one DM.
◮ Multi-objective optimization (MOO): typically about one DM
with full control + several objectives [Björnson et al 2015].
◮ ”Non-cooperative” game theory (GT): typically about several(virtual/real) DMs with partial control + several objectives.
What is the meaning of optimality then?

16

Typical issues in scenarios with partial control andmultiple objectives◮ Which solution concept to consider as a possible gameoutcome?
◮ Does it exist for the game of interest? Is it unique?
◮ Is it efficient? How do we measure efficiency? How do we
improve it?
◮ NE: What is it? Existence? Uniqueness? Efficiency?
Existence of a convergent and implementable algorithm?

17

What is a game exactly?

Main mathematical representations• Strategic or normal form games.
• Extensive form games.
• Coalitional form games.

18Cheap map of the game theory jungle

Direct gametheoryApproach:Sec. II

Solutionconcept:

NE

Solutionanalysis:

Algorithm
design:Sec. IV

Strategic
form

Mathematicalrepresentation:Reverse game theory(mechanism design)

CE

Coalition
form

NBS

Core

Other forms (extensive form,
state-space representation, etc.)

not addressedin this paper

Shapley
value

Existence, uniqueness, characterization, efﬁciency, ...

BRD

FP

RL
Sec. III

RM

Consensus

Merge-andsplit
Sec. V[Bacci et al 2016]19

Game Theory: Fundamentals and Application to Wirelessand Electricity Networks

1. Strategic form games

20

Strategic form
Game ≡ triplet:

G = (K, {Si}i∈K, {ui}i∈K) .
◮ K = {1, ..., K} is the set of players.
◮ Si is the set of strategies for player i.
◮ Player i’s payoff/utility function:
ui : S1 × ... × Si × ... × SK →
R
.
→
7
u
(s
,
s
)
(s
,
...,
s
,
...s
)
i
i
−i
1
i
K
{z
}
|
s : strategy profile

21

Remark on the strategic form

∃ a more general form:

G = (K, {Si}i∈K, i)

22

Existence of a utility function (1/2)

Proposition (Debreu 1954): there exist no utility functions for lexicographic
ordering on R2 .
Proposition: there exists a utility function for every transitive and complete ordering on
any countable set:• completeness: x  y or y  x or both;• transitivity: “x  y and y  z ” ⇒ x  z .
Proposition (Debreu 1954): there exists a utility function for every transitive, complete,and continuous ordering on a continuous set X ⊂ RN provided X is non-empty, closed,and connected:• continuity: B(x) = {y ∈ X : x  y} and W(x) = {y ∈ X : y  x} are closed.
Remark (connectedness): X is said to be disconnected if it is the union of two disjoint
nonempty open sets. Otherwise, X is said to be connected.
23

Existence of a utility function (2/2)

Theorem (preferences over lotteries): the complete and transitive preference ordering over ∆(S) admits a utility function (expected utility) if and only if  meets the VNM
axioms of independence and continuity:• VNM independence axiom: x ≻ y ⇒ (1 − µ)x + µz ≻ (1 − µ)y + µz , µ ∈]0, 1[;• VNM continuity axiom: x ≻ y ≻ z ⇒ ∃µ ∈]0, 1[, (1−µ)x+µz ≻ y ≻ (1−µ)z+µx.
Remarks: the Allais paradox (1953), voting procedures.

24

Prisoner’s dilemma under strategic form

Market power terminology [Singh 2009]:◮ Players K = {G1, G2}.
◮ Strategies are merely actions S1 = S2 = {low, high}.
◮ Utility function for Player 1:

u1(s1, s2) =

0
1
3
4

if
if
if
if

(s1, s2)(s1, s2)(s1, s2)(s1, s2)= (low, high)= (high, high).
= (low, low)
= (high, low)25

Generator’s dilemma under matrix form

G1, G2high price
low pricehigh price low price(3, 3)(4, 0)(0, 4)(1, 1)

26

A fundamental solution concept: The Nash equilibrium(NE)

Pure Nash equilibrium. Strategy vector/profile such that∀i ∈ K, ∀si ∈ Si, ui(s∗i , s∗−i) ≥ ui(si, s∗−i).
Mixed Nash equilibrium . . .

27

Mixed strategies

28

Mixed strategies

29Mixed strategies and mixed NE◮ Mixed
strategies πi ∈ ∆(Si) with X
xj = 1∆(Si) = x ∈ R|Si| : xj ≥ 0,j◮ Expected utilityuei(π1, ..., πK ) = Eπ1⊗...⊗πK [ui(s1, ..., sK )] .

◮ Mixed Nash equilibrium

∗
∗
).
)≥u
ei(πi, π−i∀i ∈ K, ∀πi ∈ ∆(Si), uei(πi∗, π−i30Three strengths of the Nash equilibrium◮ Stability property (once you are there).
◮ Dynamical property (to get there).
◮ It “always” exists.

31

Dynamical property: Special caseBest-response

BRi(s−i) = arg max ui(si, s−i).
si∈Si

32

Illustration for continuous sets [Cournot 1838]

‫݌‬ଶ
BR ଶ

‫=ݐ‬3

BRଵ

‫=ݐ‬1

‫=ݐ‬0

‫=ݐ‬2

‫=ݐ‬4

‫݌‬ଵ
33

The sequential best-response dynamics (1/3)

G1, G2 high
high
low

low

(3, 3) (0, 4)(4, 0) (1, 1)

34

The sequential best-response dynamics (2/3)

G1, G2 high
high
low

low

(3, 3) (0, 4)(4, 0) (1, 1)

35

The sequential best-response dynamics (3/3)

G1, G2 high
high
low

low

(3, 3) (0, 4)(4, 0) (1, 1)

36

Nash equilibrium characterization

A strategy profile s∗ is an NE of G iff:∗∗
si ∈ BRi(s−i)∗∗⇔ s ∈ BR(s )where

BR : S →S
s 7→ BR1(s−1) × BR2(s−2) × ... × BRK (s−K )37

Nash equilibrium existence (finite games)

Nash existence theorem [Nash 1950].
S = S1 × ... × SK is finite. Then, there is a mixed NE.

Kuhn existence theorem [Kuhn 1953]. Every
finite game of perfect information has at least one
pure NE.

38

Nash equilibrium existence (continuous strategy sets)

Glicksberg theorem [Glicksberg 1952]. Si
compact, ui continuous in s. Then, there is a mixed
NE.
Debreu-Fan-Glicksberg theorem [Debreu, Fan,
Glicksberg 1952]. Above assumptions & ui
quasiconcave in si. Then, there exists a pure NE.

39

More about the existence of NE[Lasaulce & Tembine 2011]40

Simplified methodology for studying NE

Static games

Dynamic games

Existence

Existence

UniquenessUtility region characterization ; uniqueness

Efficiency

Design of strategies

41Uniqueness (concave games)
Rosen theorem [Rosen 1965]◮ Si compact convex.
◮ ui continuous in s.
◮ ui concave in si.
◮ Diagonally strict concavity:′T∃r > 0, ∀s 6= s , [s − s] [γr (s) − γr (s′)] > 0
where

′



∂u1
∂uK
γr (s) = r1(s), ..., rK
(s) .
∂s1
∂sK

Then, there is a unique pure NE.
42

Concave game example

Utility:H
H
u1(A1, A2) = E log I + X 1A1X H
−E
log
+
X
A
X
I
+
X
A
X
2
2
2
2
2
1
2

Action space:oA1 = A1 ≥ 0, AH
1 = A1 , TrA1 ≤ an

1. DSC is met (trace inequality); 2. NE determination (randommatrix theory) [Belmega et al 2011]43

Uniqueness (standard games)

Definition (standard functions) A vector function
K→R
g : RK+ is standard if we have:
+
′
′
,
x
≤
x
⇒
g(x)
≤
g(x
).
◮ Monotonicity: ∀(x, x′) ∈ R2K+◮ Scalability: ∀α > 1, ∀x ∈ RK
+ , g(αx) < αg(x).
Theorem [Yates 1995] If BR = (BR1, ..., BRK ) is standard,then there is a unique pure NE.
Remark: BR intersection.

44

More about the uniqueness of NE

Apply[Ros65]Yes

Apply[MS96]

CG?

Yes

PG?
No
No

Not
treatedIs there aunique NE?

SG?
No

Apply
[Yat95]
Yes

No

BRs?
Yes

Prove
 BRs ^a`

[Lasaulce & Tembine 2011]45

Obviously the Nash equilibrium has also drawbacks• Efficiency: typical consequence of partial control• Correlation: mixed NE assume independent lotteries• Strategic stability: only stable to single deviations• Not fully adapted to QoS constraints
For more drawbacks see [Perlaza & Lasaulce 2014]

46

Solution concepts for strategic/extensive form games• Pure/mixed Nash equilibrium, Wardrop equilibrium,• correlated equilibrium, coarse correlated equilibrium,• N − strong equilibrium,• Nash equilibrium refinements :equilibrium, proper equilibrium,

trembling hand perfect• ǫ−Nash equilibrium,• logit equilibrium,47

Solution concepts for strategic/extensive form games.
Continued• maxmin strategy profiles,• Bayesian equilibrium,• evolutionary stable solution,• satisfaction equilibrium, generalized Nash equilibrium,• Stackelberg equilibrium,• Pareto optimum, social optimum,• bargaining solutions (Nash, egalitarian, Kalai-Smorodinsky,etc.),...
48

How to measure efficiency: Pareto efficiency

Definition (Pareto-dominance): s Pareto-dominates s′ if:∀i ∈ K, ui(s) ≥ ui(s′),
with strict inequality for at least one player.
Definition (Pareto-optimum): s∗ is Pareto-optimal (-efficient)
if it is dominated by no other profile.

49

Illustration of Pareto optimality

‫ݑ‬ଶ

‫ݑ‬ଵ

50

How to measure efficiency : Social welfare

Definition (social welfare): the social welfare of a game isdefined as:

w=

K
X

ui .

i=1

Definition (social optimum): an SO is a strategy profile
which maximizes w.
Remark: An SO is a PO.

51

How to measure efficiency : PoA and PoS
Definition (price of anarchy):
max w(s)
PoA =

s∈S

min w(s∗)

s∗∈S NE

where S NE is the set of NE of the game.
Definition (price of stability):
max w(s)
PoS =

s∈S

∗ .

max w(s )s∗∈S NE[Papadimitriou 2001] [Anshelevich et al 2004].
52

Example: PoA in non-atomic routing games
The network cost is defined by:C(x) =X

cr (xr )xr

r∈R

Theorem. For polynomials costs of maximum degree d, the
PoA is bounded as:
degree 1
2
3
4
...
d
4
d
PoA
1.626
1.896
2.151
...
Ω(
3
ln(d) )
[Correa et al 2005].
53

How to improve efficiency

Possible approaches (non-exhaustive list)◮ Introduce pricing.
◮ Introduce hierarchy.
◮ Introduce coordination (e.g., correlated equilibrium).
◮ Introduce cooperation (bargaining, cooperation plan in
dynamic games, agreement/contract in coalitional games, ...).

54

How to improve efficiency (pricing). Example
Scenario

S
BS1

BS2

MS1

K >> 155

Example (utilities)

Utility of player k when connecting to base station s1υk,s(x) = log 1 +,as + bxs
as > 0, b > 0.

56

Example (illustration)
Social welfare for S = 2
1.8

1.7
PoA = 1.23
1.6

Social welfare

1.5

1.4

Social optimum

1.3

1.2

Nash equilibrium

1.1

1

0.9

0.8

0

0.1

0.2

0.3
0.4
0.5
0.6
0.7
Fraction of users connected to base station 1

0.8

0.9

1

57

Example (pricing and modified game)Let nk be the data volume to be transferred:nk
τk,s(x) =.
υk,s(x)
Cost function of the new game:ck,s(x) = p(τk,s(x)) + βs.
Parameter adjustment → desired solution.

58

How to improve efficiency: introduce coordination
through correlated equilibria
Definition (correlated equilibrium) Let σk : Ak → Ak be amapping. Then q CE is a CE if∀k,
X∀σk ,Xq CE(ak , a−k )uk (ak , a−k ) ≥q CE(ak , a−k )uk (σk (ak ), a−k ),
a∈A

a∈A

Example (CR coordination game)
Low
HighHigh (5 , 1 ) (0, 0)
Low (4, 4 ) (1 , 5 )59Set of correlated equilibria

60

Nash bargaining solution

Definition The NBS is the unique solution ofmax(u1 − λ1)(u2 − λ2)subject to

u1 ≥ λ 1 , u2 ≥ λ 2(u1,u2) ∈ U

where U is the game feasible utility set.

61

Illustration of the NBS

62

Game Theory: Fundamentals and Application to Wirelessand Electricity Networks

2. Dynamic games

63

Dynamic games
Typical ingredients◮ Several stages.
◮ Notions of game history, action plans.
◮ Average/long-term utility.
◮ The stage utility is state-dependent (ui(a, x)).
Informal definition. A game in which at least one player canuse a strategy depending on previously played actions. No
universal definition, only special classes.
64

Important classes of dynamic games◮ Repeated games (∅).
◮ Stochastic games (MDP).
◮ Differential/difference games (OC).
◮ Mean-field games.

◮ Evolutionary games.

65

Repeated games with perfect monitoring
Definition (game history): ∀t ≥ 1,
ht = (a(1), ..., a(t − 1)) ∈ Ht where Ht = At−1.
Definition (pure strategy): A pure strategy for player i ∈ K isa sequence (τi,t)t≥1 with
τi,t : Ht → Ai
ht 7→ ai(t)Definition (behavior strategy): A behavior strategy for playeri ∈ K is a sequence (eτi,t)t≥1 with
τei,t : Ht → ∆(Ai)
ht 7→ πi(t).
66Repeated games utilities
Finitely repeated games. Let τ = (τ1, ..., τK ) and T ≥ 1:T

1X
Tui(a(t)).
vi (τ ) =T t=1
Infinitely repeated games:T

1X∞
vi (τ ) = limui(a(t)).
T →+∞ T
t=1
Discounted repeated games. Let 0 < λ < 1 be the discountfactor:+∞Xλ(1 − λ)t−1ui(a(t)).
viλ(τ ) =t=1

67

Equilibria in repeated games

Definition (equilibrium strategies). A joint strategy τ ∗supports an equilibriumof the repeated gameK, {Ti}i∈K, {viy }i∈K , y ∈ {T, ∞, λ}, if:∗).
∀i ∈ K, ∀τi′ , viy (τ ∗) ≥ viy (τi′, τ−iRemark (equilibrium analysis): Existence for finite games,
compact games, static games with a Nash equilibrium. In
contrast with static games, there can be many equilibria.

68Equilibrium characterization for discounted repeatedgames with perfect monitoring

Folk theorem. The set of equilibrium utilities when λ → 0 is
given by
E0 = IR(G) ∩ co (U (G))
where:• IR(G) = {u ∈ RK , ∀i ∈ K, ui ≥ min max uei(π)};π−i

πi• U (G) = {u′ ∈ RK : ∃a, u(a) = u′}.

69

Illustration
Repeated prisoner’s dilemma

70Relaxing the perfect monitoring assumption:2−connected graphs
Definition (strongly connected graph) A graph Γ is said tobe strongly connected if for each pair of vertices (i, j), there isa directed path from i to j.
Definition (2−connected graph) The graph Γ is 2−
connected if, for any vertex i, Γ\{i} is strongly connected.
Theorem The following two assertions are equivalent:(i) the observation graph of the infinitely repeated games is2−connected;(ii) E∞ = IR(G) ∩ co (U (G)).
[Renault and Tomala 1998]71

Case study #1: Wireless power control◮ Static game formulation.
◮ A repeated game formulation.

72

Near far effect73

A wireless power control scenario

74

Modeling the problem as a static game [Goodman &Mandayam 2000]

Time slots
g(1)
a(1)

g(2)
a(2)

g(3)
a(3)

...
...

75

Modeling the problem as a static game. Continued◮ Set of players: K = {1, ..., K}.

◮ Set of actions : Ai = [0, Amax ].
◮ Utilities: energy-efficiency;
benefit f (βi)
ui(ai, a−i) =
=
cost
ai

where

giai
X
.
βi =
1+
gj aj
j6=i

76

Properties assumed for f• f non-negative, continuous, and non-decreasing.
• f sigmoidal.
f (x)
• lim
= 0, lim f (x) = const ≤ 1, 0 ≤ f (x) ≤ 1.
x→+∞
x→0 x
77

Nash equilibrium analysis (1/3)

Existence78

Nash equilibrium analysis (1/3)

Existence• Ai = [0, Amax]: compact, convex.
i• ui is continuous w.r.t. a = (a1, ..., aK ).
• ui is quasi-concave w.r.t. ai (f (x) sigmoidal ⇒ f (x)x is quasiconcave).

79

Nash equilibrium analysis (2/3)

Uniqueness80Nash equilibrium analysis (2/3)
UniquenessThe best response is a function and


X
β
1+
gj aj ∀i ∈ K, BRi(a−i) =gi
j6=i

with β ⋆f ′(β) = f (β).
The game is standard:• Monotonicity: a′ ≤ a ⇒ BR(a′) ≤ BR(a).
• Scalability: ∀α > 1, BR(αa) < αBR(a).
81Nash equilibrium analysis (3/3)

Determination (interior point)i
Solve the system of equations ∂u∂ai (a) = 0, which leads to:1β⋆∀i ∈ {1, ..., K}, ai =.
gi 1 − (K − 1)βProblem Generally inefficient solution. How to improve
efficiency?

82

Introduce pricing
Main points◮ New utility:uei(a) = ui(a) − αai, α ≥ 0.

◮ Good news. The new NE profile Pareto-dominates a⋆.
◮ Bad news. Uniqueness not guaranteed, convergence undersome specific assumption. Global state information isrequired.
[Saraydar et al 2002].
83

Repeated game formulation
Strategic form
G m = (K, {Ti}i , {vim}i) with m ∈ {T, λ}.
If m = T :
viT =

T
X
1

T t=1

ui(a(t)).

If m = λ ∈ (0, 1]:
viλ =

+∞
X

λ(1 − λ)t−1ui(a(t)).

t=1[Le Treust and Lasaulce 2010]84

Observation

Public signal choiceKX

βi(t) + 1
giai(t) = ai(t)gi ×
ω(t) , 1 +
βi(t)
i=1

85

Strategic form. Continued
Pure strategiest−1

τi,t : (Ai × Ω)
→ [0, Amax
]
i
t−1
,
ω
) 7→
ai(t)
(at−1
i
where
= (ai(1), ai(2), ..., ai (t − 1));
• at−1i• ω t−1 = (ω(1), ω(2), ..., ω(t − 1));"• Ω = 1, 1 +

K
X
i=1

#

.
gimaxAmaxi

86

An interesting Nash equilibrium of G m, m = T

Proposed equilibrium point

∗
=
τi,t

aOP
i
a⋆i
Amax
i

1−γ
if t ∈ {1, 2, . . . , T − t0}
and ω(t) = 1−(K−1)γ1−γ
if t ∈ {T − t0 + 1, . . . , T } and ω(t) = 1−(K−1)γ1−γ
ifω(t) =
6 1−(K−1)γwhere γ[1 − (K − 1)γ]f ′ (γ) − f (γ) = 0 and∀i ∈ K,

γ
1
OP
pi =
.
gi 1 − (K − 1)γ87

Comments◮ To obtain OP, impose gj aj = const.
◮ t0 comes from the equilibrium condition:

Let





f (β)[1−(K−1)β]
f (α)
−


α
β


t0 =  f (α)[1−(K−1)α]

f (α)


−


P
α
α 1+
g P max 
j6=i j j◮ Local knowledge. Pareto domination of the NE of G. Goodin terms of social welfare.

88Time-varying parameter case
◮ Repeated game methodology holds (worst-case scenario).
For instance, t0 becomes:gimax f (α)
f (β)[1−(K−1)β]min α −βgit0 = 
.
g max
i


f (α)
min
 f (α)[1−(K−1)α]

g
i




− P
α
max
min

α
gj +1 j6=i Pj◮ Stochastic game formulation: i.i.d. state, v Ti = Eg
• good: better performance; T vi (.)• bad: more information is needed (parameter distribution).
89

Illustration (fixed parameter)90

Illustration (time-varying parameter)[Mériaux et al 2011]91

Observations◮ Stochastic game case = most general case + most efficient
policies.
◮ Importance of characterizing equilibrium points.

92Reminders

93

Feasible set characterization for stochastic games with
i.i.d. common state◮ Stage utilities: ui(a0, a1, ..., aK ); ai ∈ Ai, |Ai| < ∞◮ Observation/signal structure: k(si|a0), Γ(yi|a0, a1, ..., aK );|Si| < ∞, |Yi| < ∞◮ Long-term utilities:
T

1X∞
vi (τ1, ..., τK ) = lim
E [ui(A0(t), A1(t), ..., AK (t))]
T →+∞ T
t=1
References: [Larrousse and Lasaulce 2013][Larrousse et al2015][Larrousse et al 2018]94

Stage game description (example)◮ Decision-makers: {1, 2}; 0 ≡ nature.
◮ Action sets: A0 = A1 = A2 = {0, 1}.
◮ Stage utility function:u(a0, a1, a2) =1
0

if a0 = a1 = a2.
otherwise95

Observation structure◮ Stages: t ∈ {1, 2, ..., T }, T ≥ 2.
◮ DM 1 knows aT0 = (a0(1), a0(2), ..., a0 (T )) and has perfectrecall.
◮ ∀t ≥ 2, DM 2 knows at0 = (a0(1), ..., a0 (t − 1)), perfectly
monitors DM 1’s actions at1 = (a1(1), ..., a1 (t − 1)), and has
perfect recall.
Question: To what extent can they coordinate?
"

T
X

#

"

T
X

1
1
u(A0(t), A1(t), A2(t)) = E
ut
E
T t=1
T t=1

#
96

Trivial upper boundCentralized case

"

T
X

#

"

T
X

#

1
1
E
ut ≤ Emax u(a0(t), a1, a2) = 1.
T t=1
T t=1 (a1,a2)

97

Average utility◮ Scheme 1:
a0
a1
a2

0

0
|

0

|

0
|

1

|

1

|

|

1
|

1

0

1
|

|

0

1

1

1
|

|

|

|

···

1
|

1
|

···

1

|

···

1
|

Match nature|◮ Average utility
"

T
X

#

1
1
E
ut → = 0.5.
T t=1
2

 
1
for A0 ∼ B
298Average utility◮ Scheme 2:
x0
x1
x2

0

0
|

0

1

|

0

0

|

0

0

|

1

···

1

···

1

···

|

1

|

0

0

0

1

|

0
|

0
|

◮ Average utility:
"

T
X

#

1
5
E
ut → = 0.625.
T t=1
8

99

Maximal average utility

"

T
X

#

1
E
ut → γ ⋆ ≃ 0.81
T t=1
where

γ

⋆

h(x) − 1= log2 3
is the solution ofx−1

and h(x) = −x log2 x − (1 − x) log2(1 − x).

100Strategies◮ Causal case:
τi,t :→ Ai
Sit × Yit−1(si(1), ..., si (t), yi(1), ..., yi (t − 1)) 7→ ai(t)◮ Noncausal case:
τi,t :

SiT × Yit−1→ Ai(si(1), ..., si (T ), yi(1), ..., yi (t − 1)) 7→ ai(t)101Important observation

102

Important observationvi∞(τ1, ..., τK )
T
1X
= lim
E [ui(A0(t), A1(t), ..., AK (t))]
T →+∞ T
t=1
T
1X X
PA0(t),...,AK (t)(a0, ..., aK )ui(a0, ...aK )= lim
T →+∞ T
t=1 a ,...,a
0

K

T

1X
PA0(t),...,AK (t)(a0, ..., aK )=ui(a0, ...aK ) lim
T →+∞ Ta ,...,a
t=1
0

X

K

103

Implementable coordination

Definition Q(a0, a1, ..., aK ) is implementable if ∃ (τ1, ..., τK ) s.t.
T
X
1

T t=1

PA0(t),...,AK (t)(a0, ..., aK ) → Q(a0, a1, ..., aK )104

Characterization of implementable distributions(noncausal case)

Theorem 1− (A0(t))t≥1 i.i.d; A0 ∼ ρ0
−K=2
− A1(t) = τ1,t(A0(1), ..., A0 (T ))− A2(t) = τ2,t(A1(1), ..., A1 (t − 1))◮ Then Q(a0, a1, a2) is implementable iff its marginal w.r.t(a1, a2) is ρ0 and
HQ(A0, A1, A2) ≥ HQ(A0) + HQ(A2).

105Performance characterization (Theorem 1)

minimize−X

Q(a0, a1, a2)w(a0, a1, a2)

a0,a1,a2subject to HQ(A0) + HQ(A2) − HQ(A0, A1, A2) ≤ 0
X−Q(a0, a1, a2) ≤ 0
Q(a0, a1, a2) = 0
−1 +
a0,aX
1 ,a2
Q(a0, a1, a2) = 0−ρ0(a0) +
a1,a2

106

Technical challenges◮ General case [Larrousse et al ITW 2015]

IQ(S1; A2) ≤ IQ(V ; Y2|A2) + IQ(V ; S1|A2)
where auxiliary variables are used.

107

Characterization of implementable distributions (causal
case)

Theorem 2− (A0(t))t≥1 i.i.d. + memoryless O.S.
−K≥2
− Ai(t) = τ1,t(Si(1), ..., Si (t), Yi(1), ..., Yi (t − 1))◮ Then Q(a0, ..., aK ) is implementable iff it factorizes as
Q(a0, ..., aK ) =X

ρ0(a0)k(s1, ..., sk |a0)PZ (z)z,s1,...,skK
YPAk |Sk ,Z (ak |sk , z)

k=1

[Larrousse et al 2015][Gossner et al 2006]108

Extensions• Security aspect• Continuous case• Controlled state109

Stochastic games

Definition (Stochastic gameswith individual states): a stochastic
 game with individualei }i , {αi }i , q, {ui }i wherestates is a 6−uplet G = K, {Ai }i , {Xi }i , {A

• Ωi is the set of individual states of player i;
ei (xi ) is the set of feasible actions for the state xi ∈ Xi ;• A
• αi : Xi → 2Ai is the correspondence determining the feasible actions at a given stateof the game;• under the Markov game assumption, the transition probability of the states is given by:
q:

NK A
i
X ×
i=1 2
(x, a)→7→∆(X )q(x′ |x, a).

with X = X1 × ... × XK .

110

Equilibrium analysis for stochastic games• Common state with perfect monitoring and recall + finite action and state spaces: there
exists an equilibrium in the finitely/discounted repeated games (see Shapley 1953 for
2−player zero-sum games and Takahashi 1962 Fink 1964 for non-zero-sum games).
• Individual states with perfect monitoring and recall: there exists an equilibrium in thefinitely/discounted repeated games (see Vrieze 2007).
• Common state + perfect monitoring + irreducible stochastic games: there is a Folk
theorem for infinitely repeated games (Dutta 1991).
• Common state + public signal + irreducible stochastic games: there is a Folk theorem
for infinitely repeated games (Hörner etal 2009, Fudenberg and Yamamoto 2009).
• ...

111

Differential games (linear-quadratic + common state +finite horizon)• Control functions: ui : t 7→ ui(t), i ∈ {1, ..., K}• State law:

KXdx
Bi(t)ui(t)(t) = A(t)x(t) +dt
i=1• Cumulative utility:Ji(u1, ..., uK ) =Z

xT(t)Qix(t)dt+t∈[0,T ]X

j = 1KZ

t∈[0,T ]uT
j (t)Rij uj (t)dt+qi (xT )112

More general differential games• More general control law:ui(t, yi(t))• More general state law:dx(t) = f (t, x(t), u1(t, y1(t)), . . . , uK (t, yK (t)))
dt• More general observation structures. Closed-loop perfect state example:
yi(t) = {x(t′) : 0 ≤ t′ ≤ t}. Memoryless perfect state example: yi(t) ={x(0), x(t)}.
• Remark (stochastic differential game):dx(t) = f (t, x(t), u1(t, y1(t)), . . . , uK (t, yK (t)))dt + dw(t)→ One path to mean field games.
113

Equilibrium analysis for differential/difference games

Basar, T., Olsder, G.J., 1982. Dynamic noncooperative game theory. In: Classics inApplied Mathematics, first ed. SIAM, Philadelphia.
T. Eisele, ”Nonexistence and Nonuniqueness of Open-Loop Equilibria in Linear-Quadratic
Differential Games”, Journal of optimization theory and applications, Vol. 37, No. 4, Aug.
1982.
G. Jank, ”Introduction to Non-cooperative Dynamical Game Theory”, Coimbra, March
2001.
G. Jank and H. Abou-Kandil, ”Existence and Uniqueness of Open-Loop Nash Equilibria in
Linear-Quadratic Discrete Time Games”, IEEE Trans. on Automatic Control, Vol. 48, No 2,
Feb. 2003.
Engwerda, J.C., 2005. LQ Dynamic Optimization and Differential Games. Wiley.
P. Cardaliaguet, ”Introduction to differential games”, Lecture Notes, 2010.
M. Quincampoix, ”Differential games”, Computational complexity. Vols. 16, 854861,
Springer, New York, 2012.
114

Game Theory: Fundamentals and Application to Wirelessand Electricity Networks

3. Learning algorithms andstrategic-form games

115

Algorithm 1: The best-response dynamics (BRD)

Updating rule (asynchronous BRD) K = 2. Action
sequence: a1(0), a2(1) ∈ BR2[a1(0)], a1(2) ∈ BR1[a2(1)], etc.
More generally:ai(t + 1) ∈ BRi [a1(t + 1), ..., ai−1 (t + 1), ai+1(t), ..., aK (t)] .
Updating rule (synchronous BRD):ai(t + 1) ∈ BRi [a−i(t)] .
[Cournot 1838]116

Comments on Algorithm 1

Main features◮ Fast convergence.
◮ Steady state: NE.
◮ Required knowledge: Action profile and individual utility
function (in general).

117

The iterative water-filling algorithm [Yu et al 2002]◮ Actions: ai = pi = (pi,1, ..., pi,S ) withX

pi,s ≤ P max ands

pi,s ≥ 0◮ BRD:
pi(t + 1) ∈ argmax
pi

S
X
s=1


log 1 +

gii,spi,sX
σ2 +gji,spj,s(t)



j6=i

◮ The water-filling solution writes as
+

pi(t)
1
−
pi,s(t + 1) =λi SINRi(t)118

Algorithm 2: Fictitious play (FP)
Updating rule (synchronous FP):X
ai(t + 1) ∈ arg max
f−i,t(a−i)ui(ai, a−i).
ai ∈AiRecursive structure
fi,t+1(ai) =
=
=
=

1
t+1

t+1
X

a−i

1l{ai,t′ =ai}

′ =1
tP
t
1
1
1
l
+
′
{a
=a
}
t =1
j
t+1
t+1 1l{aj,t+1 =ai }
j,t′
1
t
f
(a
)
+
i,t
i
t+1
t+1
h 1l{aj,t+1=ai}i
1
1l{aj,t+1=ai} − fi,t(ai)fi,t(ai) + t+1hi= fi,t(ai) + λi(t) 1l{aj,t+1=ai} − fi,t(ai)where 1l is the indicator function [Brown 1951].

119

Algorithm 3: Reinforcement learning

A reinforcement learning algorithm. |Ai| < +∞,∀i ∈ K, ∀n ∈ {1, ..., |Ai |},hi
πin(t + 1) = πin(t) + λi(t)ui(t) 1l{ai(t)=ani} − πin(t) ,0 < λi(t) < 1.

[Bush and Mosteller 1955][Sastry et al 1994].

120

Main features of Algorithm 3◮ Required knowledge: individual utility realizations.
◮ Slow convergence.
◮ Steady state: NE/boundary points/limit cycle.

121

Convergence issue◮ Convergence depends on: the updating rule + the
associated game.
◮ For algorithms 1, 2, and 3, it is sufficient that the game be: dominance solvable, or potential, or supermodular.

122

An important class of games: Potential games

Exact potential games [Monderer and Shapley 1996].
∃Φ, ∀i, ∀s, ∀s′i,ui(s) − ui(s′i, s−i) = Φ(s) − Φ(s′i, s−i).
Characterization (special case). Si = Ii ⊂ R. A game is anexact PG iff:2∂(ui − uj )2
= 0.
∀(i, j) ∈ K ,∂si∂sj123

Potential games. Continued

Properties◮ Convergence of important dynamics. X◮ Existence of a pure NE. X
Examples. Team games, dummy games, self-motivatedgames, congestion games.

124A simple example of potential game

!"
!"#

!$#

%&#

'##

125

A simple example of potential game [Perlaza et al 2009]







gi,spi,sXui(p1, ..., pK ) =log 1 +
2σ +gj,spj,s 
s=1
SX

X j6=i 
gj,spj,s
σ2 +
S


X
j


X
=
log 

2

σ +
gj,spj,s 
s=1




j6=i

= log σ +
2

X
j





gj,spj,s − log σ += Φ(p1, ..., pK ) − log σ +
2

X
j6=i

2

X

j6=i


gj,spj,s

gj,spj,s

126

Another important special class of games: Supermodular
games

Definition (supermodularity): Si compact subset of R, ui
upper semi-continuous in s, ∀s−i ≥ s′−i, ui(s) − ui(si, s′−i) is
non-decreasing in si.
Characterization:
∂ 2ui
≥ 0.
∀i 6= j,∂si∂sj127

Supermodular games. Continued

Properties◮ Convergence of important dynamics. X◮ Existence of a pure NE. X
Examples. Queueing problems [Yao 1995], power control
problems [Saraydar et al 2002].

128

A simple example of supermodular game [Mochaourab &Jorswieck 2009]!"#$%&$%'()*+'(,-*"%'()*+'(

129

Algorithm 4: Regret Matching

Definition (regret) [Hart & Mas-Collel 2000]∀n, rk,ak,n (t+1) =

t
X
1

t ′

uk (ak,n, a−k (t′))−uk (ak (t′), a−k (t′))

t =1Updating rulei+hrk,ak,n (t + 1)

πk,ak,n (t + 1) = Nk hi+Xrk,ak,n′ (t + 1)
n′=1

130

Main features of Algorithm 4◮ Required knowledge: action profile◮ Convergence: unconditional convergence +intermediate speed◮ Steady state: CCE
Remark: ”pure NE ⊆ mixed NE ⊆ CE ⊆ CCE”

131

Coarse correlated equilibrium

Definition∀k, ∀a′k ,
X

a∈A

q

CCE

(a)uk (a) ≥X

q CCE(a)uk (a′k , a−k )

a∈A

132

Algorithms to reach a given solution concepts (strategiccase)• Asynchronous/synchronous best response dynamics,
fictitious play, a type of reinforcement algorithm, regret
matching,• Boltzmann-Gibbs learning,• coupled dynamics learning,• trial-and-error learning,• conditional no-regret learning,• Bayesian learning,...
133

Game Theory: Fundamentals and Application to Wirelessand Electricity Networks

4. Case study #2:
Power consumption scheduling134

Case study #2: Power consumption scheduling◮ Static game formulation.
◮ A dynamic approach.

135

Application example. Continued

0h

4h

8h

12 h

16 h 19 h

24 h

136

Modeling the problem as a static game
◮ Set of players: I = {1, ..., I}.

◮ Set of actions : si ∈ Si = {1, ..., T }◮ Action profile◮ Total load
◮ Utilities: s = (s1, ..., sI ):ℓt(s) = ℓexo+t

: ui(s) =PEVℓi i,t (s)Xft (ℓ1(s), ..., ℓt (s)) + gi(si)t∈{si ,...,si+Di −1}137Nash equilibrium analysis (1/6)

Existence138Nash equilibrium analysis: Existence (2/6)

Exact potentiality [Monderer Shapley 1996]∃Φ, ∀i, ∀s, ∀s′i :ui(s) − ui(s′i, s−i) = Φ(s) − Φ(s′i, s−i)
Ordinal potentialityui(s) − ui(s′i, s−i) ≥ 0 ⇔ Φ(s) − Φ(s′i, s−i) ≥ 0
Result [Beaude et al TSG 2016]: OP available formemoryless utilities.
139

Nash equilibrium analysis (3/6)

Uniqueness No

140

Nash equilibrium analysis: Determination (4/6)

141Nash equilibrium analysis: BRD convergence (5/6)

Empirical convergence probability (%)

100

98

96

94

δ = 0, M = 100
92

90

88

Obtained with the data from [37]Obtained with 104 draws froma Gaussian random vector
0

5

10

15

20

25

30

35

40

45

Number of electric vehicles

142Nash equilibrium analysis: Efficiency (6/6)

PoA: PoA → 1 when I → ∞ and under symmetry
assumptions. Otherwise, losses may be non-negligible.
→ Continuous actions
References: [Beaude et al Netgcoop 2012][Beaude et al TSG
2016][Paccagnan et al L-CSS 2018]143

Why moving to a dynamical formulation?

144

Why moving to a dynamical formulation?

145

Objectives for the new formulation: Recap◮ Existence of an individual constraint on the state◮ More efficiency: discrete actions → continuous actions;
exploit the dynamical structure◮ Directly consider the global cost/utility function

146

Optimal control formulation

minimize g(v, x) =TXeαxt + J

I
X

+
ℓexo
t

t=1

∀i,

T
X

!

s.t. :

!2

+ ct

vi,t

i=1

vi,t ≥ Ci

t=1∀(i, t),∀t

0 ≤ vi,t ≤ Vmax
xt = axt−1 + b1 ×
+b2 ×

+
ℓexo
t
ℓexo
t−1 +

I
X

vi,t

i=1
I
X

vi,t−1i=1∀t,

xt ≤ xmax!2147

Optimal control formulation

minimize g(v, x) =TXeαxt + J

+
ℓexo
t

t=1

∀i,

T
X

I
X

!

s.t. :

!q

+ ct

vi,t

i=1

vi,t ≥ Ci

t=1∀(i, t),∀t

0 ≤ vi,t ≤ Vmax
xt = axt−1 + b1 ×
+b2 ×

ℓexo
+
t
ℓexo
t−1 +

I
X

i=1
I
X
i=1

∀t,

xt ≤ xmax ,

vi,t

!p

vi,t−1148

Optimal control formulation

minimize g(v, x) =TXeαxt + J

I
X

+
ℓexo
t

t=1

∀i,

T
X

!

s.t. :

!q

+ ct

vi,t

i=1

vi,t ≥ Ci

t=1∀(i, t),∀t

0 ≤ vi,t ≤ Vmax
xt = axt−1 + b1 ×
+b2 ×

+
ℓexo
t
ℓexo
t−1 +

I
X

vi,t

i=1
I
X

vi,t−1i=1∀t,

xt ≤ xmax ,

!p

149

Optimal control formulation

minimize g(v, x) =TXeαxt + J

I
X

+
ℓexo
t

t=1

∀i,

T
X

!

s.t. :

!q

+ ct

vi,t

i=1

vi,t ≥ Ci

t=1∀(i, t),∀t

0 ≤ vi,t ≤ Vmax
xt = axt−1 + b1 ×
+b2 ×

+
ℓexo
t
ℓexo
t−1 +

I
X

vi,t

i=1
I
X

vi,t−1i=1∀t,

xt ≤ xmax ,

!p

150

Optimal control formulation

minimize J(v, x) =TXeαxt + γ

I
X

+
ℓexo
t

t=1

∀i,

T
X

!

s.t. :

!q

+ ct

vi,t

i=1

vi,t ≥ Ci

t=1∀(i, t),∀t

0 ≤ vi,t ≤ Vmax
xt = axt−1 + b1 ×
+b2 ×

+
ℓexo
t
ℓexo
t−1 +

I
X

vi,t

i=1
I
X
i=1

∀t,

xt ≤ xmax ,!pvi,t−1151

Proposed methodology to solve the problem◮ Substitution technique for xt◮ Operate in a convex regime (e.g., ab1 + b2 ≥ 0)
◮ Apply the best response dynamics with vi = (vi,1, ..., vi,T )[Beaude et al ECC 2015]

152

Stochastic aspects

exo
+ zt
=
ℓ
◮ Noisy forecast: ℓeexott◮ Randomness in the state evolution: e
ct = ct + zt′◮ Discretization + apply the best response dynamics withdynamical programming[Gonzalez et al Gretsi 2017][Gonzalez et al TSG 2018]153Illustration 1

154

Illustration 2

155

Illustration 3

156

Game Theory: Fundamentals and Application to Wirelessand Electricity Networks

4. Coalitional form games

157

Moving from strategic-form games to coalition formgames

◮ Cooperation is sought/allowed◮ Explicit communication is allowed◮ Beyond NBS

158

The bankruptcy problem (Talmud’s version)

Claim
100 200 300
100
3

100
Estate 200 50
300 50

100
3

75
100

100
3

75
150

159

Physical interpretation of the (game-theoretic) solution[Aumann and Maschler 1985].

160

Messages

Coalition games can be a very powerful tool.
Two important issues in coalition games:◮ utility allocation/division;◮ coalition formation.

161

Classification of coalition-form games

Distribution of utility:
Can the value of any coalition be
divided arbitrarily among its members?

Coalition value type:
Does the value function of a coalition
depend on its own members only?

TU: yes

NTU: no

CF: yes

PF: nonot addressedin this paper

162

Coalition form games with characteristic functions

Definition. Game ≡ pair:G = (K, v) .
Notation (power set).
Ex:
if K = {1, 2}, 2K = ∅, {1}, {2}, {1, 2} .
Transferable utility (TU) games:v : 2K → R.
C 7→ v(C)163

Coalition form games with characteristic functions

Non transferable utility (NTU) games:KK

v: 2 →
R.
C 7→ v(C) = {(v1(C), ..., vK (C))}

164

Ice-cream game example (TU game) → investors...

Chris: $4,
w = 500
p = $7

Marvin: $3,

Terry: $3
w = 750
p = $9• v(Ø) = v({C}) = v({M}) = v({T}) = 0• v({C, M}) = 500, v({C, T}) = 500, v({M, T}) = 0• v({C, M, T}) = 750

165

Ice-cream game example. General solution concept.
Utility division: x = (xC, xM, xT).
• x = (200, 200, 350) not stable (v ({C, M}) > xC + xM).
• x′ = (250, 250, 250) stable.
• x′′ = (750, 0, 0) stable.
Notion of core (TU superadditive games):core(G) =

(

K

x∈R

:

X
i∈K

xi = v(K), ∀C ⊆ K,

X
i∈C

)

xi ≥ v(C) .

166

Ice-cream game core
x1 + x2 + x3





x1




x2



x3

x1 + x2
x1 + x3
x2 + x3
x1 + x2 + x3

=
≥
≥
≥
≥
≥
≥
≥

???
???
???
???
???
???
???
???

167

Ice-cream game core
x1 + x2 + x3





x1




x2



x3

x1 + x2
x1 + x3
x2 + x3
x1 + x2 + x3

=
≥
≥
≥
≥
≥
≥
≥

750
0
0
0
500
500
0
750

168

Core existence: theorems

Theorem (Bondareva-Shapley) Not treated here.
See e.g., [Bacci et al 2016].
Definition (convex TU game)∀C1, C2 ⊆ K, v(C1) + v(C2) ≤ v(C1 ∪ C2) + v(C1 ∩ C2)
Theorem Convex TU game ⇒ non-empty core.

169

The nucleolusCorencore(G) = x ∈ RK :X

xi = v(K), ∀C ⊆ K, v(C) −

i∈K

|

X

o
xi ≤ 0 .

{zi∈C }

e(C,x)

Excess: e(x) = (e(C1, x), ..., e(C2K , x)) (withe(C1, x) ≥ e(C2, x) ≥ ... ).
Nucleolus (relative to X ⊆ RK )nonucleolus(G; X ) = x ∈ X : e(x) L e(x′), ∀x′ ∈ X .
170

The Shapley value

Motivation Stability → fairness
Definition Utility division:
X |C|!(|K| − |C| − 1)!
xi =[v(C ∪ {i}) − v(C)] .
|K|!
C⊆K\{i}171

Axiomatic characterization◮ Efficiency:Xxi = v(K)i∈K◮ Additivity: xi(G1 ⊕ G2) = xi(G1) + xi(G2(⊕ ≡ v = v1 + v2)◮ Dummy: ∀C ′, v(C ′) = v(C ′ ∪ {i}) (C does notcontain i)◮ Symmetry: ∀C ′′, v(C ′′ ∪ {i}) = v(C ′′ ∪ {j}) (Cdoes neither contain i nor j)

172

Coalitional form (NTU)◮ Players: secondary transmitters K = {1, ..., K}.
◮ Characteristic function:v(C) = 1 − Pm(C) − J(Pf (C))
with
J(Pf (C)) =−q 2 log 1 −+∞

Pf (C)q2

if 0 ≤ Pf (C) < q.

if q ≤ Pf (C) ≤ 1

173

Coalition formation

Utility division. Not relevant.
Coalition formation. Merge and split coalitions by performing
Pareto comparisons.
Results. Converging algorithm. Distributed solution:
implementable, good performance in terms of miss and false
alarm probabilities [Saad et al 2011].

174

Solution concepts for coalition form games• core, nucleolus,• ǫ− core,• least core,• kernel,• bargaining set,
• Shapley value, Harsanyi value, Banzhaf index,...

175

Game Theory: Fundamentals and Application to Wirelessand Electricity Networks

5. Extensive form games

176

Extensive form games

Definition: A standard extensive form game is a 6−uplet
G = (K, V, vroot , π, {Vi}i∈K, {ui}i∈K)
where:◮ K = {1, ..., K} is the set of players;◮ (V, vroot , π) is a tree;◮ {Vi}i∈K is a partition of V.
Remark: ∀v ∈ V, ∃n ≥ 1, π (n) = π ◦ ... ◦ π = vroot.

177

Representing the prisoner’s dilemma under extensive
form

!"#$

%$

&$
!"-$

!"#$

%$
'()(*$&$'+),*$%$',)+*$&$'#)#*$

178

Extensive form with imperfect information

Definition: It is a 9−upletj
G = K, V, vroot , π, V0, {q0 }j∈V0 , {Vi}i∈K, {Wik }k∈{1,...,ki}, {ui}i∈K
where:◮ player 0 is nature;◮ ∀j ∈ V0 qj0 is the transition probability used by player 0 tochoose a successor to j;◮ Wik corresponds to the partition of Vi which defines theinformation structure for i.
Remark: Games with perfect information Wik = {wik }.
179

Strategic form and extensive form

• Extensive form more complete than strategic form.
• Extensive form usually less convenient for mathematicalanalysis.
• Continuous/discrete action sets.
• Extensive form sometimes more intuitive.
• The tree structure of the extensive form can be useful forcomputer-based analyses.

180

On the difference between static and dynamic games
Transforming the prisoner’s dilemma into a dynamic game

!"#$

%$

&$
!"-$

!"#$

%$
'()(*$&$'+),*$%$',)+*$&$'#)#*$

181

Game Theory: Fundamentals and Application to Wirelessand Electricity Networks

6. Conclusion

182

Summarizing◮ Direct game theory – mechanism design.
◮ 3 dominant mathematical representations:strategic form, extensive form, coalition form.
◮ Focus on the Nash equilibrium.

183

Summarizing◮ Static games - dynamic games.
◮ Relationship between static games and learning.

184

Challenges◮ Tradeoff between efficiency – weak information assumption.
◮ Bridge the gap between learning and dynamic games.
◮ Dynamic games with arbitrary observation graphs.
◮ Mechanism design.

185

Mechanism design, Nobel prizes,...

186

Game Theory: Fundamentals and Application to Wirelessand Electricity Networks

7. References

187

Quoted references (1)Most quoted references can be found in:Lasaulce and Tembine 2011: Lasaulce, S., & Tembine, H. (2011). Game theory andlearning for wireless networks: fundamentals and applications. Academic Press.

188

Quoted references (2)Knödel 1969: Knödel, W. (1969). Graphentheoretische Methoden und ihre
Anwendungen. Springer-Verlag.
New York Times 1990: Kolata G. What if they closed 42d Street and nobody noticed?
(1990, December). New York Times 1990-12-25.
Cohen and Kelly 1990: Cohen, J. E., & Kelly, F. P. (1990). A paradox of congestion in aqueuing network. Journal of Applied Probability, 730-734.
Perlaza et al 2009: Perlaza, S. M., Belmega, E. V., Lasaulce, S., & Debbah, M. (2009,
October). On the base station selection and base station sharing in self-configuring
networks. In Proceedings of the Fourth International ICST Conference on Performance
Evaluation Methodologies and Tools (p. 71).
Björnson et al 2015: Bjornson, E., Jorswieck, E., Debbah, M., & Ottersten, B. (2014).
Multiobjective Signal Processing Optimization: The way to balance conflicting metrics in
5G systems. Signal Processing Magazine, IEEE, 31(6), 14-23.
Bacci et al 2015: Bacci, G., Lasaulce, S., Saad, W., & Sanguinetti, L. (2015). Game
Theory for Signal Processing in Networks. arXiv preprint arXiv:1506.00982.

189

Quoted references (3)Cournot 1838: Cournot, A. A. (1838). Recherches sur les principes mathmatiques de lathorie des richesses par Augustin Cournot. chez L. Hachette.
Nash 1950: Nash, J. F. (1950). Equilibrium points in n-person games. Proc. Nat. Acad.
Sci. USA, 36(1), 48-49.
Kuhn 1953: Kuhn, H. W. (1953). Extensive games and the problem of information.
Contributions to the Theory of Games, 2(28), 193-216.
Glicksberg 1952: Glicksberg, I. L. (1952). A further generalization of the Kakutani fixed
point theorem, with application to Nash equilibrium points. Proceedings of the American
Mathematical Society, 3(1), 170-174.
Debreu 1952: Debreu, G. (1952). A social equilibrium existence theorem. Proceedings of
the National Academy of Sciences of the United States of America, 38(10), 886.
Fan 1952: Fan, K. (1952). Fixed-point and minimax theorems in locally convex topologicallinear spaces. Proceedings of the National Academy of Sciences of the United States ofAmerica, 38(2), 121.

190

Quoted references (4)Rosen 1965: Rosen, J. B. (1965). Existence and uniqueness of equilibrium points forconcave n-person games. Econometrica: Journal of the Econometric Society, 520-534.
Yates 1995: Yates, R. D. (1995). A framework for uplink power control in cellular radio
systems. Selected Areas in Communications, IEEE Journal on, 13(7), 1341-1347.
Perlaza & Lasaulce 2014: Perlaza, S. M., & Lasaulce, S. (2014). Game-Theoretic
Solution Concepts and Learning Algorithms. Mechanisms and Games for Dynamic
Spectrum Allocation, 185-221.
Yates 1995: Yates, R. D. (1995). A framework for uplink power control in cellular radio
systems. Selected Areas in Communications, IEEE Journal on, 13(7), 1341-1347.
Papadimitriou 2001: Papadimitriou, C. (2001, July). Algorithms, games, and the internet.
In Proceedings of the thirty-third annual ACM symposium on Theory of computing (pp.
749-753). ACM.

191

Quoted references (5)Anshelevich 2014: Anshelevich, E., Dasgupta, A., Kleinberg, J., Tardos, E., Wexler, T., &Roughgarden, T. (2004). The price of stability for network design with selfish agents. In
IEEE Symposium on Foundations of Computer Science (pp. 295-304).
Correa et al 2005: Correa, J. R., Schulz, A. S., & Stier-Moses, N. E. (2005). On theinefficiency of equilibria in congestion games. In Integer Programming and Combinatorial
Optimization (pp. 167-181). Springer Berlin Heidelberg.
Larsson & Jorswieck 2008: Larsson, E. G., & Jorswieck, E. (2008). Competition versus
cooperation on the MISO interference channel. Selected Areas in Communications, IEEE
Journal on, 26(7), 1059-1069.
Yu et al 2002: Yu, W., Ginis, G., & Cioffi, J. M. (2002). Distributed multiuser power control
for digital subscriber lines. Selected Areas in Communications, IEEE Journal on, 20(5),1105-1115.

192

Quoted references (6)Brown 1951: Brown, G. W. (1951). Iterative solution of games by fictitious play. Activity
analysis of production and allocation, 13(1), 374-376.
Bush & Mosteller 1955: Bush, R. R., & Mosteller, F. (1955). Stochastic models forlearning.
Sastry et al 1994: Sastry, P. S., Phansalkar, V. V., & Thathachar, M. (1994). Decentralized
learning of Nash equilibria in multi-person stochastic games with incomplete information.
Systems, Man and Cybernetics, IEEE Transactions on, 24(5), 769-777.
Monderer & Shapley 1996: Monderer, D., & Shapley, L. S. (1996). Potential games.
Games and economic behavior, 14(1), 124-143.
Yao 1995: Yao, D. D. (1995). S-modular games, with queueing applications. Queueing
Systems, 21(3-4), 449-475.
Saraydar 2002: Saraydar, C. U., Mandayam, N. B., & Goodman, D. J. (2002). Efficient
power control via pricing in wireless data networks. Communications, IEEE Transactions
on, 50(2), 291-303.

193

Quoted references (7)Hart and Mas-Collel & 2000: Hart, S., & Mas-Collel, A. N. D. R. E. U. (2000). A simple
adaptive procedure leading to correlated equilibrium. Econometrica, 68(5), 1127-1150.
Mochaourab & Jorswieck 2009: Mochaourab, R., & Jorswieck, E. (2009, October).
Resource allocation in protected and shared bands: uniqueness and efficiency of Nashequilibria. In Proceedings of the Fourth International ICST Conference on Performance
Evaluation Methodologies and Tools (p. 68).
Renault & Tomala 1998: Renault, J., & Tomala, T. (1998). Repeated proximity games.
International Journal of Game Theory, 27(4), 539-559.
Goodman & Mandayam 2000: Goodman, D., & Mandayam, N. (2000). Power control for
wireless data. Personal Communications, IEEE, 7(2), 48-54.
Le Treust & Lasaulce 2010: Le Treust, M., & Lasaulce, S. (2010). A repeated gameformulation of energy-efficient decentralized power control. Wireless Communications,
IEEE Transactions on, 9(9), 2860-2869.
Mériaux et al 2011: Mériaux, F., Le Treust, M., Lasaulce, S., & Kieffer, M. (2011, July). A
stochastic game formulation of energy-efficient power control: Equilibrium utilities andpractical strategies. In Digital Signal Processing (DSP), 2011 17th International
Conference on (pp. 1-6). IEEE.
194

Quoted references (8)Larrousse and Lasaulce 2015: B. Larrousse and S. Lasaulce, ”Coded Power Control:
Performance Analysis”, IEEE Intl. Symposium on Information Theory (ISIT), Istanbul,
Turkey, Jul. 2013.
Larrousse et al 2015: Larrousse, B., Lasaulce, S. & Wigger, M. (2015, May).
Coordination in State-Dependent Distributed Networks. In Information Theory Workshop(ITW). (pp. 1-5). IEEE.
Larrousse et al 2018: B. Larrousse, S. Lasaulce, and M. Bloch, Coordination in
distributed networks via coded actions with application to power control, IEEE
Transactions on Information Theory, Vol. 64, No. 5, pp. 3633-3654, 2018.
Gossner et al 2006: O. Gossner, P. Hernández, and A. Neyman, “Optimal use ofcommunication resources”, Econometrica, Vol.74, No.6, pp. 1603-1636, 2006.
Agrawal et al 2015: Agrawal, A., Lasaulce, S. & Visoz, R. (2015, November). A
framework for decentralized power control with partial channel state information. In
Communications and Networking (ComNet), 2015 4th International Conference on (pp.
1-6). IEEE.
Aumann & Maschler 1985: Aumann, R. J., & Maschler, M. (1985). Game theoretic
analysis of a bankruptcy problem from the Talmud. Journal of economic Theory, 36(2),
195-213.
195

Quoted references (9)[Aumann and Maschler 1985] Aumann, R.J., Maschler, M., 1985. Game theoretic analysis
of a bankruptcy problem from the Talmud. J. Econ. Theory, 36, 195213.
Saad et al 2011: Saad, W., Han, Z., Başar, T., Debbah, M., & Hjørungnes, A. (2011).
Coalition formation games for collaborative spectrum sensing. Vehicular Technology, IEEE
Transactions on, 60(1), 276-297.
[Gonzalez et al Gretsi 2017] M. Gonzalez, O. Beaude, P. Bouyer, S. Lasaulce, and N.
Markey, ”Stratgies dordonnancement de consommation dnergie en prsence dinformation
imparfaite de prvision”, Gretsi conference, Juan-les-Pins, France, Sep. 2017.
[Gonzalez et al TSG 2018] M. Gonzalez, O. Beaude, P. Bouyer, S. Lasaulce, and N.
Markey, ”Dynamic load scheduling under uncertainty”, IEEE Trans. on Smart Grid,
submitted.
[Bacci et al 2016] G. Bacci, S. Lasaulce, W. Saad, and L. Sanguinetti, ”Game theory andits applications in signal processing”, IEEE Signal Processing Magazine, Vol. 33, No. 1,
pp. 94–119, Jan. 2016.
G. Bacci, S. Lasaulce, W. Saad, and L. Sanguinetti, ”Game theory and its applications insignal processing”, IEEE Signal Processing Magazine, Vol. 33, No. 1, pp. 94–119, Jan.
2016.
196

Quoted references (10)[Beaude et al ECC 2015] O. Beaude, S. Lasaulce, M. Hennebel, and J. Daafouz,”Minimizing the impact of EV charging on the distribution network”, European Conference
on Control (ECC), Linz, Austria, July 2015.
[Beaude et al TSG 2016] O. Beaude, S. Lasaulce, M. Hennebel, and I. Mohand-Kaci,”Reducing the impact of distributed EV charging on distribution network operating costs”,
IEEE Transactions on Smart Grid, Vol. 7, No.6, pp. 2666–2679, 2016.
[Paccagnan et al L-CSS 2018] D. Paccagnan, F. Parise, and J. Lygeros, ”On the Efficiency
of Nash Equilibria in Aggregative Charging Games”, IEEE L-CSS, 2018.
[Perlaza et al 2013] S. M. Perlaza, S. Lasaulce, and M. Debbah, ”Equilibria of Channel
Selection Games in Parallel Multiple Access Channels”, EURASIP Journal on WirelessCommunications and Networking (JWCN), Jan. 2013.
[Sastry et al 1994] Sastry, P.S., Phansalkar, V.V., Thatchar, M.A.L., 1994. Decentralized
learning of Nash equilibria in multi-person stochastic games with incomplete information.
IEEE Trans. Syst. Man Cybern. 24, 769777.

197