v2.11.0 (5354)

Cours scientifiques - RO203 : Graphes, jeux et R.O

Domaine > Optimisation, Recherche opérationnelle et Commande, Mathématiques et leurs applications.

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

Pour les étudiants du diplôme Master 1 Applied Mathematics ans statistics - 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 20

Littérale/grade européen

Pour 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
L'UE est acquise si Note finale >= 10
  • Crédits ECTS acquis : 2.5 ECTS
  • Scientifique acquis : 2.5

Le coefficient de l'UE est : 2

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 Parisien de Recherche Opérationnelle

Le rattrapage est autorisé (Note de rattrapage conservée)
  • le rattrapage est obligatoire si :
    Note initiale < 7
L'UE est acquise si Note finale >= 10
  • Crédits ECTS acquis : 5 ECTS

Le coefficient de l'UE est : 1

Pour les étudiants du diplôme Master 1 Applied Mathematics ans statistics - 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
L'UE est acquise si Note finale >= 10
  • Crédits ECTS acquis : 2.5 ECTS
  • Scientifique acquis : 2.5

Le coefficient de l'UE est : 2

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

Mots clés

théorie des jeux, jeux à 2 joueurs, graphes, programmation linéaire, modélisation

Méthodes pédagogiques

CM, TD, Projet
Veuillez patienter