Option théorie des jeux en L2Mass

Jeux à deux joueurs à somme nulle, extension mixte des jeux matriciels.

Présentation :
Pour une classe de jeux (dits à information complète), chaque joueur dispose d'un ensemble de stratégies, connaît les stratégies des autres joueurs et le paiement que recevra chaque joueur une fois choisie les stratégies de chacun. Chaque joueur choisit alors indépendamment et en secret sa stratégie (le jeu est dit non-coopératif). A l'issue du jeu, les stratégies choisies par chaque joueur sont dévoilées et les paiements distribués.
La théorie des jeux vise alors d'une part à déterminer rationnellement le choix que devrait faire un joueur particulier pour optimiser son gain, d'autre part à dire s'il existe des situations d'équilibre, c'est à dire des situations où aucun joueur ne regrettera a posteriori son choix. La notion même de choix optimal n'est pas complètement évidente comme le montre cet exemple.
La théorie des jeux déborde largement de ce cadre : Que se passe t-il lorsque le jeu est répété un grand nombre de fois et qu'on ne s'intéresse qu'au gain moyen de chaque joueur ? Que se passe t-il si l'information dont dispose chaque joueur sur le paiement des autres joueurs à l'issue du jeu est incomplète ?
Dans ce cours(-TD) nous étudierons les jeux à deux joueurs et à somme nulle (le gain de chaque joueur est exactement l'opposé du gain de l'autre joueur). Nous proposerons autant que possible les algorithmes conduisant aux solutions.


Contenu mathématique : borne supérieure ou élément maximal d'un ensemble de nombres réels, certains d'entre eux dépendant éventuellement d'un paramètre (discussion suivant la valeur du paramètre), ou d'une fonction à valeurs réelles dépendant éventuellement d'un paramètre ; utilisation d'un tableau de variation ; point selle d'une fonction de deux variables ; enveloppe convexe dans R^n d'un ensemble fini de points, minimum et maximum d'une fonction affine à valeurs réelles ou d'une fonction convexe, définie sur l'enveloppe convexe d'un ensemble fini de points ; application affine par morceaux donnée comme sup ou inf d'une famille finie d'applications affines à valeurs réelles, définies sur l'enveloppe convexe d'un ensemble fini de points ; maximum et minimum d'une telle fonction, interprétation en terme de programmation linéaire ; représentation graphique en dimension <=2.


Contenu appliqué : modélisation d'un jeu à deux joueurs par les ensembles de stratégies et la fonction de paiement de chaque joueur ("forme normale"), notion de stratégie prudente, gain garanti optimal, meilleure réponse à une stratégie donnée de l'autre joueur, regret, équilibre de Nash, stratégie dominée, comparaison du jeu après élimination des stratégies dominées avec le jeu initial, extension mixte d'un jeu (choix par les joueurs d'une mesure de probabilité sur leurs ensembles de stratégies et espérance de gain associée), discussion des stratégies dominées dans l'extension mixte du jeu


Page du cours en 2011-12


Lectures :
La notice de wikipedia (en).
Ken Binmore, Jeux et théorie des jeux, traduit de l'anglais, De Boeck Université (1999), disponible à la BU St Jean d'Angely.  Extraits via GoogleBooks.


Un jeu comme un autre.
Le général A, à la tête de 4 compagnies, veut prendre une ville défendue par le général B, à la tête de 5 compagnies. Deux routes mènent à cette ville. Le général A lancera un certain nombre de compagnies sur la première route et le reste sur la seconde route. Le général B défendra sa ville en répartissant au mieux ses compagnies sur les deux routes. L'issue sera victorieuse pour le général A si sur l'une des routes ses forces seront strictement supérieures en nombre. Chacun connaît l'état des forces de son adversaire mais les mouvements des uns et des autres restent cachés.
Comment le général A doit-il répartir ses forces pour prendre la ville ou, à tout le moins, mettre le maximum de chance de son côté ?