Quelques apports de la théorie des jeux à l'utilisation

Quelques apports de la theorie des jeux al’utilisation des reseaux de communication

Un focus sur les jeux de congestion

Corinne Touati

Mines de Saint Etienne, 23 novembre 2015

Pourquoi la theorie des jeux dans les reseaux de

communication?

(http://www.ccri.uottawa.ca/IRCS/Contact.fr.html)

I Automatisation dans lesannees 70

I Evolution vers les paquetsde donnees (datagrampacket switching)

I Experience del’e↵ondrement decongestion dans lesannees 80 (RFC 896)

C. Touati (INRIA) Theorie des jeux en telecom Introduction 2 / 27

http://www.ccri.uottawa.ca/IRCS/Contact.fr.html

http://www.ccri.uottawa.ca/IRCS/Contact.fr.html

L’equite dans le controle de congestion

Equite de Thomson, Rai↵a-Kalai-Smorodinsky, Nash notamment

Axes de recherche:I Implementation (algorithmes primal / dual - descentes de

gradient)I DimensionementI Prediction de situations (d’un melange de protocols - theorie

des jeux evolutionnaires)

Milano

Copenhagen

Vienna

Prague

BerlinAmsterdam

Luxembourg

Paris

London

Zurich

Brussels

80

2520

...

Paris−Vienna

55.06

19.46

25.48

London−Vienna

Zurich−Vienna


L’equite dans le controle de congestion

Equite de Thomson, Rai↵a-Kalai-Smorodinsky, Nash notammentAxes de recherche:

I Implementation (algorithmes primal / dual - descentes degradient)

I DimensionementI Prediction de situations (d’un melange de protocols - theorie

des jeux evolutionnaires)

Milano

Copenhagen

Vienna

Prague

BerlinAmsterdam

Luxembourg

Paris

London

Zurich

Brussels

80

2520

...

Paris−Vienna

55.06

19.46

25.48

London−Vienna

Zurich−Vienna


Illustration: Prediction

Question: Quelle est l’e�cacite du point solution?


Illustration: Implementation de Solutions

Question: Comment creer des systemes e�caces?


Jeux de Potentiel

Definition: Jeu de potentiel.

Un jeu dans lequel toutes les utilites individuelles derivent d’unememe fonction.

Definition:Jeu de potentiel (exact) (Monderer & Shapley, 96).

Soit un jeu (N ,S,U). Le jeu a un potentiel f : S 7! R si:8n 2 N, 8s 2 S, 8a 2 Sn :

un(s)� un(a, s�n) = f(s)� f(a, s�n)

Di↵ utilites individuelles Di↵ de potentiel

Lien avec les equilibres de Nash

Les optima du potentiel f sont les equilibres de Nash du jeu.

C. Touati (INRIA) Theorie des jeux en telecom A Specific Class of Games 6 / 27

Quels jeux admettent une fonction de potentiel?

Definition: Les jeux de congestion.

Considerons:

I Un ensemble fini de joueurs N , ensemble fini de ressources R.

I Chaque action est le choix d’un ensemble de ressources:Sn ⇢ P (R)

I L’utilite d’une ressource ne depend que du nombre de joueursqui y accede: cr(s) = cr(card(n|r 2 sn))

I Utilite d’une action: ca =

X

r2acr.

Theorem.

Les jeux de congestion avec des utilites decroissantes sont des jeuxde potentiel exact.

Exemples typiques: problemes d’allocation de ressources avec desjoueurs identiques.


Exemple de Jeu de Congestion: Jeu de Routage Fini

Hypothese

Les joueurs ont des poids identiques) charge `r = nombre de joueurs sur le lien r.

A B

b

a

c

Jeu de routage

I Cout d’un lien cr(`r)

I Cout d’un chemin cp(`)=X

p3rcr(`r)

(Hypothese: pas de cycle)Jeu de congestion avec:

I ressource = lien

I action = cheminTheorem.

Ces jeux de routage ont un potentiel exact:

C(s) =

X

lien r

`r(s)X

i=1

cr(i)


Consequences de l’ine�cacite: Paradoxe de Braess

Considerons un total de 4000 joueurs, allant de A a B.

A B

b

a

45 N/100

45N/100

A B

b

a

c

45 N/100

45N/100

0


New York Times, Dec 25, 1990, Page 38, What if They Closed 42dStreet and Nobody Noticed?, par GINA KOLATA:

“ ON Earth Day this year, New York City’s TransportationCommissioner decided to close 42d Street, which as every NewYorker knows is always congested. ”Many predicted it would bedoomsday,” said the Commissioner, Lucius J. Riccio. ”You didn’tneed to be a rocket scientist or have a sophisticated computerqueuing model to see that this could have been a major problem.”But to everyone’s surprise, Earth Day generated no historic tra�cjam. Tra�c flow actually improved when 42d Street was closed. “


Topologie en Triangle

Peut modeliser des situationsde:

I Accords de routageinter-domaines

I Collusions entre desfournisseurs de contenuset de services

N N

C

A B

Figure: Un systeme ”en triangle”

Eitan Altman, Corinne Touati, “Load Balancing Congestion Games and their

Asymptotic Behavior” (submitted).


Liens paralleles

Peut modeliser descompetitions entre reseauxsociaux (dans quel reseauinvestir)

`2

`1

`L

s d

•••

Figure: Un systeme a liensparalleles

Nof Abuzainab, Eitan Altman, Fabrice Lebeau, Corinne Touati, “The Social

Medium Selection Game” (submitted).

Eitan Altman, Li Jie, Corinne Touati, “Resilience of Routing in Parallel link

networks” (submitted).


Une remarque sur la convexite dans les systemes discrets

Pas de definition unique: Multi-modularite, M-convexite,L-convexite

Definition: M-concavity (Murota, 1996).

Une fonction f : ZJ ! R est M-concave si pour tout ~x, ~y dans Det pour tout u 2 supp

+(~x� ~y):

9v 2 supp

+(~y � ~x),

f(~x) + f(~y) f(~x� ~eu + ~ev) + f(~y � ~ev + ~eu).

Figure: M-concavity


Une remarque sur la convexite dans les systemes discrets

Pas de definition unique: Multi-modularite, M-convexite,L-convexite

Definition: M-concavity (Murota, 1996).

Une fonction f : ZJ ! R est M-concave si pour tout ~x, ~y dans Det pour tout u 2 supp

+(~x� ~y):

9v 2 supp

+(~y � ~x),

f(~x) + f(~y) f(~x� ~eu + ~ev) + f(~y � ~ev + ~eu).

Theorem: Global Optima (Murota, 1996).

If g is M-concave and ~x 2 dom g then:~x 2 argmax g , 8u, v, g(~x) � g(~x� ~eu + ~ev)

Besides, M-concavity allows to have e�cient algorithms for findinga Nash equilibrium.


Une remarque sur le trafic ”splittable”

N N

C

A B

Figure: Un reseau simple

Que dire si chaque joueur peut diviserson trafic entre les di↵erentes routes?) PLUS un jeu de potentiel (engeneral)

Que dire si chaque joueur a un ensem-ble d’elements non-splitables dans sontrafic?) trafic semi-splitableExemple: Connexions TCP multiples,taches d’applications dans les desktopgrids


Exemple: Le probleme d’association optimal

Contexte

I Les cellules de di↵erentes technologies se recouvrent (LTE,WiFi, WiMax, etc)

I Les mobiles sont compatibles avec plusieurs technologiesI Protocoles:

I Multi-homing: plusieurs connexions actives en meme tempsI Vertical Handover: on passe d’une technologie a une autre

But

Trouver un algorithme d’association entre les mobiles et lesantennes qui soit:

I distribue

I optimal

Pierre Coucheney, Corinne Touati, Bruno Gaujal: Fair and E�cient

User-Network Association Algorithm for Multi-Technology Wireless Networks,

INFOCOM 2009C. Touati (INRIA) Theorie des jeux en telecom A Specific Class of Games 15 / 27





Methode:

I Introduire un jeu de potentiel

I Concevoir une decente de gradientsur le ”replicator dynamics”:@qi,ai

@t

= qi,ai(fi,ai(Q)� fi(Q))


0

0.5

1

0 0.5 1

Formation de Coalition dans la radio cognitive

I cooperation entre noeuds secondaires dans les reseaux deradion cognitive

I Travaux initiaux: ”sensing” et acces collaboratif

I Plus recemments: utilisateurs secondaires cooperent avec lesutilisateurs primaires

Notre proposition:

I des utilisateurs primaires multiples et des utilisateurssecondaires multiples.

I les utilisateurs secondaires utilisent le ”sequential relaying”

I formulation en tant que jeu de formation de coalition etetablissement d’un parallele avec les jeux de potentiels.

Nof Abuzainab, Sai Rakshit Vinnakota, Corinne Touati, “Coalition formation

game for cooperative cognitive radio using Gibbs Sampling”. WCNC 2015:

937-942


System Model

Scenario:

I lien descendant

I Utilisateurs primaires P, utilisateurs secondaires: S

I Besoin en debit fixe: Rp bits/sec over [0, T ] pour les UP p

I |P| orthogonal frequency channels (Rayleigh fading,independant, additive white Gaussian noise of variance N0).

I Pour chaque UP p, on definit l’ensemble CP d’utilisateurssecondaires qui servent p.

Deux phases dans l’intervalle de temps [0, T ]:

1 Phase de cooperation: Pendant la fraction ↵P de T , les US deCP assistent p.

2 Phase de transmission des US: Pendant la fraction 1� ↵P deT , les US de CP se partagent le canal de p pour leur proprestransmissions.


Phase de cooperation

Une coalition d’US P est un triplet (CP,�P, tP),

I tP est le vecteur de fractions de temps tP = (t

P0 , . . . , t

PCP)

>

I tP > 0 et t>P .1 = 1.

I Pendant la fraction de temps tP0 , la station transmet aupremier US �P(1). Puis, �P(1) decode pendant que les autresUS et le PU enregistrent l’information recue.

I Durant tPk , US �P(k) transmet a l’US �P(k + 1) qui decodependant que les US suivants et l’UP enregistrent la nouvelleinformation recue.

I Durant tPCP , US �P(CP) transmet a l’UP p, qui decode lemessage.


La phase de transmission des US

I On utilise le multiplexage temporel.

I Le temps de transmission est proportionnel a la quantited’energie depensee par l’US pour aider l’UP dans la phase decooperation.

uk(P) = (1� ↵P(P))tPkLB,k.


Jeu de Formation de coalition

I Comme chaque US est devoue a assister un seul UP, les USsont partitionnes en ensembles disjoints. Alors, chaque groupeassistant un UP est considere comme une coalition, et legroupe des US est ”mapped” a une partition de coalition.

I La valeur V de la coalition P est la somme des utilites dechacun de ses membres pour sa propre transmission:

V (P) =X

k2Puk(P) = (1� ↵P(P))

X

k2Pt

PkLB,k.


Jeu de Formation de coalition

Definition: Coalitional Allocation Game

A coalition game satisfying:

1 Given number of coalitions A

2 Coalitions indexed by parameter a, 1 a A.

3 The value of each coalition only depends on parameter a andthe set of members of the coalition Ca.

Note that allocation coalition games are not in characteristic form.

Proposition: repercussion utilities

Suppose that the advertised utility for player k when in coalition a

is: rk(Ca) = uk(Ca)�X

j2Ca,j 6=k

⇣uj(Ca\{k})� uj(Ca)

⌘.

Then, the set of stable coalition partitions CS

⇤ are the maximizersof the social welfare: W (CS

⇤) = max

CS

X

a

V (Ca).


Conclusion

La theorie des jeux est un outil naturel pour:

I Modeliser les situations de competition / cooperation dans unlarge ensemble de reseaux de communications

I Concevoir des systemes dans lesquels les equilibres de Nashsont e�caces

I Concevoir des methodes pour calculer les equilibres de NashI Algorithmes derives du best responseI Dynamiques des jeux evolutionnaires et les approximations

stochastiquesI Le ”machine learning” ou l’apprentissage automatique...

C. Touati (INRIA) Theorie des jeux en telecom Specific Topology Structure 26 / 27

C. Touati (INRIA) Theorie des jeux en telecom Specific Topology Structure 27 / 27

Documents

Quelques apports de la théorie des jeux à l'utilisation