Problème du rendez-vous
problème logique
Le problème du rendez-vous est une situation d'exemple de la théorie des jeux.
Situation de base
modifierLa situation de base est un jeu à somme non nulle égale. Si les joueurs arrivent au même endroit au même moment, ils gagnent tous la même chose, les autres situations sont perdantes.
1 \ 2 | rendez-vous | ailleurs |
---|---|---|
rendez-vous | (+1;+1) | (+0;+0) |
ailleurs | (+0;+0) | (+0;+0) |
La solution est évidente, mais ce jeu de base présente des variantes plus intéressantes.
Variantes
modifier- Lorsque le jeu est légèrement dissymétrique : chaque joueur a un lieu préféré, il gagne un peu plus lorsque le rendez-vous s'y produit. La matrice de gain est alors :
1 \ 2 | cinéma | fête |
---|---|---|
cinéma | (+2;+1) | (+0;+0) |
fête | (+0;+0) | (+1;+2) |
- Lorsque le jeu fait participer un nombre important de joueurs, et que le résultat dépend du nombre p de joueurs qui se coordonnent : il y a gain s'il y a au moins N participants. La matrice est alors :
1 \ « autres » | p >= N | p < N |
---|---|---|
fête | 2 | -1 |
absent | 0 | 1 |
- Lorsque le jeu est répété, et que le seul lien de communication est le résultat de la partie précédente.
- Lorsque le jeu n'est pas répété, mais que la communication est dégradée entre les deux joueurs (ils peuvent envoyer des messages, mais ils ne peuvent pas savoir si le message est bien parvenu). C'est la variante des « généraux byzantins » : s'ils attaquent ensemble leur ennemi ottoman sans que celui-ci connaisse leur plan, ils gagnent, sinon ils perdent. Ils doivent envoyer des messagers pour communiquer entre eux, mais pas trop sinon leur ennemi risque de capturer un messager porteur du plan. En fonction des probabilités que respectivement le messager se perde et se fasse capturer, il faut calculer le nombre optimal de messagers à envoyer.