36
Mathématiques Mathématiques et et Théorie des Jeux Théorie des Jeux

Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

Embed Size (px)

Citation preview

Page 1: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

Mathématiques Mathématiques et et

Théorie des JeuxThéorie des Jeux

Page 2: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

Qu’est ce que la Théorie Qu’est ce que la Théorie des jeux ?des jeux ?

Page 3: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

• Une Une théorie mathématiquethéorie mathématique

du conflit et de la coopération . . .du conflit et de la coopération . . .

• Elle analyse des situations où des Elle analyse des situations où des agents rationnelsagents rationnels doivent prendre doivent prendre des décisions des décisions stratégiquesstratégiques dont les dont les conséquences dépendent de l’état du conséquences dépendent de l’état du monde,monde,

mais aussi des décisions prises mais aussi des décisions prises par les autres agents.par les autres agents.

Page 4: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

• Des motivations Des motivations historiqueshistoriques et et philosophiques anciennes : philosophiques anciennes : La question du contrat social chez les La question du contrat social chez les précurseurs de la philosophie politique,précurseurs de la philosophie politique,

Platon Platon ((La La républiquerépublique, - 427, -347), , - 427, -347),

Hobbes (Hobbes (Le LéviathanLe Léviathan, 1651), , 1651),

Rousseau (Rousseau (Du Contrat Social, Du Contrat Social, 1762).1762).

Page 5: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

• Des motivations Des motivations historiqueshistoriques et et philosophiques anciennes : philosophiques anciennes : La question du La question du contratcontrat social chez les social chez les précurseurs de la philosophie politique,précurseurs de la philosophie politique,

Platon Platon ((La La républiquerépublique, - 427, -347), , - 427, -347),

Hobbes (Hobbes (Le LéviathanLe Léviathan, 1651), , 1651),

Rousseau (Rousseau (Du Contrat Social, Du Contrat Social, 1762).1762).

• UneUne théorie jeune : théorie jeune :Von Neumann et Morgenstern Von Neumann et Morgenstern

((Theory of Games and Economic Theory of Games and Economic Behavior, 1944Behavior, 1944 ). ).

Page 6: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

Qu’est ce qu’un jeu ?Qu’est ce qu’un jeu ?

Page 7: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

• Des Des joueursjoueurs : i = 1, 2 : i = 1, 2

• Un ensemble d’Un ensemble d’actionsactions pour chaque pour chaque joueur : A1, A2joueur : A1, A2

• Des fonctions d’Des fonctions d’utilitéutilité : U1, U2 :A1 × : U1, U2 :A1 × A2→ R A2→ R

U1(x,y) = utilité (payoff) du joueur 1 U1(x,y) = utilité (payoff) du joueur 1 associée aux actions x et y.associée aux actions x et y.

Les joueurs jouent Les joueurs jouent simultanément.simultanément.

Page 8: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

Le Dilemme du PrisonnierLe Dilemme du Prisonnier(Tucker, 1950)(Tucker, 1950)

-6 /-6-6 /-6 0 /-100 /-10

-10 / 0-10 / 0 -2 /-2-2 /-2

Trahir Coopérer

T

C

Page 9: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

Le DP est un paradigme pour de Le DP est un paradigme pour de nombreuses situations :nombreuses situations :

• Le Problème du « free rider » (les Le Problème du « free rider » (les boites à journaux en Suisse)boites à journaux en Suisse)

• La provision des biens publics La provision des biens publics (environnement, taxes, défense (environnement, taxes, défense nationale,…)nationale,…)

La solution de Hobbes : Changer les La solution de Hobbes : Changer les règles du jeu …règles du jeu …

« Covenants struck without the sword are « Covenants struck without the sword are but words », 1651, but words », 1651, Le LéviathanLe Léviathan

Page 10: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

Le Dilemme du Le Dilemme du PrisonnierPrisonnier

Page 11: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

ÉquilibresÉquilibres

Page 12: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

Un couple Un couple d’actionsd’actions ( (xx , , yy) ) estest un un équilibreéquilibre de Nashde Nash sisi

U2 (U2 (xx , , yy) ≥ U2() ≥ U2(xx , y) pour toute , y) pour toute action y action y

etet

U1 (U1 (xx , , yy) ≥ U1(x , ) ≥ U1(x , yy) pour ) pour toutetoute action x action x

Page 13: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

Un couple Un couple d’actionsd’actions ( (xx , , yy) ) estest un un équilibreéquilibre de Nashde Nash sisi

U2 (U2 (xx , , yy) ≥ U2() ≥ U2(xx , y) pour toute , y) pour toute action y action y

etet

U1 (U1 (xx , , yy) ≥ U1(x , ) ≥ U1(x , yy) pour ) pour toutetoute action x action x

• (T,T) est l’unique équilibre du (T,T) est l’unique équilibre du Dilemme du PrisonnierDilemme du Prisonnier

Page 14: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

Le Le jeujeu des 3 des 3 pontspontsSûrSûr PierresPierres CobrasCobras

S

P

C

0 / 1000 / 100 100 / 0100 / 0 100 / 0100 / 0

80 / 2080 / 20 0 / 1000 / 100 80 / 2080 / 20

60 / 40 60 / 40 60 / 40 60 / 40 0 / 1000 / 100

Page 15: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

• Le jeu des 3 ponts n’admet pas Le jeu des 3 ponts n’admet pas d’équilibre…d’équilibre…

Et pourtant :Et pourtant :

ThéorèmeThéorème (Nash, 1950) : (Nash, 1950) : Tout jeu admet Tout jeu admet un équilibre en un équilibre en stratégies mixtesstratégies mixtes

« I certainly knew right away that it was a « I certainly knew right away that it was a thesis. I didn’t know it was a Nobel. » thesis. I didn’t know it was a Nobel. » (David Gale, 1995)(David Gale, 1995)

Page 16: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

• Une Une stratégie mixtestratégie mixte est une est une « loterie » (une distribution de « loterie » (une distribution de probabilité) sur l’ensemble des probabilité) sur l’ensemble des actionsactions

• L’utilité s’étend par bilinéarité à L’utilité s’étend par bilinéarité à l’espace des stratégies mixtes l’espace des stratégies mixtes

U(x,y) = U(x,y) = ΣΣ x(i) y(j)x(i) y(j) U(i,j) U(i,j) L’équilibre dans le jeu des 3 ponts L’équilibre dans le jeu des 3 ponts

est x est x ~ (0.26, 0.32, 0.42), ~ (0.26, 0.32, 0.42), y y ~ (0.49, 0.36, 0.15) ~ (0.49, 0.36, 0.15)

La La valeurvaleur du jeu du jeu~ 51~ 51

Page 17: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

L’existence n’est pas L’existence n’est pas l’unicitél’unicité

Page 18: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

Le Le jeujeu du Cerf et du du Cerf et du LièvreLièvre

““S’agissait-il de prendre un cerf, chacun S’agissait-il de prendre un cerf, chacun sentait bien qu’il devait pour cela garder sentait bien qu’il devait pour cela garder fidèlement son poste; mais si un lièvre fidèlement son poste; mais si un lièvre venait à passer à la portée de l’un d’eux, venait à passer à la portée de l’un d’eux, il ne faut pas douter qu’il ne le poursuivit il ne faut pas douter qu’il ne le poursuivit sans scrupule, et qu’ayant atteint sa sans scrupule, et qu’ayant atteint sa proie il ne souciât fort peu de faire proie il ne souciât fort peu de faire manquer la leur à ses compagnons”manquer la leur à ses compagnons”

Rousseau, Rousseau, Discours sur l’origine de Discours sur l’origine de l’inégalité,l’inégalité, 1755 1755

Page 19: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

5 / 55 / 5 0 / 40 / 4

4 / 0 4 / 0 2 / 22 / 2

Cerf Lièvre

C

L

Page 20: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

5 / 55 / 5 Pareto Pareto dominant dominant 

0 / 40 / 4

4 / 0 4 / 0 2 / 22 / 2

Cerf Lièvre

C

L

Page 21: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

5 / 55 / 5 Pareto Pareto dominant dominant 

0 / 40 / 4

4 / 0 4 / 0 2 / 22 / 2

Risque Risque dominantdominant

(Harsanyi et (Harsanyi et Selten, prix Selten, prix

Nobels 1994)Nobels 1994)

Cerf Lièvre

C

L

Page 22: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

5 / 55 / 5 Pareto Pareto dominant dominant 

0 / 40 / 4

4 / 0 4 / 0 Un équilibre Un équilibre mixtemixte : :

(2/3 C, 1/3 L)(2/3 C, 1/3 L)

2 / 22 / 2

Risque Risque dominantdominant

(Harsanyi et (Harsanyi et Selten, prix Selten, prix

Nobels 1994)Nobels 1994)

Cerf Lièvre

C

L

Page 23: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

• La multiplicité des équilibres, La multiplicité des équilibres, • La question de la rationalité et du « La question de la rationalité et du «

common knowledge »,common knowledge »,• Les évidences expérimentales, Les évidences expérimentales,

Posent un Posent un ProblèmeProblème Majeur Majeur à la à la théorie des jeux classique :théorie des jeux classique :

Page 24: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

• La multiplicité des équilibres, La multiplicité des équilibres, • La question de la rationalité et du « La question de la rationalité et du «

common knowledge »,common knowledge »,• Les évidences expérimentales, Les évidences expérimentales,

Posent un Posent un ProblèmeProblème Majeur Majeur à la à la théorie des jeux classique :théorie des jeux classique :

Pourquoi les joueurs devraient t-Pourquoi les joueurs devraient t-ils se coordonner sur un ils se coordonner sur un équilibre particulier ?équilibre particulier ?

Page 25: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

ApprentissageApprentissage et et DynamiqueDynamique

Page 26: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

Une explication alternative issue Une explication alternative issue de de l’économiel’économie et de la et de la biologie biologie évolutionnaireévolutionnaire est que est que

« les équilibres peuvent résulter d’un « les équilibres peuvent résulter d’un processus dynamique d’adaptation processus dynamique d’adaptation ou d’apprentissage » ou d’apprentissage »

Page 27: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

Une explication alternative issue Une explication alternative issue de de l’économiel’économie et de la et de la biologie biologie évolutionnaireévolutionnaire est que est que

« les équilibres peuvent résulter d’un « les équilibres peuvent résulter d’un processus dynamique d’adaptation ou processus dynamique d’adaptation ou d’apprentissage » d’apprentissage »

Maynard Smith, Maynard Smith, Evolution and the Theory Evolution and the Theory of Gamesof Games, 1982,, 1982,

Fudenberg et Levine, Fudenberg et Levine, Theory of Learning Theory of Learning in Gamesin Games, 1998,, 1998,

Page 28: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

Le processus de meilleure Le processus de meilleure réponseréponse

• y(n) = fréquence empirique des y(n) = fréquence empirique des actions du joueur 2 à l’instant n,actions du joueur 2 à l’instant n,

• br(y(n)) = « la meilleure réponse à y(n) br(y(n)) = « la meilleure réponse à y(n) » » = Argmax {j : U1( j, y(n))},= Argmax {j : U1( j, y(n))},

• À l’instant n+1, le joueur 1 joue À l’instant n+1, le joueur 1 joue l’action br(y(n)) avec une probabilité l’action br(y(n)) avec une probabilité proche de 1 et le joueur 2 en fait proche de 1 et le joueur 2 en fait autant …autant …

Page 29: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

Vieille idée (Robinson, 1950) Vieille idée (Robinson, 1950) revisitée à la lumière de la théorie des revisitée à la lumière de la théorie des systèmes dynamiquessystèmes dynamiques, des , des processus processus stochastiques, stochastiques, des des inclusions inclusions et deset des équations différentielleséquations différentielles

Travaux en collaboration avecTravaux en collaboration aveco M. W Hirsch, BerkeleyM. W Hirsch, Berkeleyo J. Hofbauer, Londre et VienneJ. Hofbauer, Londre et Vienneo S. Sorin, ParisS. Sorin, Pariso J. Weibull, Stockholm J. Weibull, Stockholm

Page 30: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

Jeux à somme nulleJeux à somme nulle

• U1(x,y) + U2(x,y) = cU1(x,y) + U2(x,y) = c

ThéorèmeThéorème : : Pour un jeu à somme Pour un jeu à somme nulle (x(n),y(n)) converge presque nulle (x(n),y(n)) converge presque sûrement vers l’équilibre de Nash.sûrement vers l’équilibre de Nash.

Page 31: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

Jeux à 2 joueurs et 2 Jeux à 2 joueurs et 2 stratégiesstratégies

ThéorèmeThéorème : : Pour un jeu 2 Pour un jeu 2 × 2 × 2 (x(n),y(n)) (x(n),y(n)) converge presque sûrement vers un converge presque sûrement vers un équilibre de Nash. équilibre de Nash.

« Génériquement » un jeu « Génériquement » un jeu 2 2 × 2 × 2 admet un ou admet un ou trois équilibres : 2 purs et 1 mixte. trois équilibres : 2 purs et 1 mixte.

Dans le second casDans le second cas (x(n),y(n)) converge (x(n),y(n)) converge presque sûrement vers un presque sûrement vers un équilibre puréquilibre pur et et chaque équilibre pur a une probabilité chaque équilibre pur a une probabilité positive d’être sélectionné.positive d’être sélectionné.

Page 32: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

ExternalitésExternalités de Réseau de Réseau

5 / 55 / 5 0 / 40 / 4

4 / 0 4 / 0 2 / 22 / 2

Cerf Lièvre

C

L

Page 33: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

ExternalitésExternalités de Réseau de Réseau

5 / 55 / 5 0 / 10 / 1

1 / 0 1 / 0 2 / 22 / 2

Betamax Vhs

B

V

Page 34: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

ExternalitésExternalités de Réseau de Réseau

5 / 55 / 5 0 / 10 / 1

1 / 0 1 / 0 2 / 22 / 2

Ideal Qwerty

I

Q

Page 35: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

Jeux M x N où M>2, N > Jeux M x N où M>2, N > 22

• Analyse locale : Tout équilibre Analyse locale : Tout équilibre stablestable (instable) a une probabilité (instable) a une probabilité positivepositive (nulle) d’être sélectionné. (nulle) d’être sélectionné.

• Analyse globale : l’asymptotique du Analyse globale : l’asymptotique du jeu requiert l’analyse globale d’un jeu requiert l’analyse globale d’un système dynamique non linéaire. système dynamique non linéaire.

Convergence, Oscillation et Chaos Convergence, Oscillation et Chaos sont possibles.sont possibles.

Page 36: Mathématiques et Théorie des Jeux Quest ce que la Théorie des jeux ?

Jeux répétés et Jeux répétés et CoordinationCoordination