Probleme du Rendez-vous

Problème du Rendez-vous

Le problème du rendez-vous est une situation de théorie des jeux.

Pour la situation de base, 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 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

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.

Ce document provient de « Probl%C3%A8me du Rendez-vous ».