Théorie des jeux - Centrale Marseille

1 Th orie des jeux Renaud Bourl s Dominique Henriet EAO-32-O-FIST. 2 me ann e 2016-2017. Chapitre 1. Introduction Qu'est-ce que la th orie des jeux ? La th orie des jeux est une discipline th orique qui permet de comprendre (formellement). des situations dans lesquelles les joueurs, les preneurs de d cision, interagissent. Un jeu est alors d nit comme un univers dans lequel chaque preneur de d cision poss de un ensemble d'actions possibles d termin par les r gles du jeu. Le r sultat du jeu d pend alors conjointement des actions prises par chaque preneur de d cision. Cette discipline poss de de nombreuses applications permettant notamment de comprendre des ph nom ne conomiques, politiques ou m me biologiques. Parmi ces ph nom nes, voici une liste de situations dans lesquelles la th orie des jeux peut tre appliqu e : la concurrence entre entreprises, la concurrence entre hommes politiques, un jury devant s'accorder sur un verdict, des animaux se battant pour une proie, la participation une ench re, le vote d'un l gislateur soumis la pression de lobbies, ou le r le des menaces et des sanctions dans une relation de long terme.

2 Comme toute discipline th orique, la th orie des jeux consiste en une collection de mod les. Ces mod les sont alors des abstractions utilis es pour comprendre ce qui est observ ou v cu. Ils permettent de pr dire l' volution d'un jeu ou de conseiller le ou les joueurs sur le meilleur coup jouer. Les questions se poser sont alors : Qu'est-ce qu'un individu peut inf rer sur les d cisions des autres ? Peut-on pr dire le choix de chaque joueur ? Quel sera le r sultat de ces actions ? Cela fait-il une di rence si le jeu se d roule plusieurs fois ? 2. LA TH ORIE DU CHOIX RATIONNEL 3. La th orie du choix rationnel Comment mod liser le comportement et les choix des joueurs? La th orie du choix rationnel est une composante majeure de la plupart des mod les de th orie des jeux. Cette th orie stipule qu' tant donn es ses pr f rences, un joueur choisit la meilleure action parmi celles disponibles. On n'impose toutefois aucune restriction qua- litative sur les pr f rences du joueur. La "rationalit " tient dans la coh rence des actions d'un joueur avec ses pr f rences, pas de la nature de ces pr f rences.

3 A n de pouvoir repr senter les pr f rences, il est toutefois n cessaire de supposer que celles-ci sont compl tes sur l'ensemble des actions possibles : si un joueur doit faire un choix entre deux actions, il sera toujours capable de dire laquelle il pr f re des deux ou si il est indi rent entre les deux. Pour que le probl me soit formalisable, il est par ailleurs n cessaire de supposer des pr f rences transitives : si l'action a est pr f r e l'action b et b pr f r e c alors a devra tre pr f r e c. Aucune autre restriction n'est impos e aux pr f rences. Par exemple, il se peut qu'un joueur ait des pr f rences altruistes dans le sens o ses pr f rences d pendent du bien- tre du ou des autres joueurs. Comment repr senter les pr f rences? Une des possibilit s est de sp ci er pour chaque paire d'actions, l'action que le joueur pr f re ou de noter que le joueur est indi rent entre les deux actions. Alternativement, on peut repr senter les pr f rences par une "fonction de paiement" qui associe un nombre chaque action de telle sorte que les actions avec le plus grand "score" soient celles qui sont pr f r es.

4 Comment valuer le r sultat d'un jeu pour un individus? Lorsqu'un jeu conduit des gains mon taires et que les joueurs sont opportunistes ( non altruistes), il est assez facile d' valuer le r sultat d'un jeu et leurs pr f rences : ils pr f rent le r sultat pour lequel ils obtiennent le plus d'argent. Cependant tous les jeux n'ont pas un r sultat mon taire. Ainsi, plus g n ralement, on d nira, la fonction de paiement u d terminant la "satisfaction" des joueurs. La fonction de paiement u repr sentera alors les pr f rences d'un joueur si pour toute actions a et b (dans l'ensemble des actions possible) : u(a) > u(b) si et seulement si le joueur pr f re a b Exemple Une personne a le choix entre 3 destinations pour ses vacances : La Havane, New-York et Venise. Elle pr f re La Havane aux deux autres, qu'elle juge quivalentes. Ses pr f rences entre les 3 destinations sont repr sent es par n'importe quelle fonction de paiement qui assigne le m me nombre New-York et Venise et un nombre plus lev La Havane.

5 Par exemple, on peut xer u(La Havane)=1 et u(New-York)=u(Venise)=0; ou u(La Havane)=10 et u(New-York)=u(Venise)=1; ou encore u(La Havane)=0 et u(New- York)=u(Venise)=-2,.. 4 CHAPITRE 1. INTRODUCTION. Exercice Le joueur 1 se soucie la fois de sa richesse et de la richesse du joueur 2 . Plus pr cis ment, la valeur qu'il attache une unit de sa propre richesse est la m me que celle qu'il attache deux unit s de la richesse du joueur 2 . Par exemple, il est indi rent entre une situation o sa richesse est 1 et celle du joueur 2 est 0, et une situation o sa richesse est 0 et celle du joueur 2 est 2. Comment sont ordonn es ses pr f rences entre les r sultats (1,4), (2,1) et (3,0), o la premi re composante est sa richesse et la seconde celle du joueur 2 ? Donner une fonction de paiement coh rente avec ces pr f rences. R ponses : (1, 4) (3, 0) (2, 1). u( 1 , 2 ) = 1 + 21 2 , ou u( 1 , 2 ) = 2 1 + 2 , ou plus g n ralement u( 1 , 2 ) =. 2t 1 + t 2 t R. Attention : Les pr f rences du joueur telles que pr sent es ici, ne contiennent qu'une information ORDINALE.

6 Elles nous apprennent que le joueur pr f re a b c mais ne nous disent pas "de combien" il pr f re a b ou si il "pr f re plus" a b que b c. La th orie du choix rationnel peut- tre expos e simplement : dans chaque situation, le joueur choisit parmi les actions disponibles celle qui est la meilleure selon ses pr f rences. En permettant que le joueurs soient indi rents entre plusieurs actions, la th orie des choix rationnels stipule que : l'action choisie par le preneur de d cision est au moins aussi bonne (au sens de ses pr f rences) que toutes les autres actions disponibles. Vous aurez not que cette th orie appara t galement dans la th orie conomique classique, du consommateur ou du producteur. Dans la th orie du consommateur, l'ensemble des actions possibles est l'ensemble des paniers de biens abordables ; alors que dans la th orie du producteur, il correspond tous les vecteurs input-outputpossibles et l'action a est pr f r e l'action b si a conduit un pro t plus important que b.

7 Jusqu'ici nous avons suppos que le preneur de d cision choisit une action et ne s'int resse qu' cette action. Cependant, en r alit , peu d'individus ont le luxe de contr ler l'ensemble des variables qui les a ectent. Si certaines sont la r sultante de d cisions d'autre individus, la prise de d cision devient plus complexe. L' tude de ces situations, qui peuvent tre mod lis es sous forme de jeux, sera l'objet de ce cours. Nous consid rerons dans un premier temps des situations dans lesquelles les joueurs ne peuvent pas s'allier ou s'engager sur une action vis- -vis de leur opposant, c'est- -dire des jeux non-coop ratifs. Table des mati res 1 Introduction 2. Qu'est-ce que la th orie des jeux ? .. 2. La th orie du choix rationnel .. 3. 2 La mod lisation des jeux 6. Jeux sous forme extensive .. 6. Repr sentation et d nition .. 6. Jeux en information parfaite .. 8. L'introduction du joueur Nature .. 11. Jeux en information imparfaite et ensemble d'information .. 12. Jeux sous forme strat gique (ou normale).

8 16. 3 Les concepts strat giques 22. Strat gies prudentes : La notion de maximin .. 22. La notion de dominance .. 24. limination successive des strat gies domin es .. 30. quilibre de Nash en strat gie pure .. 33. quilibre de Nash en strat gie mixte .. 36. 4 Les concepts d' quilibre dans les jeux s quentiels 39. quilibre parfait : l'algorithme de K hn .. 39. quilibre parfait en sous-jeux .. 46. quilibre Bayesian Parfait .. 50. Bibliographie : Introduction to Game Theory ; M. Osborne ; Oxford University Press Game Theory Online ; M. Jackson, Y. Shoham and K. Leyton-Brown ; YouTube 5. Chapitre 2. La mod lisation des jeux Dans ce chapitre nous aborderons les di rentes mani res de mod liser les jeux travers quelques exemples et d nitions. Les m thodes de r solution seront d taill es par la suite. N'essayez donc pas pour l'instant pr dire ce que les joueurs vont jouer mais uniquement de comprendre leur repr sentation ! A n de d crire ou de mod liser un jeu (c'est- -dire une situation d'interaction d cisionnelle).

9 Quatre l ments doivent tre pr cis s : l'ensemble des joueurs (ou preneurs de d cisions). les actions possibles pour chaque joueur les r gles du jeu sp ci ant notamment l'ordre dans lequel les joueurs jouent et quand le jeu se termine le r sultat du jeu pour chaque n possible et son implication en termes de "fonction de paiement" (pour cela il faut conna tre les pr f rences des joueurs). Jeux sous forme extensive La mod lisation sous forme extensive est un des moyens les plus simples de repr senter un jeu. Il s'agit d'un mod le o les joueurs choisissent s quentiellement leurs actions, jusqu'au moment o le jeu est d clar ni. Repr sentation et d nition Avant de d nir pr cis ment les di rentes composantes de cette mod lisation, commen ons par un exemple permettant de les illustrer. Exemple Un joueur en position de monopole, le "titulaire", est confront la possible entr e d'un challenger (le challenger peut, par exemple, tre une rme d sirant entrer sur un march r git par un monopole; un homme politique d sirant prendre le contr le d'un parti; ou un animal souhaitant entrer en comp tition pour obtenir le droit de s'accoupler 6.)

10 JEUX SOUS FORME EXTENSIVE 7. avec un de ses cong n res du sexe oppos ). Le challenger peut entrer ou non. Si il entre, le "titulaire" peut accepter ou se battre. Les r sultats possibles du jeux sont ainsi (Entrer, Accepter), (Entrer, Se battre) ou (Ne pas entrer). Les r gles du jeux sp ci ent par ailleurs que le challenger joue le premier et que le titulaire ne joue que si le challenger a jou "Entrer". Au d but d'un jeu s quentiel et apr s chaque s quence d' v nements, un joueur choisit une action. L'ensemble des actions disponibles pour un joueur ne doit pas n cessairement tre donn explicitement dans la description du jeu. Il su t que la description du jeu sp ci e les di rents r sultats et la s quentialit du jeu pour qu'on puisse en d duire l'ensemble des actions disponibles. Repr sentation graphique : Tout jeu sous forme extensive peut tre repr sent par un arbre (graphe connexe sans cycle) o . chaque n ud terminal correspond un r sultat du jeu chaque n ud non terminal est associ un joueur : arriv ce point du jeu, c'est.