Descriptif
Ce cours comporte deux parties reliées par un thème commun: les jeux !
La première partie est consacrée à la résolution de jeux solitaires ou à deux joueurs à l'aide de la théorie des graphes et de la programmation linéaire. Ces outils (graphes et PL), qui ont beaucoup d'autres utilisations, seront présentés avant d'être utilisés pour trouver des stratégies gagnantes dans plusieurs jeux: jeu de Marienbad, Sudoku, divers casse-tête, jeux à deux joueurs à somme nulle (concurrence)... Un projet s'appuyant sur le logiciel commercialisé Cplex illustrera le cours.
La deuxième partie du cours concerne la théorie des jeux. La théorie des jeux a pour objectif de développer les concepts aussi bien que les modèles formalisés en vue de l’analyse du conflit et de sa résolution. Les applications sont nombreuses : en Economie, politique, négociations mais aussi bien théorie de l’évolution et équilibres évolutionnistes. Seront abordés le modèle stratégique, le modèle extensif et quelques aspects du modèle coopératif. Nous définirons pour chacun des modèles les principaux concepts d’équilibre, les liens éventuels entre les modèles et nous donnons des éléments pour le calcul.
Bibliographie
- Van Damme « Stability and perfection of Nash equilibria » Springer- Verlag.
- Myerson « Game theory, analysis of conflict » Harvard University Press.
- Moulin « Théorie des jeux » PUF.
- M.J. Osborne et A. Rubinstein « A course in Game Theory », MIT University Press
- Graph Theory, Bondy, Adrian and Murty, U.S.R.. Graduate Texts in Mathematics, Vol. 244
Spinger Ed., 2008.
Objectifs pédagogiques
- Modélisation de problèmes (graphes ou programmes en nombres entiers)
- Initiation à la théorie des jeux
- Réalisation concrète de problèmes via l'implémentation d'un projet
effectifs minimal / maximal:
6/60Diplôme(s) concerné(s)
- Master 1 Mathématiques et Applications - site Orsay
- Diplôme d'Ingénieur de l'Ecole Nationale Supérieure de Techniques Avancées
Parcours de rattachement
Pour les étudiants du diplôme Master 1 Mathématiques et Applications - site Orsay
Programmation linéaire Programmation en nombres entiers Manipulation basique de graphes
Pour les étudiants du diplôme Diplôme d'Ingénieur de l'Ecole Nationale Supérieure de Techniques Avancées
MAP-RO
Format des notes
Numérique sur 20Littérale/grade européenPour les étudiants du diplôme Diplôme d'Ingénieur de l'Ecole Nationale Supérieure de Techniques Avancées
Vos modalités d'acquisition :
F=note finale, PR=Projet, E=Examen final - Session 1 : F=0,5PR+0,5E - Session 2 : F=1E
Le rattrapage est autorisé (Max entre les deux notes écrêté à une note seuil)- le rattrapage est obligatoire si :
- Note initiale < 6
- le rattrapage peut être demandé par l'étudiant si :
- 6 ≤ note initiale < 10
- Crédits ECTS acquis : 3.5 ECTS
- Scientifique acquis : 3.5
Le coefficient de l'UE est : 3.5
La note obtenue rentre dans le calcul de votre GPA.
L'UE est évaluée par les étudiants.
Pour les étudiants du diplôme Master 1 Mathématiques et Applications - site Orsay
Vos modalités d'acquisition :
F=note finale, PR=Projet, E=Examen final - Session 1 : F=0,5PR+0,5E - Session 2 : F=1E
Le rattrapage est autorisé (Note de rattrapage conservée)- le rattrapage est obligatoire si :
- Note initiale < 7
- le rattrapage peut être demandé par l'étudiant si :
- 7 ≤ note initiale < 10
- Crédits ECTS acquis : 3.5 ECTS
Le coefficient de l'UE est : 3.5
La note obtenue rentre dans le calcul de votre GPA.
L'UE est évaluée par les étudiants.
Programme détaillé
Bloc de module (1/2 journée) | Résolution de jeux par la PL. Graphes, fonction de Grundy. Résolution de jeux par les graphes. Jeux de Nim. |
||
Bloc de module (1/2 journée) | Projet. Rappel de programmation linéaire et dualité. Exercices. Présentation du projet. |
||
Bloc de module (1/2 journée) | Théorie des jeux. Jeux à deux joueurs à somme nulle. Stratégie mixte, théorème de Von Neumann, Equilibre de Nash. |
||
Bloc de module (1/2 journée) en salle info | Rappel de programmation en nombres entiers. Exercices. Poursuite du projet. |
||
Bloc de module (1/2 journée) | Théorie des jeux. Equilibre de Nash suite. Existence. Jeux bimatriciels. Calcul des équilibres. Jeux sous forme extensive à information parfaite. Rationalité séquentielle. Equilibre sous-jeux-parfait. |
||
Bloc de module (1/2 journée) en salle info | Poursuite du projet. | ||
Petite classe | Graphes. Exercices. | ||
TD en salle info | Suite du projet. | ||
Bloc de module (1/2 journée) | Graphes planaires. Théorème des quatre couleurs. Coloration de graphes. | ||
Bloc de module (1/2 journée) | Stratégies mixtes. Jeux matriciels. Calcul des stratégies optimales. Jeux bimatriciels . Calcul des équilibres de Nash. | ||
Bloc de module (1/2 journée) | Jeux sous forme extensive. Forme normale associée. Stratégies de comportement. Théorème de Kuhn. Rationalité séquentielle. Equilibre Bayésien parfait faible, Equilibre sous-jeux-parfait. | ||
Bloc de module (1/2 journée) en salle info | Soutenance des projets. | ||
Contrôle | Examen écrit |