Calendrier
10 séances de cours-TD le vendredi de 08h15
à
10h15 en salle M 0.3. Première séance vendredi 16 septembre. Pas
de cours les 4 et 11 novembre.
Contrôle continu : Deux interrogations de 40mn, un examen final.
1ère interrogation le 14 octobre
2ème interrogation le 2 décembre.
Examen vendredi 16 décembre.
de rattrapage lundi 16 janvier à 10h. Séance de soutien jeudi 12 janvier à 10h.
Présentation.
Progression du cours :
1. Introduction
et exemples.
Jeux sous forme normale : ensemble de joueurs J={1,..,n}, 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.
Représentation matricielle dans le cas de deux joueurs. Exemple avec le
dilemme du prisonnier, stratégie optimale.
Jeux à deux joueurs à somme nulle, exemple : l'écu caché ;
représentation matricielle.
Jeux sous forme extensive (séquentielle) à information parfaite (ex.:
morpion) ou
imparfaite. Exemple : admission au club d'un nouveau membre soumis au
vote.
2. Déf. Equilibre
de Nash d'un jeu sous forme normale, stratégie regrétée, meilleure
réponse, exemple.
Identification des stratégies et mise sous forme normale du jeu
"Morpion" (information parfaite), "Nouveau membre pour le club" d'abord
avec vote public (information parfaite) puis avec vote à bulletin
secret (information imparfaite), équilibre explicite pour ce dernier
jeu. Ex. 2-3 de la feuille de TD 1.
3. Déf. gain
garanti optimal d'un joueur, stratégies prudentes, exemple de calcul
pour les ex. 6-7 de la feuille 1, stratégie strictement dominée. Ex. 4,
7, 6 de la feuille de TD 1.
4. Jeux à deux
joueurs à somme nulle : le gain du joueur 1 est la perte du joueur 2 ;
g_=gain garanti optimal du joueur 1, g-=majoration
garantie optimale de la perte du joueur 2. Garantie sur un objectif de
gain du joueur 1 ou de majoration de perte du joueur 2 ; g_≤g-.
Equilibres du jeu à deux joueurs à somme nulle : regret de J1 si
g(x,y)<g-, regret de J2 si g(x,y)>g_ ; pas d'équilibre
si g_<g-, dans le cas contraire les équilibre sont les
couples de stratégies prudentes.
Ex. 1 (calcul du gain garanti optimal) et 2 de la feuille de TD 2.
5. TD feuille1
ex8-9, feuille 2 ex1 (meilleures réponses de J2 aux stratégies de J1)
et 3 1ère matrice (discussion des stratégies strictement dominées).
Interrogation 50mn.
6. TD Correction
des ex. 1 et 3 de l'interro, feuille 2 ex 3 3ème matrice (discussion
suivant a des stratégies prudentes)
Cours : théorème de Sion pour l'existence d'un équilibre (point selle),
explication des hypothèses ; vérification des hypothèses avec les ex. 4
et 5 de la feuille 2.
7.
TD fin ex. 4, ex5 pour g(x,y)=x+y-1 (discussion des hypothèses du
théorème de Sion, les meilleures réponses à une stratégie strictement
dominante donnent les équilibres).
Cours : Elimination d'un ensemble de stratégies dominées au sens large
: conséquence sur g_ , g- , les stratégies prudentes, les
équilibres. Exemple avec l'ex.2 de l'interrogation
de nov. 2010.
Introduction
aux stratégies mixtes : exemple avec un jeu matriciel sans équilibre
répété un nombre N de fois, gain moyen, choix des stratégies par l'un
des joueurs suivant une loi de probablité, gain moyen garanti et
meilleure réponse de l'autre joueur, équilibre avec un couple de
stratégies mixtes.
8. Cours : extension mixte d'un jeu
matriciel : stratégies mixtes (p1,...,pm), piqj≈fréquence
d'apparition du couple (Li,Cj) lorsque le jeu est répété un grand
nombre de fois et que J1 et J2 jouent selon les stratégies mixtes (pi)
et (qj), gain moyen (lorsque le jeu est répété un grand
nombre de fois) ≈ espérance de gain G((pi),(qj)).
Recherche d'équilibres en stratégie mixte avec l'exercice 5 de la
feuille 3 (représentation graphique de inf(q∈[0,1])G(p,q)
comme fonction de p∈[0,1]).
Δm={stratégies mixtes (p1,...,pm)} est
une partie convexe fermée bornée de Rm
dont les coins sont les stratégies pures (0,...,1,...,0) (1 en position
i). Le théorème de Sion s'applique et donne l'existence d'au moins un
équilibre pour l'extension mixte du jeu ; en particulier G_=G-.
TD feuille 3 ex.4.
9.
Recherche des équilibres de l'extension mixte d'un jeu matriciel :
Rappel : existence d'une valeur ; recherche des stratégies mixtes
prudentes. Soient C une partie convexe fermée bornée de Rn,
S l'ensemble des coins de C et f: Rn→R
une fonction affine ; alors le max de f sur C est égal au max de f sur
S et l'ensemble des points de C où f est maximale est la partie convexe
de C dont les coins sont les points de S où f est maximale. Soient
maintenant f1,f2,...,fn sont des
fonctions affines Rn→R et notons f la fonction min(f1,f2,...,fn)
; alors les hyperplans d'équation fi=fj pour
certains couples (i,j) délimitent les morceaux Ck de C où f
coïncide avec fk (en particulier f est affine par morceaux),
le max de f sur C est le plus grand des max des fk sur Ck.
Les Ck
sont des parties convexes fermées bornées ; leurs coins sont formés des
coins de C, d'intersections de n hyperplans de la forme fi=fj,
d'intersection de ces hyperplans avec le bord de C (Cf les exemples
dans les notes
de cours ou cet
exemple de recherche algorithmique des stratégies prudentes). La
complexité de la méthode augmente avec n !
TD
: Feuille 3 ex.7 avec plusieurs méthodes (recherche des stratégies
mixtes prudentes de J1 connaissant la valeur de l'extension mixte du
jeu, parmis les meilleures réponses à la stratégie mixte prudente de
J2).
10. Stratégies
pures dominée dans l'extension mixte d'un jeu matriciel, élimination.
TD feuille 3 ex7 : la ligne 2 est strictement dominée dans l'extension
mixte du jeu. Ex8, 10 + recherche des stratégies mixtes prudentes de J2.
Interrogation (≥40mn)
Séance du 12 janvier.
Rappel des fondamentaux pour un jeu à deux joueurs à somme nulle :
meilleure réponse à une stratégie de l'autre joueur, équilibre, plus
mauvais gain en jouant x, stratégie prudente de J1, gain garanti
optimal, plus grande perte en jouant y, stratégie prudente de J2,
majoration optimale de la perte, équilibres en terme de couple de
stratégies prudentes, lien entre stratégies prudentes et meilleures
réponses lorsque le jeu admet un équilibre.
Correction des exercices 2,3 (avec en complément les stratégies mixtes prudentes de J2) et 4 de l'examen du 16 décembre.
|
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 23 sept 11).
feuille
de TD 2 (7 oct. 11)
feuille de TD 3 (18 nov. 11) Corrigé
des exercices 5,7-10 ; deux
autres méthodes pour l'exercice 7 ; corrigé
des exercices 6 et 11
(numérotés 1 et 3)
Notes
de cours 2 (jeux à deux joueurs à somme nulle)
Notes
de cours 3 (extension mixte d'un jeu matriciel)
Contrôle
des
connaissances :
1ère interrogation (50mn) le 14
octobre. Barème : 5.5pts pour l'ex.1, 3.5 pour l'ex.2, 4 pour l'ex.3 ; note sur 10.
2ème interrogation (40mn) le 2 décembre et un
corrigé. Barème : 1pt pour chaque question, note=1/2*note_ex.1+9/7*note_ex2 ; note sur 10.
Examen (1h30) le 16 décembre 8h15. Barème : voir Notes CC au 6 jan.
Rattrapage (1h30) le 16 janvier. Variante du 20 janvier. Barème : voir Notes CC au 23 jan.
Notes CC au 14 décembre 2011
Notes CC au 6 jan 2012. Barème : Int1 et int2 sur 10pts, examen sur 20pts, note CC=0.6*(int1+int2)+0.4*exam.
Notes CC au 23 jan 2012. Barème : comme ci-dessus mais avec max{examen, rattrapage} en place de la note d'examen
Archives
2010-11.
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é, 16 septembre 2011
|