Ce projet est une étude pratique de la théorie des jeux, plus précisément de la recherche d'une situation stable entre deux protagonistes.
La théorie des jeux constitue une approche mathématique de problèmes de stratégie tels qu’on en trouve en recherche opérationnelle et en économie. Elle étudie les situations où les choix de deux protagonistes - ou davantage - ont des conséquences pour l’un comme pour l’autre. Le jeu peut être à somme nulle (ce qui est gagné par l’un est perdu par l’autre, et réciproquement) ou, plus souvent, à somme non-nulle.
John Nash a défini une situation d'interaction comme stable si aucun protagonistes n'a intérêt à changer sa stratégie. La formalisation de ce constat simple a été essentielle pour la théorie des jeux. Avant Nash, la détermination de situation stable n'avait pas de méthode formelle. Même si la traduction courante d'un équilibre de Nash peut paraître simpliste, les considérables possibilités de résolution ouvertes par lui ont mérité le Prix Nobel en 1994, conjointement à Reinhard Selten et John Harsanyi.
On travaillera sur l'exemple dit des marchands de glace, qui peut se résumer ainsi : deux marchands de glace doivent choisir un emplacement sur une plage de longueur donnée, les prix et les produits étant les mêmes, chaque client ira vers le marchand le plus proche de lui. Cet exemple est souvent cité comme pendant négatif de la main invisible d'Adam Smith, , économiste et philosophe d'origine écossaise, considéré comme le père de l'économie moderne.
Cahier des charges
De façon à rendre le projet un peu plus attractif, celui-ci simulera et enregistrera les conclusions d'un grand nombre d'expérience (10000 "journées" par exemple) sur cet exemple.
Le cadre de la simulation sera une matrice de position de 100 x 11 cases, qui symbolisera une plage (voir la représentation graphique ci-dessous). Sur cette "plage" les deux marchands de glaces, dénommés "glaciers" par la suite, devront occupé chacun une place différente l'une de l'autre, définie aléatoirement et limitée à la première ligne de la matrice (représentant le "trottoir"). Les vacanciers se répartiront quant à eux au hasard, sur les cases libres de la matrice (sauf sur la première ligne).
Chaque début de "journée", les deux glaciers se placeront ainsi qu'un premier groupe de vacanciers (dont le nombre ne pourra pas excéder 100). Une journée comportera 10 h durant laquelle l'expérience se déroulera. Chaque vacancier reste un nombre d'heure aléatoire (qui ne peut excéder bien entendu la différence entre son heure d'arrivée et la fin de la journée) et peut ou non acheter une glace au glacier le plus proche de lui durant l'intervalle de temps où il est présent à la plage. Chaque heure, un certain nombre de vacanciers arrivent (entre 0 et 100) et partent. Du fait que les deux glaciers proposent exactement les mêmes produits aux mêmes prix, chaque "achat" de glace sera comptabilisé 1 point. A la fin d'une journée, un bilan est établi qui enregistre principalement la différence entre les gains des deux glaciers ainsi que leur position respective.
Implantation
Dans un soucis d'évolutivité, on vous impose d'utiliser un L3G orienté objet (ici le C++ !) ainsi que sa bibliothèque standard, la STL. Dans ce contexte, on distingue les classes : Plage, Personne, Glacier, Vacancier, Vacances et Bilan.
La classe Plage correspond à la représentation symbolique d'une plage par une matrice 100 x 11 de cases. Elle doit gérer cet espace en l'initialisant, en marquant une case donnée comme occupée ou libre, en tenant le compte du nombre de places libres, etc.
La classe Personne est la classe mère des classes Glacier et Vacancier. Elle regroupe bien entendu les attributs communs aux glaciers et aux vacanciers (position, heure d'arrivée, heure de départ, etc.) ainsi que des méthodes permettant de connaître son état, de se placer sur la plage, etc.
La classe Glacier hérite de la classe Personne. Elle a la particularité de gérer les profits d'une journée.
La classe Vacancier hérite de la classe Personne. Elle a la particularité de déterminer si elle ira acheter une glace durant sa présence sur la plage et à qui (glacier le plus proche).
La classe Vacances est une classe superviseur, c'est la classe la plus conséquente en terme de nombre de lignes de code. Elle comportera au minimum comme attributs une plage et une liste de personnes et comme méthode une méthode permettant de lancer la simulation.
La classe Bilan enregistre les conclusions de chaque simulation et produit un bilan statistique dans lequel elle met en évidence les résultats les plus probants.
Modalités de rendu
La date de rendu est fixée au 6 et 7 juin (suivant les groupes). Vous devez rendre votre miniprojet dans un tarball nommé : login-nash.tgz et placer dans votre répertoire : $HOME avec les droits 444. Vos fichiers devront s'extraire dans le répertoire : ./login-nash (attention au point).Votre exécutable doit s'appeler nash.
Votre tarball devra contenir, en plus des modules, un makefile dont les règles suivantes sont nécessaires :
- all : crée le programme demandé,
- clean : nettoie tout ce qui a été généré pendant la compilation du programme.
La notation se base sur le passage des tests, le respect du sujet et le respect des principes et conseils énoncés dans le sujet. Les commentaires utiles seront pris en compte dans la notation.