Accueil |

Théorie des jeux

       

La Théorie des jeux est une branche des mathématiques, de la recherche opérationnelle et de l'économie. Elle considère des interactions formalisées par des structures incitatives, les "jeux". On étudie le comportement prévu et réel d'individus soumis à  des jeux, ainsi que les stratégies optimales. Des situations apparemment très différentes peuvent être représentées avec des structures d'incitation comparables, et constituant autant d'exemple d'un même jeu.

La théorie des jeux est très proche de l'économie en ce sens qu'elle cherche les stratégies rationnelles dans des situations o๠les gains d'un acteur dépendent non seulement de son comportement et des conditions de marché, mais aussi de celui des autres intervenants, lesquels peuvent poursuivre des objectifs différents ou contradictoires. On trouve aussi des applications en sciences politiques ou en stratégie militaire.

Les résultats peuvent être appliqués à  des divertissements (comme le jeu télévisé "Friend or Foe" sur une chaîne cà¢blée spécialisée au États-Unis, Game Show Network) ou à  des considérations plus poignantes (la crise des missiles à  Cuba ou la lutte contre le terrorisme). Albert W. Tucker a par exemple diffusé de nombreuses interprétations du dilemme du prisonnier dans la vie courante. Des biologistes ont utilisé la théorie des jeux pour comprendre et prévoir les résultats de l'évolution, en particulier la notion d'équilibre évolutionnairement stable introduit par John Maynard Smith dans son essais La théorie des jeux et l'évolution de la lutte (Game Theory and the Evolution of Fighting). Voir aussi sonlivre Evolution and the Theory of Games.

D'autres branches des mathématiques comme les probabilités ou les statistiques et la programmation linéaire sont couramment utilisés en conjonction avec la théorie des jeux pour étudier des situations.

Sommaire
1 Types de jeux et exemples
2 Représentations canoniques
3 Résolution d'un jeu à  somme nulle
4 La notion de stratégie et d'équilibre mixte
5 Jeu à  somme non-nulle
6 Gains et aversion au risque
7 Jeux de chiffres
8 Les jeux et l'histoire
9 Voir aussi
10 Liens extérieurs et références en anglais

Types de jeux et exemples

La théorie des jeux classifie les jeux en catégories qui déterminent quelles méthodes sont à  appliquer pour les résoudre -- et que signifie "résoudre" pour une catégorie. Les catégories les plus ordinaires sont :

Les jeux à  somme nulle sont tous les jeux o๠la somme des gains des joueurs est constante. à€ ce total près, leurs bénéfices sont toujours nuls et ce que gagne l'un est nécessairement perdu par un autre. Les échecs ou le poker sont des jeux à  somme nulle car les gains se font exactement aux dépends d'un autre. Les situations d'affaires, la vie politique ou le dilemme du prisonnier sont des jeux à  somme non-nulle car certaines issues sont profitables pour tous, ou dommageables pour tous. Il est plus facile d'étudier les jeux à  somme nulle ; on dispose de davantage de résultats théoriques.

Les jeux de Nim forment un cas particulier de jeu à  somme nulle, sans intervention du hasard et dans la plupart des cas à  nombre de situations finies.

[La définition anglophone précise que l'on peut ramener un jeu à  somme non-nulle à  un jeu à  somme nulle en ajoutant un joueur simplet, le "tableau", qui compense les pertes nettes des joueurs. Cette remarque est inappropriée : un joueur doit défendre ses intérêts dans la mesure de ses possibilités, cet ajout formel n'apporte rien.]

Représentations canoniques

Tous les jeux peuvent être représentés par un arbre, o๠chaque nÅ“ud est associé au joueur qui y décide. Chaque option est une branche. Un joueur peut ignorer à  quel nÅ“ud il se trouve si la part de l'historique qu'il connaît pour aboutir aux différents points est le même, si les options qui lui sont laissées sont identiques et si le mécanisme le prévoit. C'est par exemple le cas quand il hésite à  demander à  voir au Pocker : l'issue n'est pas la même selon la main qu'on lui cache, mais lui doit prendre une décision sans savoir à  quelle situation il est confronté. Les gains de tous sont associés aux terminaisons.

Dans le cas particulier d'un jeu à  deux joueurs, et si les différentes combinaisons compatibles de leurs actions définissent un ensemble fini de stratégie, alors on peut représenter le jeu sous une forme matricielle. Les notions d'action et de stratégie sont très différentes : une même stratégie pourra comporter deux actions opposées selon le comportement observable de l'autre joueur. On peut, avec un nombre réduit de stratégies, tenter de représenter avec une matrice un jeu à  trois ou quatre joueurs, mais cela pose souvent plus de problème d'interprétation et de lecture que ça n'apporte.

Le tableau à  double-entrée énumère sur chaque coté les stratégies possibles des joueurs respectifs. Dans la case à  la croisée de deux stratégies, on note le binà´me de gains des deux joueurs. C'est ce que l'on appelle (abusivement) la matrice de gains.

Si le jeu est à  somme nulle et à  deux joueurs, alors on peut ne noter que les gains du premier joueur : ceux du second sont directement opposés. Le tableau de gains se ramène alors effectivement à  une matrice.

Résolution d'un jeu à  somme nulle

1\\2 (A) (B) (C)
(a) 30 -10 20
(b) 10 20 -20

Les deux joueurs décident simultanément de leur stratégie. Le joueur peut se dire : << La stratégie (b) peut me faire perdre 20, et au plus gagner 20. En revanche, avec la stratégie (a) je peux gagner jusqu'à  30, et au pire perdre 10. >> De même, le joueur (2) aurait tendance à  opter pour la stratégie (C) -- il touche l'opposé des valeurs du tableau. Mais dans ce cas, le joueur 2 perd 20. Que se passe-t-il s'il anticipe le choix de 1 ? Il préfèrera faire (B) et gagner 10. Et si à  son tour le joueur 1 anticipe cette déviation et préfère faire (b) pour alors toucher 20 ?

La notion de stratégie et d'équilibre mixte

Aucune réponse ne paraît satisfaisante. John von Neumann est pourtant parvenu à  sortir de cet imbroglio à  l'aide des probabilités. Au lieu de décider fermement d'une action, chaque joueur associe à  chaque option une probabilité et tranche au hasard avec un processus aléatoire artefact. C'est le choix des probabilités qui doit maximiser le gain espéré indépendamment de la stratégie de l'adversaire. Cela revient à  se ramener à  un problème de programmation linéaire avec une solution unique pour chaque joueur dans tous les jeux à  deux joueurs et à  somme nulle.

Dans le cas ci-dessus, le joueur 1 hésitera entre (a) et (b) en choisissant (a) dans # cas sur # soit 57 % des cas. Le joueur n'optera jamais pour (A), mais oscillera entre (B) et (C) en choisissant (B) dans # cas sur #, soit 57 % des cas. Le joueur 1 pourra espérer un gain moyen à  chaque partie de #/#, soit 2,85.

Jeu à  somme non-nulle

Le cas le plus célèbre de jeu à  somme non-nulle est le dilemme du prisonnier, déjà  évoqué plus haut. Tout gain d'un joueur ne trahit pas nécessairement une perte pour l'autre. La plupart des situations réelles sont mieux décrites par un jeu à  somme non-nulle. Par exemple, un contrat d'affaires correspond à  une situation favorable aux deux parties, qui préfèrent avoir des garanties écrites. La plupart des jeux de société -- qui visent à  désigner un unique gagnant -- sont des jeux à  somme nulle.

Les jeux coopératifs regroupent toutes les situations o๠chaque intervenant peut communique librement avec tous les autres -- notamment, les joueurs sont libres de négocier pour influencer des décisions. Le Monopoly peut être un jeu coopératif, alors que le dilemme du prisonnier ou le jeu du rendez-vous ne le sont pas.

Les jeux en information complète regroupe tous les cas o๠toute l'information pertinente pour le jeu est observable par tous. Les échecs sont en information complète, le poker non. Les situations réelles sont rarement en informations parfaitement complète, et ce cas ne sert souvent qu'aux approximations confiantes.

Gains et aversion au risque

Dans l'exemple en stratégie mixte défini plus haut, les participants au jeu ont été considérés comme neutres au risque. Cela signifie qu'ils considèrent qu'avoir une chance sur deux d'obtenir 20 et une chance sur deux de ne rien avoir est équivalent à  obtenir 10. Cependant, la plupart des personnes sont averses au risque, et préfèrent les issues les plus sà»res -- et n'accepteraient un risque supplémentaire que contre une espérance de gain plus important. La théorie de l'utilité subjective espérée construit une mesure de l'utilité qui satisfasse toujours le critère de neutralité au risque, et corresponde donc à  un tableau de gains en stratégie mixte.

Un exemple de cette aversion au risque peut être remarqué au cours de jeux télévisés. Si, par exemple, on propose aux candidats soit une chance sur trois d'avoir 50 000 € soit 10 000 € à  coup sà»r, beaucoup préfèreront la garantie de changer leur ordinaire. Le revenu supplémentaire espéré qui est exigé pour compenser l'aversion au risque est appelé, en finance, la prime de risque

Jeux de chiffres

John Conway a mis en place une notation pour certains jeux et défini des opérations sur ces jeux, dans l'espoir d'étudier le Go. à€ partir d'associations surprenantes d'idée, il a isolé une sous-classe avec des propriétés numériques, et a abouti à  définir la classe très générale des nombres surréels.

Les jeux et l'histoire

Bien qu'ayant fait l'objet de résultats assez anciens, à  partir des travaux de Blaise Pascal sur la question des parties qui a donné une première intuition des probabilités et de l'espérance mathématique, et de son étonnant pari la théorie des jeux n'est devenue une branche importante des mathématiques qu'à  partir des années 1940, surtout après la publication en 1944 de La théorie des jeux et du comportement économique (The Theory of Games and Economic Behavior) par John von Neumann et Oskar Morgenstern. Cet ouvrage difficile détaillait la méthode vue plus haut de résolution des jeux à  somme nulle et à  deux joueurs vue plus haut.

Vers 1950, John Nash a été le premier à  présenter une définition d'une stratégie optimale pour un jeu à  plusieurs joueurs, dite équilibre de Nash. Ce résultat tardif génial a été raffiné par Reinhard Selten ; cela leur a valu le prix Nobel d'Économie en 1994 pour leurs travaux sur la théorie des jeux, avec John Harsanyi qui avait travaillé sur les jeux en information incomplète.

L'association entre jeu et nombre par Conway a été établie dans les années 1970.

Voir aussi

Jeux mathématiques, Intelligence artificielle, Paradoxe de Newcomb, Classification des jeux, Théorie combinatoire des jeux.

Liens extérieurs et références en anglais