Problème du Rendez-vous
Le problème du rendez-vous est une situation de théorie des jeux.
Pour la situation de bas, c'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
- lorsque le jeu est légèrement dyssymétrique : chaque joueur à 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 (
| 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 optimum de messagers à envoyer.