Arbres de Décision) Meltem OZTURK: …ozturk/CoursSlides/ThJeux2011.pdfTheorie des jeux : histoire´ La théorie des jeux moderne commence avec la publication en 1944 du livre d’Oskar

Théorie des jeux

(Arbres de Décision)

Meltem OZTURK: [email protected]

www.lamsade.dauphine.fr/∼ozturk, enseignement

AMCD – p. 1

Théorie des jeux

Un jeux est une situation où les joueurs sont conduits à faire des choixstratégiques parmi un certain nombre d’actions possibles, ,

et dans un cadre défini à l’avance qui sera les règles du jeu.

Le résultat de ces choix constituant une issue du jeu, à laquelle estassocié un gain (ou une perte) pour chacun des participants.

ref : www.sciences.ch/htmlfr/mathsociales

AMCD – p. 2

Théorie des jeux

La théorie des jeux s’intéresse aux situations où des individusdoivent prendre des décisions "en interaction" , dans le sens où le gainde chacun dépend de ce qu’il fait mais aussi de ce que font les autres.

Pour un joueur, toute la difficulté provient alors de ce qu’il doit anticiperle choix des autres, avant de faire le sien.

d’où l’hypothèse de rationalité : les joueurs cherchent à maximiserleur gain, compte tenu de l’information dont ils disposent et ce fait estconnaissanec commune (chacun sait que les autres sont rationnels,qu’ils savent qu’il sait, etc...)

ref : B. Guerrin, La théorie des jeux, Economica, 2002

AMCD – p. 3

Théorie des jeux : histoire

L’analyse du duopole d’Antoine Augustin Cournot publiée en 1838dans ses Recherches sur les principes mathématiques de la théoriedes richesses peut être considérée comme la première formulation,dans un cadre particulier, de la notion d’équilibre de Nash.

Dans son ouvrage de 1938, Applications aux Jeux de Hasard, ÉmileBorel développe un théorème du minimax pour les jeux à somme nulleà deux joueurs, c’est-à-dire les jeux dans lesquels ce que gagne l’unest perdu par l’autre.

AMCD – p. 4

Théorie des jeux : histoire

La théorie des jeux moderne commence avec la publication en 1944du livre d’Oskar Morgenstern et John von Neumann, Theory of Gamesand Economic Behavior. Cet ouvrage fondateur détaille la méthode derésolution des jeux à somme nulle

Elle a été principalement développée dans les années 1950,notamment avec les travaux de John Nash.

Deux prix de Nobel : En 1994, John Nash, Reinhard Selten et JohnHarsanyi et en 2005, Thomas Schelling et Robert Aumann

ref : http://fr.wikipedia.org/wiki/Théorie_des_jeux

AMCD – p. 5

Théorie des jeux: premier exemple

Dilemme des prisonniers

deux prisonniers (complices d’un délit) retenus dans des cellulesséparées et qui ne peuvent communiquer. On leur dit que

• si un des deux prisonniers dénonce l’autre, il est remis en libertéalors que le second obtient la peine maximale (10 ans) ;

• si les deux se dénoncent entre eux, ils seront condamnés à unepeine plus légère (5 ans) ;

• si les deux refusent de dénoncer, la peine sera minimale (6mois), faute d’éléments au dossier.

AMCD – p. 6

Théorie des jeux: premier exemple


B se tait B denonce

A se tait (0.5,0.5) (10,0)

A denonce (0,10) (5,5)

où les M(i, j) sont à minimiser.

AMCD – p. 7

Théorie des jeux : types de jeux

• Jeux coopératifs et jeux non coopératifsjeux coopératifs: formation de coalitions entre les joueurs afind’obtenir un meilleur résultat pour ses membres;

• Jeux simultanés et jeux séquentielsjeu simultané: les joueurs décident en même temps de leurstratégie ;jeu séquentiel: on peut spécifier l’ordre des décisions de sortequ’un joueur peut décider de sa stratégie conditionnellement àce qu’ont joué les autres joueurs précédemment.

AMCD – p. 8

Théorie des jeux : types de jeux

• Jeux finis(l’ensemble des stratégies de chacun des joueurs est fini) .

• Jeux à somme nulle et jeux à somme positive (et aussi jeux àintérêts communs, ex: lieu de rdv)

• Jeux répétés(connaissance des résultats intermédiaires, change souventfondamentalement son déroulement (les meilleurs coups et laconclusion). Ex : il peut être utile de prendre ponctuellement lerisque de perdre « pour voir », tester les autres joueurs, et mettreen place des stratégies de communication par les coups joués.

Notre cours se base sur les jeux non coopératifs, simultanés, finis et àun seul coup.

AMCD – p. 9

Cadre du cours: jeux̀a un seul coup

Jeux à un seul coup : Un jeux où les joueurs choisissentsimultanément une, et une seule de leur action possible.

exemple

b1 b2 b3

a1 (7, 5) (3, 7) (1, 8)

a2 (8, 4) (5, 3) (2, 6)

où M(ai, bj) = (xi, yj) : le joueur A choisit de jouer ai et B choisit bj . Al’issue de ces décisions A gagne xi et B gagne yj .

AMCD – p. 10

Cadre du cours: jeux̀a un seul coup

Remarque : La représentation matricielle des gains s’appelle formenormale. Il existe aussi une représentation dite forme extensive où onutilise un arbre.

• La représentation sous forme matricielle ou normale: Adaptépour des jeux (statiques) avec décisions simultanées

• La représentation sous forme d’arbre ou extensive : Adapté pourdes jeux avec décisions séquentielles

AMCD – p. 11

Théorie des jeux: exemple de stratégie


B se tait B denonce

A se tait (0.5,0.5) (10,0)

A denonce (0,10) (5,5)

où les M(i, j) sont à minimiser.

AMCD – p. 12


le joueur A pense:

• si B dénonce, alors :

• si je me tais j’ai 10 ans de prisons

• si je dénonce j’ai 5 ans de prisons

c’est donc mieux de dénoncer

• si B se tait, alors :

• si je me tais j’ai 6 mois de prisons

• si je denonce j’ai 0 an de prisons

c’est donc mieux de dénoncer

Conclusion je dénonce.

Dénoncer est une stratégie dominante pour A.

AMCD – p. 13



se taire denoncer

se taire (0.5, 0.5) (10,0)

denoncer (0,10) (5,5)

Résultat : tous les deux prisonniers dénoncent pourtant le cas (setaire, se taire) est mieux pour les deux mais cette issue n’est passtable! (voir plus loin l’idéee de l’equilibre de Nash)

AMCD – p. 14

Théorie des jeux: dilemme des prisonniers


Modélisation pour

• problèmes politiques tarifaires: baisser ou pas le prix d’un produit

• politique internationale : avoir ou pas avoir d’armée

• psychologie : couple où chacun trompe l’autre

• sociologie, ecologie, ...

AMCD – p. 15

Petite parenth̀ese

Exemple de stratégie pour jeux séquentiels

• voir l’exemple de Jérôme Renault (polycopié 1, page 9) : lien surle site de Mme Öztürk

• et le dilemme des prisonniers

AMCD – p. 16

Théorie des jeux : dominance

Dominance

Une stratégie si est dominante (resp. faiblement dominante) pour unjoueur A si et seulement si quelles que soient les actions de l’autrejoueur la stratégie si apporte strictement plus (resp. plus ou égal) degain que les autres stratégies du joueur A.

AMCD – p. 17


Dominance

b1 b2 b3

a1 (7,5) (3,7) (1,8)

a2 (8,4) (5,3) (2,6)

AMCD – p. 18


Dominance

b1 b2 b3

a1 (7,5) (3,7) (1,8)

a2 (8,4) (5,3) (2,6)

• pour A : la stratégie dominante est a2

• pour B : la stratégie dominante est b3

solution "évidente :" (a2, b3)

AMCD – p. 18


Dominance

b1 b2 b3

a1 (7,5) (3,7) (1,8)

a2 (8,4) (5,3) (2,6)




• Même remarque que les prisonniers : et si c’était (3,7)?

AMCD – p. 18


Dominance

b1 b2 b3

a1 (7,5) (3,7) (1,8)

a2 (8,4) (5,3) (2,6)




• Même remarque que les prisonniers : et si c’était (3,7)?

• Et s’il n’y a pas de stratégie dominante?

AMCD – p. 18


Stratégie dominée

Une stratégie si est strictement dominée (resp. faiblement dominée)pour un joueur A si et seulement s’il existe une autre stratégie s∗ telleque, quelles que soient les stratégies adoptées par les autres joueurs,cette autre stratégie s∗ est toujours strictement meilleure que si (resp.au moins aussi bonne que si et strictement meilleure dans au moinsl’une des situations) .

AMCD – p. 19

Théorie des jeux

Elimination par iteration des stratégies dominées

b1 b2 b3

a1 (2,4) (3,7) (2,5)

a2 (4,6) (6,5) (3,7)

a3 (5,4) (2,3) (4,2)

AMCD – p. 20

Théorie des jeux


b1 b2 b3

a1 (2,4) (3,7) (2,5)

a2 (4,6) (6,5) (3,7)

a3 (5,4) (2,3) (4,2)

on elimine d’abord a1 (dominé par a2)

AMCD – p. 20

Théorie des jeux


b1 b2 b3

a1 (2,4) (3,7) (2,5)

a2 (4,6) (6,5) (3,7)

a3 (5,4) (2,3) (4,2)

on elimine d’abord a1 (dominé par a2)après b2 (dominé par b1).

AMCD – p. 20

Théorie des jeux


b1 b2 b3

a1 (2,4) (3,7) (2,5)

a2 (4,6) (6,5) (3,7)

a3 (5,4) (2,3) (4,2)

on elimine d’abord a1 (dominé par a2)après b2 (dominé par b1).L’action a3 devient dominante sur le reste des actions de A.

AMCD – p. 20

Théorie des jeux


b1 b2 b3

a1 (2,4) (3,7) (2,5)

a2 (4,6) (6,5) (3,7)

a3 (5,4) (2,3) (4,2)

on elimine d’abord a1 (dominé par a2)après b2 (dominé par b1).L’action a3 devient dominante sur le reste des actions de A.Donc A choisit a3, alors B choisira b1 (et si (a2, b2)?).

AMCD – p. 20

Théorie des jeux : exemples

• D’autres exemples

• exemple jeux pécheurs

• exemple avec 4 actions

• exemple avec dominance faible

• Et si ces exemples étaient des jeux séquentiels

• exemple avec dominance

• exemple avec élimination par itération des stratégiesdominées

AMCD – p. 21

Théorie des jeux


• Un jeu est dit résoluble par élimination itérative des stratégiesdominées, si on obtient un unique profil en éliminantsuccessivement des stratégies (strictement) dominées

• Les profils obtenus après élimination itérative des stratégiesstrictement dominées ne dépendent pas de l’ordre choisi pourl’élimination des stratégies.

• Les profils obtenus après élimination itérative des stratégiesfaiblement dominées dépendent de l’ordre choisi pourl’élimination des stratégies.

AMCD – p. 22

Théorie des jeux


• Si on modélise le même jeux simultané comme un jeuxséquentiel, l’ordre de passage des joueurs est important sil’élimination en jeux simultanée se fait avec dominance faible.

• et si pas d’actions dominées?

AMCD – p. 23

Théorie des jeux: Croyance

exemple

b1 b2 b3

a1 (2,2) (1,6) (4,4)

a2 (3,3) (2,2) (2,0)

a3 (2,1) (7,5) (2,7)

AMCD – p. 24


exemple

b1 b2 b3

a1 (2,2) (1,6) (4,4)

a2 (3,3) (2,2) (2,0)

a3 (2,1) (7,5) (2,7)

• pas de dominance

• idée pour continuer : croyance de chaque joueur concernant lechoix des autres fondées sur l’idée que les autres sont rationnelset cela est connaissance commune.

AMCD – p. 24


exemple

b1 b2 b3

a1 (2,2) (1,6) (4,4)

a2 (3,3) (2,2) (2,0)

a3 (2,1) (7,5) (2,7)

croyance erronées : Si c’est (a1, b1) qui réalise:

AMCD – p. 25


exemple

b1 b2 b3

a1 (2,2) (1,6) (4,4)

a2 (3,3) (2,2) (2,0)

a3 (2,1) (7,5) (2,7)

croyance erronées : Si c’est (a1, b1) qui réalise:

• A dit : ayy ayy j’avais cru que B allait jouer b3.

• B dit : ayy ayy j’avais cru que A choisira a2.

• tous les deux joueurs se sont trompés dans leur croyance quiporte sur l’action de l’autre.

AMCD – p. 25

Théorie des jeux: Croyance, Eq. de Nash

exemple

b1 b2 b3

a1 (2,2) (1,6) (4,4)

a2 (3,3) (2,2) (2,0)

a3 (2,1) (7,5) (2,7)

Bonne croyance (?) : si c’est (a2, b1)

AMCD – p. 26

Théorie des jeux: Croyance, Eq. de Nash

exemple

b1 b2 b3

a1 (2,2) (1,6) (4,4)

a2 (3,3) (2,2) (2,0)

a3 (2,1) (7,5) (2,7)

Bonne croyance (?) : si c’est (a2, b1)

• A a joué a2 car il pensait que B choisira b1

• B a joué b1 car il pensait que A choisira a2.

• Les deux joueurs ont eu raisons.

• Personne n’a intérêt de bouger.

AMCD – p. 26

Théorie des jeux: Equilibre de Nash

Equilibre de Nash: une issue d’un jeu dans lequel aucun joueur n’aintérêt à modifier sa stratégie unilatéralement, compte tenu desstratégies des autres joueurs. Les joueurs sont contents de leurprévision.

Interpretation : issue a∗, b∗ est un equilibre de Nash :

• a∗ est la meilleure stratégie pour A si B joue b∗

• b∗ est la meilleure stratégie pour B si A joue a∗

AMCD – p. 27


Equilibre de Nash: une issue d’un jeu dans lequel aucun joueur n’aintérêt à modifier sa stratégie unilatéralement, compte tenu desstratégies des autres joueurs. Les joueurs sont contents de leurprévision.

Remarque :

• (a2, b1) est une équilibre de Nash dans le jeu précédent.

• issue (dénoncer, dénoncer) est l’équilibre de Nash dans le jeudes prisonniers

AMCD – p. 28


exemple de jeu de coordination

Femme et mari veulent aller voir un film ensemble. La femme préfèreles films romantiques tandis que son mari veut voir un film d’action.Néanmoins ils n’ont pas envie de voir des films séparément. Voici letableau des utilités (femme sur les lignes et homme sur les colonnes)

romantique action

romantique (3,2) (1,1)

action (1,1) (2,3)

AMCD – p. 29




romantique action


action (1,1) (2,3)

Deux equilibres : (romantique, romantique) et (action, action)

AMCD – p. 29




romantique action


action (1,1) (2,3)

Deux equilibres : (romantique, romantique) et (action, action)

Quelle conclusion? (peut-on attendre tout et n’importe quoi?)

AMCD – p. 29


exemple de jeu : poule mouillée

deux voitures se dirigent l’une vers l’autre au milieu de la chaussée.:celui qui s’écarte au dernier moment est "poule mouillé", donc songain est nul, celui de l’autre étant strictement positif. Si tous les deuxs’écartent le déshonneur est total mais le pire arrive bien sûr quand iln’y a aucun qui s’écarte.

passer s’écarter

passer (-2, -2) (1,0)

s’écarter (0,1) (-1, -1)

Equilibre(s) : ?

AMCD – p. 30


exemple de jeu : un gagne l’autre perd

b1 b2

a1 (0, 1) (1,0)

a2 (1, 0) (0,1)

Equilibre(s) : ?

AMCD – p. 31


exemple de jeu : Pierre/ciseau/papier

pierre ciseau papier

pierre (0, 0) (1,-1) (-1,1)

ciseau (-1, 1) (0, 0) (1, -1)

papier (1, -1) (-1, 1) (0, 0)

Equilibre(s) : ?

AMCD – p. 32


exemple de jeu : Pierre/ciseau/papier

pierre ciseau papier

pierre (0, 0) (1,-1) (-1,1)

ciseau (-1, 1) (0, 0) (1, -1)

papier (1, -1) (-1, 1) (0, 0)

Equilibre(s) : ?

Deux autres exemples de jeux?

AMCD – p. 32

Théorie des jeux

Equilibre de Nash

• Un profil (unique) obtenu par élimination itérative de stratégies(strictement) dominées est un équilibre de Nash (et c’est le seuléquilibre du jeu).

• On peut avoir plusieurs équilibres de Nash.

• On peut ne pas avoir d’équilibre de Nash.

• A quoi sert l’équilibre de Nash?

• Expérience (ex: jeux des milles pattes, seuls 1,5% des sujets secomportent comme le prédit l’eq. de Nash, pas le cas avec lesjoueurs professionnels d’échecs)...

AMCD – p. 33


exemple de jeu : échange de monnaie

b1 b2

a1 (1, -1) (-1,1)

a2 (-1, 1) (1, -1)

• Pas d’équilibre mais Nash est connu avec sa théorème surl’existence d’équilibre (1950)?

• Jeux à somme nulle, mais même en 1928 Von Neumangarantissait l’existence d’équilibre (thm Minimax)?

• Alors où ont-ils trouvé l’équilibre?

AMCD – p. 34

Strat́egie pure/ stratégie mixte

• Une stratégie pure du joueur i est un plan d’action qui prescritune action de ce joueur pour chaque fois qu’il est susceptible dejouer.

• Les cas que nous avons vus jusqu’à présent sont à stratégiespures.

• Une stratégie mixte du joueur i est une distribution deprobabilités pi définie sur l’ensemble des stratégies pures dujoueur i.

AMCD – p. 35


exemple de stratégie mixte :

b1 b2 probabilité de A

a1 (2, 0) (0,1) pA

a2 (0, 3) (1, 0) 1− pA

probabilité de B pB 1− pB

AMCD – p. 36


exemple de stratégie mixte :

b1 b2 probabilité de A

a1 (-3, -2) (10, 0) pA

a2 (0, 0) (1, 0) 1− pA

probabilité de B pB 1− pB

AMCD – p. 37


• Il existe toujours un équilibre de Nash dans des stratégiesmixtes.

• Donc prendre en compte les stratégies mixtes permet de trouverdes équilibres là où il n’y en a pas.

• Mais cela peut faire apparaître de nouveaux équilibres là où il yen a déjà trop.

• Quelle interprétation à donner à des stratégies mixtes?

AMCD – p. 38


Trouver les equilibres de Nash en stratégies mixtes:

•

b1 b2

a1 (2,1) (0,0)

a2 (0,0) (1, 2)

•

b1 b2

a1 (1, -1) (-1,1)

a2 (-1, 1) (1, -1)

AMCD – p. 39

si on a du temps

Résoudre l’exemple de jeux séquentiel avec plusieurs niveaux :stratégie “backward induction” (induction en arrière)

AMCD – p. 40

ThÃ©orie des jeuxThÃ©orie des jeuxThÃ©orie des jeuxThÃ©orie des jeux : histoireThÃ©orie des jeux : histoireThÃ©orie des jeux: premier exempleThÃ©orie des jeux: premier exempleThÃ©orie des jeux : types de jeuxThÃ©orie des jeux : types de jeuxCadre du cours: jeux Ã€ un seul coupCadre du cours: jeux Ã€ un seul coupThÃ©orie des jeux: exemple de stratÃ©gieThÃ©orie des jeux: exemple de stratÃ©gieThÃ©orie des jeux: exemple de stratÃ©gieThÃ©orie des jeux: dilemme des prisonniersPetite parenthÃ¨seThÃ©orie des jeux : dominanceThÃ©orie des jeux : dominanceThÃ©orie des jeux : dominanceThÃ©orie des jeux : dominanceThÃ©orie des jeux : dominance

ThÃ©orie des jeux : dominanceThÃ©orie des jeuxThÃ©orie des jeuxThÃ©orie des jeuxThÃ©orie des jeuxThÃ©orie des jeuxThÃ©orie des jeux

ThÃ©orie des jeux : exemplesThÃ©orie des jeuxThÃ©orie des jeuxThÃ©orie des jeux: CroyanceThÃ©orie des jeux: Croyance

ThÃ©orie des jeux: CroyanceThÃ©orie des jeux: Croyance

ThÃ©orie des jeux: Croyance, Eq. de NashThÃ©orie des jeux: Croyance, Eq. de Nash

ThÃ©orie des jeux: Equilibre de NashThÃ©orie des jeux: Equilibre de NashThÃ©orie des jeux: Equilibre de NashThÃ©orie des jeux: Equilibre de NashThÃ©orie des jeux: Equilibre de Nash

ThÃ©orie des jeux: Equilibre de NashThÃ©orie des jeux: Equilibre de NashThÃ©orie des jeux: Equilibre de NashThÃ©orie des jeux: Equilibre de Nash

ThÃ©orie des jeuxThÃ©orie des jeux: Equilibre de NashStratÃ©gie pure/ stratÃ©gie mixteStratÃ©gie pure/ stratÃ©gie mixteStratÃ©gie pure/ stratÃ©gie mixteStratÃ©gie pure/ stratÃ©gie mixteStratÃ©gie pure/ stratÃ©gie mixtesi on a du temps

Documents

Arbres de Décision) Meltem OZTURK: …ozturk/CoursSlides/ThJeux2011.pdfTheorie des jeux : histoire´ La théorie des jeux moderne commence avec la publication en 1944 du livre d’Oskar