Calendrier de l'UFR Sciences
Cours-TD le vendredi de 9h à 12h15 en salle M0-3 (20h de
cours, 10h de TD par Ingo Washkies)
Première séance vendredi 14 sept.
Contrôle continu : Deux interrogations de 40mn, un examen final. note CC=0.6*(int1+int2)+0.4*exam.
1ère interrogation le 26 oct.
2ème interrogation le 30 nov.
Examen mardi 15 janvier (Cf page du L2Mass). Séance de révision lundi 14 janvier à 15h30 en salle M0-3.
Présentation.
Progression du cours :
1. (14 sept.)
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 "Sortie de Paul et Jacqueline" (cf ex9 de la feuille 1), jeu initial, extension mixte du
jeu, jeu avec l'avis d'un tiers tirant au sort la sortie ; notion de
meilleure réponse, équilibre, comparaison des gains suivant les
différents scénarios.
Jeux sous forme extensive (jeu séquentiel), information parfaite ou
imparfaite. Ex "pierre-papier-ciseau" biaisé
Lecture : La notice de Wikipedia sur la théorie des jeux
2. (21 sept)
Recherche des équilibres via la correspondance des meilleures réponses
pour l'extension mixte du jeu "Sortie de Paul et Jacqueline".
Notion de stratégie strictement dominée, stratégie prudente ; exemple
avec le "dilemme du prisonnier"
3. (28 sept) Autre
exemple de jeu sous forme extensive : "admission au club d'un nouveau
membre", jeu informel, trois scénarios donnant un équilibre ou pas,
arbre du jeu, identification des stratégies en jeu (version économe)
dans les 3 scénarios.
Extension mixte d'un jeu, théorèmes d'existence d'équilibre (début),
jeu à deux joueurs à somme nulle, représentation matricielle pour un
jeu fini, extension mixte du jeu.
Ex. d'un jeu fini sans équilibre, équilibre de l'extension mixte.
Lecture : R. Myerson, Nash equilibrium and the history of economic theory
4. (5 oct.)
Correspondance des meilleures réponses d'un jeu à n joueurs, équilibre
du jeu comme point fixe, théorème d'existence de Kakutami, discussion
des hypothèses : convexité, compacité, convexité de l'ensemble des
stratégies mixtes associé à un ensemble fini de stratégies ; ex.
extension mixte du jeu "Sortie de Paul et Jacqueline".
Jeux à deux joueurs à somme nulle : gain garanti optimal, majoration
optimale de la perte, stratégies prudentes, discussion : g_≤g-,
(x,y) est regrétée par l'un des joueur si g_<g- ou si x
ou y n'est pas prudente.
Lectures : le théorème de Kakutami sur Wikipedia
5. (12 oct.) Suite jeux à 2 joueurs à somme nulle : Lorsque g_=g-,
les équilibres sont exactement les couples de stratégies prudentes.
Hypothèses sur X,Y et g(,) garantissant l'existence de stratégies
prudentes, exemples de jeu où aucune stratégie n'est prudente, où toutes
les stratégies sont prudentes bien que strictement dominées (cf f2 ex4).
Valeur du jeu, point selle, théorème du minimax de von Neumann pour les
extensions mixtes des jeux matriciels, théorème de Sion, discussion des
hypothèses du théorème avec l'ex. 4 de la feuille 2. Début ex. 5.
Lectures : points selle sur wikipedia,
6. (19 oct.)
(1h30) Retour sur f2 ex2 (TD), fin f2 ex5 : min ou max d'une fonction définie
par morceaux, comparaison extrémum local et valeurs au bord du domaine
de définition.
Avancement sur la feuille de TD : f2 ex1-5.
7. (26 oct.) (1h30) Recherche des équilibres de l'extension mixte d'un jeu matriciel à
somme nulle : extrémum d'une fonction affine par morceaux définie sur
un polytope convexe donné par un système d'inéquations (cf f3 ex6).
Interrogation 1h.
8. (9 nov.) (1h30) Suite du cours du 26 oct : 1er exemple des notes de cours 3 §3
(recherche par le dessin et algorithmiquement par le calcul (calcul des
coins des morceaux où le plus mauvais gain de J1 est affine et des
valeurs du plus mauvais gain en ces coins) des stratégies mixtes
prudentes de J1, recherche des stratégies mixtes prudentes de J2
connaissant la valeur du jeu ou connaissant une stratégie mixte
prudente de J1).
Avancement en TD (5h30 jusque maintenant) : f2 ex 6,7,8
9a (16 nov.) Uniquement TD (feuille 3) de 9h30 à 12h : f3 ex 5,7,8
9 (23 nov.) (1h30) Simplification du jeu pour la recherche des equilibres de l'extension mixte : élimination des stratégies pures strictt
dominées dans l'extension mixte du jeu, stratégies pures dominées au
sens large, meilleures réponses à une stratégie mixte prudente de
l'autre joueur.
Exemple des notes de cours 3 §4
: le jeu se ramène à (2 6 0 \\ 4 2 8) ; (1/3,2/3) est la seule
stratégie mixte prudente de J1 pour le nouveau jeu ; les meilleures
réponses de J2 à (1/3,2/3) sont les (q,1-q,0) ; reste à chercher parmis
ces meilleures réponses les stratégies mixtes prudentes de J2.
Avancement en TD : f3 ex 9,10
10 (30 nov.) 9h-11h Suite du cours
11h : Interrogation 45mn. Au programme : recherche des équilibres de l'extension mixte d'un jeu matriciel.
11 (7 dec.) TD f3 ex 6 + min{x-y+2, x+y+1, -2x+3} dans le carré 0≤x≤1, 0≤y≤1
Cours (1h) : biblio, discussion arbre d'un jeu et forme normale, ex1 de l'int2 de dec11.
12 (14jan. 15h30) Révision : stratégies dominées dans l'extension mixte du jeu, meilleures réponses, correction de l'interro du 30 nov.
|
Documents de
cours :
Les documents imprimés sont disponibles sur demande (Labo Dieudonné
(Bâtiment de recherche Math), bureau 620)
Feuille de TD 1
Feuille de TD 2
Correction de la 1ère interrogation de 2011-12
Feuille de TD 3 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)
Contrôle
des
connaissances :
Interrogation du 26 octobre et un corrigé. Notes détaillées.
Interrogation du 30 novembre et un corrigé (mise à jour 14jan13-12h). Notes détaillées
Examen du 15 janvier et un corrigé. Notes détaillées.
Archives
2011-12.
Page du cours de C. Pauly en L1Mass (sem2 2012-13)
Lectures :
[1] Ken Binmore, Jeux et théorie des jeux, traduit de l'anglais, De
Boeck Université (1999), disponible à la BU St Jean d'Angely. Extraits sur Google Books.
Version anglaise (K. Binmore, Playing for real, Oxford Univ. Press (2007) disponible à la BU sciences
[2] M. Yildizoglu, Introduction à la
théorie des jeux, chap. 1,2,3I-II, Dunod 2003, disponible à la BU St Jean d'Angely, consultable en ligne sur le site de la BU.
Egalement
[3] H. Moulin, Fondation
de la théorie
des jeux,
Herman 1979, disponible à la BU sciences.
[4] H.W. Kuhn, Lectures on the
theory of games, Annals of Math. Studies 37
(2003).
Pour aller plus loin : (jeux à somme non nulle, plus que deux joueurs,
jeux répétés, information incomplète, etc.) :
[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é, 2 octobre 2012
|