Mieux comprendre la Game Theory

• 06 septembre 2016
• Barth_Gury
• 5247
•  PA  1
• 34 Commentaires

La Game Theory (ou théorie des jeux en français) est un ensemble d'outils qui permet de définir une action optimale à un moment donné. Longtemps utilisé en économie, en science politique ou encore en biologie, elle a pris une place importante dans le milieu du poker ces dernières années. Youstiti vous la présente dans ses grandes largeurs. 

 

Youstiti a participé à la promotion meilleur article du mois, et a remporté le second prix pour 400 PPA

• Découvrez la promotion meilleur article du mois

Introduction : Pourquoi cet article ?

Cet article se donne pour but de fournir un cadre de compréhension général de la théorie des jeux, afin de donner la possibilité aux joueurs de poker de mieux comprendre la théorie des jeux dans le cadre du poker. 

La théorie des jeux est un domaine très vaste, je ne me donne pas pour objectif de couvrir son ensemble, ma contribution sera modeste, et ne couvrira qu'une infime partie de ce qui pourrait se faire. Le but sera de permettre d'acquérir des bases de raisonnement, pour avoir un peu moins l'impression de patauger dans la semoule quand on lit un article de game theory appliquée au poker.

En effet, en lisant des articles orientés game theory, on peut vite se perdre avec les différentes notions, surtout si l'on n'a pas de background mathématiques. J'ai la chance d'avoir eu des cours de théorie des jeux dans mon cursus, et je vais vous proposer de partager avec vous une partie de ce que j'en ai retenu, de façon à vous améliorer sur ce domaine.

 

Partie I : Définitions et concepts de base

Je vais proposer quelques définitions, pour que nous soyons d'accord sur le vocabulaire utilisé par la suite. J'espère que ça sera lisible même si on n'a pas fait de maths. Cette partie pourra être survolée si l'on sent que l'on s'y perd, les exemples plus concrets arriveront ensuite. Je conseille par ailleurs de la survoler en première lecture et d'y revenir ensuite au besoin. J'ai décidé d'omettre volontairement certains résultats que je jugeais trop complexes (théorème de Glicksberg par exemple), et de simplifier certaines notations. De plus, j'ai également décidé, de présenter la théorie et les définitions en premier lieu, d'un trait, et les exemples ensuite. Si vous voyez que vous décrochez, n'hésitez vraiment pas à commencer par les exemples et à revenir sur la théorie au besoin, quand vous vous poserez une question , j'ai voulu faire en sorte de faire l'article assez complet, quitte à perdre un peu en lisibilité.

Un jeu :
Un jeu est la donnée d'un triplet G=(N,(Ai)i∈N,(gi)i∈N) avec
- N : l'ensemble des joueurs
- Pour tout i dans N, Ai l'ensemble des stratégies du joueur i.
- Pour tout i dans N, gi le paiement du joueur i.

Le jeu est fini si N est fini, et pour tout i dans N, Ai est fini.

 

Stratégie dominante :
Notation préalable :
On pose A-i l'ensemble des stratégies (Ai)i∈N privé de l'ensemble Ai
Une stratégie est dite dominante si ∀ a-i∈A-i, ∀ bi∈Ai, on a gi(ai,a-i) ≥gi(bi,a-i)
En français : une stratégie dominante pour le joueur i lui assure un paiement associé supérieur ou égal à toutes les autres stratégies dont il dispose.

 

Equilibre de Nash (noté E.N. par la suite) :
Soit G=(N,A=(Ai)i∈N,(gi)i∈N) un jeu.
Un vecteur a=(ai)i∈N ∈A est un E.N. si ∀ i∈N, ∀ bi∈Ai, on a gi(ai,a-i) ≥gi(bi,a-i)

 

Autre définition de l'E.N. : (celle que l'on utilisera par simplicité) :
Un E.N. est un contrat dont personne n'a intérêt de dévier.
Autrement dit, si un joueur décide de changer sa stratégie lorsqu'on est en situation d'E.N., il va forcément s'en retrouver perdant par rapport à avant.

Remarque : lien entre stratégie dominante et E.N.
Un vecteur a=(ai)i∈N où tous les ai sont dominants est appelé un équilibre en stratégie dominante. Un équilibre en stratégie dominante est un E.N.

Stratégie pure, stratégie mixte :
Afin de ne pas alourdir l'article de notations, et décourager le lecteur, je vous propose les définitions suivantes, qui manquent cependant un peu de rigueur :

On parle de stratégie mixte, lorsque le joueur a la possibilité de pondérer l'ensemble de ses stratégies. Par exemple, jouer 1/3 du temps pierre, 1/3 du temps feuille et 1/3 du temps ciseau au chifoumi est une stratégie mixte. 

L'ensemble des stratégies mixtes, noté Δ(A) est l'ensemble des stratégies probabilisé. A l'inverse, l'ensemble des éléments de A sont les stratégies pures. Toute stratégie pure est également une stratégie mixte.

 

Jeu à somme nulle :
Soit G=(N,A=(Ai)i∈N,(gi)i∈N) un jeu.
Il est à somme nulle, si ∑ gi=0
Autrement dit, pour un jeu à deux joueurs par exemple, on aura :
N=1,2
g1=-g2
Autrement dit, ce que gagne l'un, l'autre le perd.

 

Notation dans le cadre des jeux à somme nulle :
Un jeu à somme nulle à deux joueurs, peut être résumé par Γ=(S,T,g) avec S l'ensemble des stratégies du joueur 1, T celles du joueur 2, et g la fonction du paiement du joueur 1.
On a vu que g1=-g2 autrement dit, le joueur 1 veut maximiser g, et le joueur 2 le minimiser.
Si Γ est fini, on peut également représenter le jeu par la matrice A=(g(s,t))s∈S,t∈T

 

Notion de valeur d'un jeu à somme nulle :
Il s'agit d'une notion importante à comprendre, je pense. Je vais essayer de l'expliquer tout en la définissant :
Soit Γ=(S,T,g) un jeu à somme nulle.
Notons v_- la valeur inférieure du jeu, définie par v_-= Sups∈S Inf t∈T g(s,t)
Notons v_+ la valeur supérieure du jeu, définie par v_+= Inft∈T Sup s∈S g(s,t)
Qu'est ce que cela signifie en pratique ?
v_- est l'issue du jeu si les deux joueurs sont rationnels (ie jouent de façon optimale), et que le joueur 1 joue en premier (il est donc désavantagé).
v_+ est l'issue du jeu, quand le joueur 1 joue en deuxième, si les deux joueurs jouent rationnellement.
A noter :
v_+, et v_- sont les paiement obtenus par le joueur 1.
v_+ ≥ v_-.

 

Un petit exemple pour mieux comprendre :
Je sais que je ne devais pas commencer les exemples ici, mais je pense que c'est quand même utile de comprendre cette notion de valeur.
Soit le jeu suivant :
Deux joueurs doivent choisir entre dire pile ou dire face (on ne lance à aucun moment une pièce).
Si les deux disent la même chose, le joueur 1 gagne, sinon c'est le joueur 2 qui gagne.
On a donc comme fonction de paiement :
g(P,P)=g(F,F)=1
g(P,F)=g(F,P)=-1
J1 veut maximiser g, et J2 le minimiser.
On a :
v_- = Sups∈S Inf t∈T g(s,t)= Sups∈S(-1,-1)=-1
Et en français : J1 joue en premier, quel que soit son choix, on voit que si J2 est rationnel il va jouer l'autre choix, et obtenir un paiement de 1 (pourJ2), et un paiement de -1 pour J1.
De même v_+=1

 

Notion de valeur du jeu :
On dit que le jeu a une valeur si v_+=v_-, on note v=v_+=v_- la valeur du jeu.
Important :
Si Γ a une valeur. Alors une stratégie s∈S est optimale pour J1 si pour tout t∈T, g(s,t)≥v.
Autrement dit, une stratégie est optimale pour J1 si elle lui garantit d'obtenir au moins la valeur du jeu quelque soit la stratégie adverse.
C'est un concept important, que l'on retrouvera pas mal au poker.
Autre point important (assez logique quand on y réfléchit):
Soit Γ un jeu à somme nulle :
1) S'il existe (s,t) un E.N., le jeu a une valeur, et on a v=g(s,t)
2) Si le jeu admet une valeur v, et deux stratégies optimales s et t, alors (s,t) est un E.N.

Ce sont des points importants que je vous invite à relire, car ils sont très importants à comprendre pour les applications que l'on peut en faire au niveau du poker. 

 

Exemples concrets de la théorie des jeux :

Mieux comprendre la notion d'E.N. avec des exemples simples
N.B : cette partie s'adresse avant tout à des débutants, pour mieux comprendre la notion d'E.N. en stratégie pure notamment.

 

Exemple 1 : Stratégie pure

Je m'excuse par avance de la naïveté de ce premier exemple, mais après toute cette théorie, ça ne fera pas de mal .
Considérons deux automobilistes sur une route. L'un allant de A à B, et l'autre de B à A.
Ils ont tous les deux deux stratégies possibles : rouler à droite (D), rouler à gauche (G).
On considère la fonction de paiement suivante :

g(D,D)=g(G,G)=(1,1)

Ils roulent tous les deux du même côté et n'ont pas d'accident, ils sont contents .

g(G,D)=g(D,G)=(-10,-10)
Ils roulent de côtés différents, et vont avoir un accident -> pas content -10. N.B : ce choix de paiement est arbitraire.
N.B : également, notez que l'on pourrait proposer d'autres matrices de paiement, par exemple joueur 1 roule en lamborghini et tient à sa voiture comme à la prunelle de ses yeux, joueur 2 roule en 206, on pourrait alors avoir g(G,D)=g(D,G)=(-100,-10).

On voit rapidement ici, dans cet exemple un peu simpliste, qu'il existe deux E.N, à savoir (G,G), (D,D).
Avec la définition que nous avons donné plus haut : "Un E.N. est un contrat dont personne n'a intérêt de dévier.", il est clair que si le joueur 1 décide de dévier de sa stratégie lorsque l'on est à l'E.N., il va être perdant (obtenir -10 au lieu de 1). De même J2 n'a pas intérêt de dévier de sa stratégie à l'équilibre.
On comprend bien dans cet exemple, qu'à l'E.N., aucun des deux joueurs n'a de marge de manœuvre pour changer de stratégie.

 

Exemple 2 et 3 : stratégie dominante, E.N. 

Exemple 2 : le dilemme du prisonnier (un classique) :
Soit le jeu suivant :
On a deux prisonniers, qui peuvent soit dénoncer l'autre (D) soit se taire (T).
Si les deux se taisent ils ressortent libres.
Si J1 se tait, et J2 le dénonce, J1 a 10 ans de prison, et J2 a 1000€ de récompense.
Si J2 se tait, et J1 le dénonce, J2 a 10 ans de prison, et J1 a 1000€ de récompense.
Si J1 et J2 se dénoncent mutuellement ils ont 5 ans de prisons.
Considérons la fonction de paiement suivante :
g(T,T)=(0,0) -> tous les deux libres
g(D,T)=(1,-10) -> J1 reçoit 1000€, J2 10 ans de prison
g(T,D)=(-10,1) -> J2 reçoit 1000€, J1 10 ans de prison
g(D,D)=(-5,-5) -> J1 et J2 ont 5ans de prison.

Je vais profiter de cet exemple, et de celui qui va suivre pour parler de stratégie dominante.
On voit assez rapidement que D est un stratégie dominante. En effet, intéressons nous au paiement du joueur 1 :
Pour que D soit une stratégie dominante, on a vu qu'il faut :
g1(D,D)≥g1(T,D) et g1(D,T)≥g1(T,T) où g1 est le paiement du J1.

On calcule et on a bien le résultat souhaité :
g1(D,D)=-5≥-10=g1(T,D) et g1(D,T)=1≥0=g1(T,T)
De même on peut montrer que D est une stratégie dominante pour J2.
On a également vu précédemment qu'un équilibre en stratégie dominante est un E.N., donc (D,D) est un E.N. (c'est assez clair)
Ce qu'il est intéressant de remarquer est qu'à l'E.N., les deux joueurs sont perdants, alors qu'ils pourraient être potentiellement tous les deux à 0.

-> Y a-t-il d'autres E.N. ?
Je ne vais pas m'intéresser aux stratégies, (T,D) et (D,T), on peut se convaincre assez rapidement qu'il ne s'agit pas d'E.N., mais on pourrait se poser légitimement la question de savoir si (T,T) est un E.N. ?
Eh bien non !
Rappelez vous : "Un E.N. est un contrat dont personne n'a intérêt de dévier.".
On voit donc que (T,T), ne peut être un E.N., car J1 peut dévier de sa stratégie profitablement.
En effet, en jouant D, il obtiendra alors 1000€ de récompense.

A l'inverse, on voit que (D,D) est bien un E.N. : si J1 décide de dévier de sa stratégie, il va être perdant, puisqu'il aura 10 ans de prison au lieu de 5 !

 

Exemple 3 : stratégie dominante et E.N. : la bataille des sexes
Cet exemple sert à illustrer le fait qu'on peut avoir des E.N. sans nécessairement avoir de stratégie dominante.
Considérons un couple, ils veulent savoir quoi regarder à la télé, un match de foot (M) ou un film romantique (F). S'ils ne sont pas d'accords, ils ne regardent rien, et sont tous les deux tristes.
S'ils jouent (F,F) J1 est très content, et J2 content mais un peu moins. Et à l'inverse s'ils jouent (M,M), J2 est très content, et J1 un peu moins.
Soit donc la fonction de paiement associée g:
g(F,F)=(3,1)
g(M,M)=(1,3)
g(M,F)=g(F,M)=(-1,-1)

On peut se convaincre assez rapidement qu'il n'y a pas de stratégie dominante. On peut se rappeler l'exemple précédent, et voir que là en effet, on n'a pas forcément mieux de façon systématique si on joue F ou M.
En revanche on voit qu'il y a deux E.N (c'est également assez clair), à savoir (F,F) et (M,M).
En effet, montrons que (F,F) est un E.N. : si J1 change de stratégie on voit qu'il a moins bien, puisque (F,F) lui donne un paiement de 3, alors que (M,F) lui donnera -1. De même si J2 change sa stratégie, il obtiendra -1 avec (F,M), alors qu'il obtenait 1 avec (F,F). Donc aucun des deux n'a intérêt de dévier de sa stratégie actuelle.

 

E.N en stratégie mixte, notion d'indifférence

 

Allez on s'attaque à quelque chose qui nous intéresse un peu plus, le jeu en stratégie mixte !
Les E.N. de Nash en stratégie pure, ça reste assez simple, mais en pratique, on le sait, en stratégie mixte, ça se complique ! On va également s'intéresser au principe d'indifférence dont on entend si souvent parler au poker

On va reprendre l'exemple de la guerre des sexes, avec J1, J2 qui peuvent choisir F ou M (match ou film).
On va légèrement changer la fonction de paiement :
g(F,F) =(3,1) -> J1 très content, J2 ça va
g(M,F)=g(F,M)=(-1,-2) -> J1 et J2 mécontents, mais J2 davantage, il avait vraiment envie de regarder la télé !
g(M,M)=(0,3) -> J1 neutre, J2 très content.

Note importante : on considère que les joueurs ont une stratégie déterminée au départ (par exemple jouer M, jouer F, jouer x% du temps M et le reste du temps F), et ne changent donc pas de stratégie en cours de route (sinon il y aurait une notion de qui joue le 1er, qui joue le 2eme, etc, et le 2eme pourrait simplement jouer la même chose que le 1er...).

On voit rapidement que (M,M) et (F,F) sont les deux E.N., je ne vais pas le redémontrer, mais c'est similaire à l'exemple précédent.
Ce qui va nous intéresser à présent, c'est de nous pencher sur les stratégies des joueurs, notamment aux stratégies mixtes, et voir comment arriver à ces équilibres de Nash, mais aussi comment adapter sa stratégie en fonction de la stratégie adverse... Par exemple :

Imaginons, que J1 soit très borné, et joue 100% du temps M, il est clair, que notre stratégie doit être également de jouer 100% M, sans quoi on va être perdant.
Mais si J1 est quelqu'un de raisonné, et qu'il joue 50% du temps M, et 50% du temps F, quelle stratégie adopter ?
De même s'il joue 70% du temps M et 30% du temps F ? On fait quoi nous !? C'est quoi le mieux ?
Là on voit qu'on est dans un cadre assez proche du poker avec les stratégies mixtes.

Alors, l'exemple n'étant pas forcément simple, je vais prendre le temps de détailler un peu le raisonnement que nous allons suivre :

Intéressons nous à la stratégie de J1, quand J2 joue une stratégie mixte (rappel : les stratégies mixtes englobent également les stratégies pures).
Supposons que J2 joue F avec une probabilité q et M avec une probabilité 1-q, nous cherchons à savoir quelle stratégie J1 doit adopter en fonction de la valeur prise par q.
Regardons, les paiement associés à J1 selon sa stratégie :
Si J1 joue F :
g1(F,q) = 3q + (-1)(1-q)
En effet, J1 obtiendra un gain de 3, q% du temps, et un gain de -1, (1-q)% du temps.
On remarque par ailleurs, que si q=1, cela signifie que J2 joue tout le temps F, et donc J1 obtient bien un gain de 3 en jouant F (paiement associé à J1 de (F,F)).
Et si q=0, cela signifie que J2 ne joue jamais F, donc tout le temps M, et donc en jouant F, J1 obtient bien un paiement de -1 (paiement associé à J1 de (F,M)).

Si J1 joue M :
g1(M,q) = q(-1)+(1-q)0=-q
De même, on peut voir, dans les cas extrêmes, si q=1, ie J2 joue F, J1 obtient bien -1, et si jamais q=0, J2 joue M, et J1 obtient bien 0.

Que doit jouer J1 ?
Considérons la stratégie de J1 qui consiste à jouer p% du temps F, et (1-p)% du temps M.
J1 veut maximiser son paiement.
Autrement dit, il doit jouer M, si g1(M,q)≥g1(F,q), et sinon jouer F.

Résolvons donc l'équation g1(M,q)=g1(F,q)
On a donc : 4q-1=-q
Donc q=1/5.

On voit notamment que si q prend cette valeur de 1/5, J1 est indifférent à jouer M ou F, il peut utiliser n'importe quelle stratégie mixte, qui va lui rapporter exactement le même paiement !
En revanche si q<1/5 il doit jouer toujours M ! Et si jamais q>1/5 il doit jouer toujours F.

Nous avons ainsi déterminé la stratégie optimale que doit jouer J1 en fonction de la stratégie de J2.
On note également que si q=1/5, J1 obtiendra toujours exactement le même paiement quel que soit la stratégie qu'il emploie. Il obtiendra toujours un paiement de -1/5, principe d'indifférence que l'on retrouve également au poker de manière similaire quand un joueur joue de façon optimale.
Si q=1/5, son paiement sera de -1/5, à noter également que cette valeur est une espérance de gain, autrement dit si J2 joue 1 fois sur 5 F et le reste du temps M, en moyenne J1 sera perdant, et aura un gain de -1/5 par partie (en moyenne).

On a la fonction de réaction suivante pour déterminer p :
p=R1(q)= 0 si q<1/5 -> p=0=> J1 doit jouer 100% du temps M
[0,1] si q=1/5 -> J1 peut jouer de façon indifférente n'importe quelle stratégie
1 si q>1/5 -> p=1=> J1 doit jouer 100% du temps F

 

On va faire la même chose pour J2 :
On considère que J1 joue avec probabilité p F, et avec probabilité (1-p) M.
Quels sont les paiements associés aux stratégies de J2 ?
Si J2 joue F :
g2(p,F) =1p+(1-p)(-2)=3p-2
En effet, J2 obtiendra un gain de 1, p% du temps, et un gain de -2, (1-p)% du temps.
On remarque par ailleurs, que si p=1, cela signifie que J1 joue tout le temps F, et donc J2 obtient bien un gain de 1 en jouant F (paiement associé à J2 de (F,F)).
Et si p=0, cela signifie que J1 ne joue jamais F, donc tout le temps M, et donc en jouant F, J2 obtient bien un paiement de -2 (paiement associé à J1 de (F,M)).

Si J2 joue M :
g2(p,M) = (-2)p+3(1-p)=-5p+3
De même, on peut voir, dans les cas extrêmes, si p=1, ie J1 joue F, J2 obtient bien -2, et si jamais p=0, J1 joue M, et J2 obtient bien 3 en jouant M également.

Que doit jouer J2 selon la valeur de p ???
J2 veut maximiser son paiement.
Autrement dit, il doit jouer M, si g2(p,M)≥g2(p,F), et sinon jouer F.

Résolvons donc l'équation g2(p,M)= g2(p,F)
On a donc : 3p-2=-5p+3
Donc p=5/8.

De même que précédemment, on voit que si J1 joue avec probabilité p=5/8 F et le reste du temps M, J2 recevra le même paiement quel que soit sa stratégie, et ce paiement sera de 3x5/8-2=-1/8
Si jamais p<5/8, on voit que g2(p,M)≥g2(p,F), donc J2 doit jouer 100% du temps M, autrement dit, q=0, et de même, si q>5/8, J2 doit jouer 100% du temps F et donc q=1.
On obtient donc la fonction de réaction suivante :
q=R2(p)= 0 si p<5/8 -> q=0=> J2 doit jouer 100% du temps M
[0,1] si p=5/8 -> J1 peut jouer de façon indifférente n'importe quelle stratégie
1 si p>5/8 -> q=1=> J2 doit jouer 100% du temps F.

Traçons ces deux courbes sur un même graphique

 

On aura mis en abscisse p, et en ordonnées q, et en rouge R1(q), et en bleu R2(p).
On remarque qu'il y a 3 points d'intersection, qui correspondent aux valeurs de (p,q) suivantes :
(0,0), (1,1), (5/8,1/5).
Ces 3 points correspondent aux 3 E.N., en effet, nous l'avons déjà vu pour les 2 premiers.
Mais c'est aussi clair pour le 3eme :
Si J1 joue p=5/8 nous avons vu que J2 peut choisir indifféremment n'importe quelle stratégie, et qu'elle lui apportera exactement le même paiement, il n'a donc aucun intérêt de dévier de sa stratégie actuelle.
De même si J2 joue q=1/5, on sait que J1 peut également jouer de façon indifférente n'importe quelle stratégie, il n'aura donc pas d'intérêt à dévier de sa stratégie actuelle.

 

Quelques parallèles avec le poker :

Vous l'avez compris, le but de l'article est de vous donner du vocabulaire, et des idées pour mieux comprendre les articles que vous lirez sur le GTO. En particulier, dans ces articles les notions de base que j'expose sont souvent peu définies, ou assez rapidement, et leur compréhension par le lecteur peut parfois être mauvaise, partielle, ou laborieuse.
Malheureusement, en un article, c'est un peu court pour faire un tour d'horizon. Mais un second article suivra probablement pour parler davantage de la notion d'indifférence et d'autres notions utiles à qui veut lire des articles orientés GTO, car telle qu'exposé ici, on est encore assez loin du cadre du poker. Cependant, je pense qu'il est important de bien comprendre ces premières notions (E.N., valeur, etc).

Au niveau du poker :
Le poker est un jeu à somme nulle, fini (l'ensemble des stratégies reste fini, en particulier, le nombre de size bet possible n'est pas infini).
Parler de GTO, ou de jeu à l'E.N., cela revient au même. Nous avons vu que si un jeu admettait un E.N. il admettait également une valeur. Pour le poker la valeur du jeu est de 0.
Cela signifie qu'une stratégie optimale (GTO) garantit au joueur de gagner au moins 0 (en moyenne), quelle que soit la stratégie utilisée par l'adversaire. Si nous sommes à l'E.N., cela signifie que tous les joueurs jouent de façon optimale, et le jeu atteint sa valeur, chaque joueur gagne en moyenne 0.
Si un joueur joue la stratégie optimale GTO, et pas les autres, il a la garantie de recevoir un gain minimum de 0, mais potentiellement plus selon les stratégies adversaires (en pratique plus).
A noter également, que si on s'intéresse au valeur du jeu en ne changeant pas les positions des joueurs, considérons un HU 100bb deep par exemple. Le joueur qui est au bouton a la plus grosse valeur v, celle-ci est strictement positive, cela signifie que sa stratégie optimale lui assure un gain. A l'inverse la stratégie optimale de la BB lui assure également une valeur de -v, autrement dit, sa stratégie optimale lui garantit de ne pas perdre plus de v quand il est en BB.
Ensuite les positions s'inversent, et les stratégies également, ce qui amène à une valeur de 0.
Notez également que cette notion de valeur ne tient pas compte du rake, on a vu qu'un jeu à l'E.N. amenait une valeur de 0, mais cela s'avère vrai en moyenne, et sans rake, avec le rake chaque joueur est perdant si tout le monde joue optimal

 

Article écrit par Youstiti