Master 1 MIAGe Recherche Opérationnelle I Projet de théorie des jeux à faire en groupes de 2 ou 3 Date d’échéance : Le 7 décembre 2009

Coefficient : 75% de la note de Contrôle Continu

1 Résumé

Ecrire un programme qui lit les matrices des gains des deux joueurs dans un jeu (pas forcément à somme nulle) et trouve la stratégie optimale de chaque joueur.

2 Ce qu’il faut faire

1. Lire les informations d’un fichier.

2. Trouver toutes les actions dominées possibles et les supprimer (avec un message qui explique quelle action est supprimée et pourquoi).

3. Cherche un point d’équilibre pure du jeu réduit.

4. Seulement dans le cas où il n’y a pas de point d’équilibre et il reste exactement deux actions possibles pour chaque joueur, déterminer la probabilité de chaque action dans la stratégie mixte optimale de chaque joueur.

3 À rendre par mail

Un fichier .tar qui contient :

1. les sources du programme,

2. un makefile qui sert à compiler le programme,

3. un fichier de documentation expliquant le format de vos fichiers d’entrées, les algorithmes utilisés et les structures de données,

4. les fichiers que vous aurez utilisés pour tester votre programme.