Détails du cours MAE41

Introduction to discrete optimization

Cette page est essentiellement destinée aux enseignants et regroupe toutes les informations nécessaires à la gestion d'un cours ENSTA.

Identité du cours

Sigle : MAE41
Titre français : Jeux, graphes et R.O.
Titre anglais : Introduction to discrete optimization
Méta infos : modifiée le : 21/03/2017   par : mcosta   Nb de visiteurs : 11   annee : 2A      periode : 1      Rattachement/module : ModEl      unités : 2      ECTS : 3      type : unknown     
ouvert : Oui     modif. autorisée : Oui     email auto. au responsable : Oui     à évaluer : Oui     en ligne : Non    
domaine ParisTech : 1,1b    

Equipe pédagogique

Responsable (login) :
Professeur principal :
Professeurs participants : Marie-Christine COSTA,    Rida LARAKI,    Alain FAYE,   
Maitres de conférences : Arnaud LAZARE,   

Contenu

a pour prérequis : MAP-RO1 ou Notions de programmation linéaire (dualité) et quelques
définitions de graphes.
Mise à niveau individuelle assez facile.
est prérequis pour : Utile pour les cours OROC-RO et pour des masters recherche opérationnelle
(MPRO) ou informatique ou optimisation ou économie ou finance.
Objectifs : Attention, cette page est la description du cours pour l'année 2014/2015, elle sera mise à jour ultérieurement. 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. Voir la présentation du cours PresMAE402010.pdf Le recouvrement avec le cours A0204 portera seulement sur une séance de programmation linéaire mais avec utilisation d'un logiciel. Ce cours peut être couplé avec n'importe quel autre cours. Par exemple avec: EAE20 Economie de l'environnement INE10 Principes des langages de programmation MAE10 Modèles stochastiques pour la finance EAE10 Management, stratégie industrielle et innovation ESE40 Morphologie mathématique MAE61 Apprentissage statistique ou tout autre module électif du créneau ME2. Ce cours est fortement recommandé pour ceux qui suivront la filière OROC (Optimisation, Recherche opérationnelle, commande) l'an prochain.
Mots clés : théorie des jeux, jeux à 2 joueurs, graphes, programmation linéaire,
modélisation
Objectives :
Keywords :
Supports :
Liens : http://uma.ensta.fr/files/mcosta/cours/PresMAE402010.pdf, http://www.roadef.org, http://www.ensta.fr/~diam/ro/,
Biblio : - 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.
Contrôle : Examen écrit + projet
Document autorisés: polycopié du cours et notes manuscrites. Aucun livre.

Besoins particuliers et remarques éventuelles

Moyens :
Commentaires :

Séances

lun. 13 mars 2017   - 13:30 à 17:00 : Bloc de Module (1/2 journée) (MOD)
programme : Résolution de jeux par la PL. Graphes, fonction de Grundy. Résolution de jeux par les graphes. Jeux de Nim.
besoin : Vidéo,
Intervenants : Marie-Christine COSTA,
lun. 20 mars 2017   - 9:00 à 12:30 : Bloc de Module (1/2 journée) (MOD)
programme : Projet. Rappel de programmation linéaire et dualité. Exercices. Présentation du projet.
besoin :
Intervenants : Alain FAYE,
jeu. 23 mars 2017   - 9 à 12:30 : Bloc de Module (1/2 journée) (MOD)
programme : Théorie des jeux. Jeux à deux joueurs à somme nulle. Stratégie mixte, théorème de Von Neumann, Equilibre de Nash.
besoin : Vidéo,
Intervenants : Marie-Christine COSTA,
lun. 27 mars 2017   - 09:00 à 12:30 : Bloc de Module en salle Info (MODI)
programme : Rappel de programmation en nombres entiers. Exercices. Poursuite du projet.
besoin : Vidéo,
Intervenants : Alain FAYE,
jeu. 30 mars 2017   - 9:30 à 12:45 : Bloc de Module (1/2 journée) (MOD)
programme : 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.
besoin : Vidéo,
Intervenants : Rida LARAKI,
lun. 03 avril 2017   - 09: 00 à 12:30 : Bloc de Module en salle Info (MODI)
programme : Poursuite du projet.
besoin : Vidéo,
Intervenants : Alain FAYE,
jeu. 06 avril 2017   - 9:00 à 10:45 : Petite Classe (PC)
programme : Graphes. Exercices.
besoin : Vidéo,
Intervenants : Arnaud LAZARE,
jeu. 06 avril 2017   - 11:00 à 12:30 : TD en salle info (TD)
programme : Suite du projet.
besoin :
Intervenants : Arnaud LAZARE,
jeu. 20 avril 2017   - 09:00 à 12:30 : Bloc de Module (1/2 journée) (MOD)
programme : Graphes planaires. Théorème des quatre couleurs. Coloration de graphes.
besoin :
Intervenants : Marie-Christine COSTA,
lun. 24 avril 2017   - 09:30 à 12:45 : Bloc de Module (1/2 journée) (MOD)
programme : Stratégies mixtes. Jeux matriciels. Calcul des stratégies optimales. Jeux bimatriciels . Calcul des équilibres de Nash.
besoin : Vidéo,
Intervenants : Rida LARAKI,
jeu. 27 avril 2017   - 09:30 à 12:45 : Bloc de Module (1/2 journée) (MOD)
programme : 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.
besoin :
Intervenants : Rida LARAKI,
mar. 02 mai 2017   - 9:00 à 12:30 : Bloc de Module en salle Info (MODI)
programme : Soutenance des projets.
besoin :
Intervenants : Alain FAYE,
jeu. 04 mai 2017   - 10:00 à 12:00 : Contrôle (CC)
programme : Examen écrit
besoin :
Intervenants : Marie-Christine COSTA,