Calendrier
10 séances de cours-TD le vendredi de 08h00
à
10h00 en salle M 0.3. Première séance vendredi 17 septembre.
Les
cours-td des
vendredi 1 et 22 octobre sont
reportés.
vendredi 5 novembre : cours-TD de 8h à 11h
Mardi 9 novembre : cours-TD de 10h15 à 11h15
1ère interrogation (1h) mardi 9 novembre à 14h, amphi de chimie
2ème interrogation (1h30) mardi 7 décembre à 13h30, amphi de chimie
à rendre avant le 10 janvier : sujet transmis par mail.
Présentation.
Progression du cours :
1.
Plusieurs types de jeux.
Jeux sous forme normale : ensemble de stratégies Xi et
fonction de gain gi:X1x...xXn → R du
joueur i, 1≤i≤n. Non coopératif : l'objectif du joueur i est de
maximiser gi.
Information complète : chaque joueur connaît toutes les fonctions gi.
Equilibre (de Nash) = choix de stratégies non regrété à postériori par
les joueurs. Exemples.
Jeux sous forme extensive : arbre du jeux (actions successives des
différents joueurs, un joueur à la fois). Information parfaite ou
imparfaite, identification des stratégies, mise sous forme normale.
Exemple avec le jeu Pierre-papier-ciseaux.
2. Mise sous forme
normale du jeu Pierre-papier-ciseaux biaisé. Recherche des équilibres.
Meilleures réponses du joueur i à un choix de stratégies des autres
joueurs.
Exemple : deux marchands sur une longue plage (sur le segment [0,1]).
3.Stratégies
dominées, strictement dominées, exemple avec le dilemme des
prisonniers, avec les deux marchands. On ne modifie pas les équilibres
en enlevant les startégies strict. dominées. Qu'en est-il avec les
stratégies dominées au sens large ?
Stratégies prudentes, exemple d'équilibre non prudent.
Gain garanti optimal, caractérisation. Une stratégie du joueur i est
prudente si elle lui garantit son gain garanti optimal.
4. Solution à la
question du cours 3.
Jeux à deux joueurs à somme nulle : gain du joueur 1 interprété comme
perte du joueur 2. Majoration optimale de la perte du joueur 2,
caractérisation.
(x0,y0) est un équilibre ssi le gain garanti
optimal du joueur 1 égale la majoration optimale de la perte du joueur
2 (la valeur commune est applée valeur du jeu) et si (x0,y0)
est un couple de startégies prudentes, auquel cas g1(x0,y0)
est égal à la valeur du jeu. Exemple avec l'ex.1 de la feuille 1 de
2009-10.
5.
Recherche de stratégies prudentes, regret, équilibres avec les ex 1,2,3
de la feuille 1 de 2009-10. Analyse du regret avec pour seule
information le gain en le couple de stratégies choisies, le gain
garanti optimal et la majoration optimale de la perte.
Elimination des stratégies dominées, ex 7
de la feuille 1 de 2009-10.
6. (3h) Théorème de
Sion sur l'existence d'un équilibre pour un jeu à deux joueurs à somme
nulle. Commentaires sur les hypothèses : parties convexes fermées
bornées de Rn. Cas où les ensembles de stratégies des
joueurs sont des parties de R. Illustration avec les ex. 5 et 6 de la
feuille 1 de 2009-10, recherche de la valeur (si elle existe) et des
stratégies prudentes de chaque joueur.
7.
Introduction aux stratégies mixtes d'un jeu matriciel par l'exemple (cf
exemple des notes de cours 3 p3) : analyse de la meilleure réponse du
joueur 2 à une stratégie donnée du joueur 1 puis à la stratégie mixte
(1/2,1/2) du joueur 1 puis à la stratégie mixte (1/3,2/3) du joueur 1.
Définition de l'extension mixte d'un jeu matriciel ; vérification des
hypothèses du théorème de Sion.
8. Recherche des
équilibres en stratégies mixtes d'un jeu matriciel : minimum ou maximum
d'une fonction affine sur un domaine convexe fermé borné en fonction
des valeurs prises en les coins du domaine. Calcul de l'équilibre de
l'exemple du cours 7.
9. Simplification
de la recherche des équilibres en stratégies mixtes : stratégies pures
dominées, meilleures réponses à une
stratégie mixte optimale, exemple avec la matrice de l'ex 7 de la
feuille 3.
10. (1h30)
Recherche des stratégies pures dominées dans l'extension mixte d'un jeu
matriciel, interprétation graphique lorsque l'autre joueur n'a que deux
stratégies pures, élimination. Exemple avec les ex. 7,8 de la feuille 3
et avec le dernier exemple des notes de cours.
|
Documents de
cours :
Les documents imprimés sont disponibles sur demande (Labo Dieudonné
(Bâtiment de recherche Math), bureau 620)
feuille de TD 1 (mise à jour 4 nov 10).
feuille de TD 2 (5 nov 10)
feuille de TD 3. Un
corrigé des exercices 5 à 9 ; deux
autres méthodes pour l'exercice 6.
Notes de cours 2 (jeux à deux joueurs
à somme nulle) et notes de cours 3
(extension mixte d'un jeu matriciel).
Deux outils (WIMS) de calcul en ligne : résolution de système d'équations linéaires et multiplication de matrices.
Contrôle
des
connaissances :
Interrogation du 9 novembre 2010 et un corrigé.
Interrogation du 7 décembre 2010 et un
corrigé.
Barème de l'interrogation : ex1 sur 9, ex2 sur 8.5, ex3 sur 6.5, note=ex1*7/9+ex2+ex3*9/6.5.
Devoir du 20 déc. : sujet no 1, un corrigé des devoirs no 1 et 2, un corrigé très succint du devoir no 3. Recherche algorithmique des stratégies mixtes prudentes du devoir 1.
Barème de notation du
devoir : 5 pts pour l'avancement dans le sujet, 5 pts pour la précision
des mathématiques, 5 pts pour la rédaction et la rigueur de
raisonnement.
Notes détaillées (anonymes).
Archives
2009-10.
Lectures :
[1] H. Moulin, Fondation
de la théorie
des jeux,
Herman 1979, disponible à la BU sciences.
[2] H.W. Kuhn, Lectures on the
theory of games, Annals of Math. Studies 37
(2003).
[3] Ken Binmore, Jeux et théorie des jeux, traduit de l'anglais, De Boeck Université (1999), disponible à la BU St Jean d'Angely.
Pour aller plus loin : (jeux à somme non nulle, plus que deux joueurs,
jeux répétés, information incomplète, etc.) :
[3] M. Yildizoglu, Introduction à la
théorie des jeux, Dunod 2003, disponible à la BU St Jean d'Angely.
[4] G. Giraud, La théorie des jeux,
Champs
Université, Flamarion 2000.
[5] S. Sorin, A first course on zero-sum repeated games, Mathématiques et Applications, 37, Springer (2002).
F.X. Dehon,
Laboratoire J.A. Dieudonné, 25 août 2008
|