A l'occasion de votre anniversaire vous allez réunir quelques amis. Pour que cette soirée se déroule sous les meilleurs auspices, vous aurez pris la précaution de faire en sorte qu'il y ait
autant de filles que de garçons. Ils se connaissent plus ou moins et sont disposés à se mettre en couple mais pas n'importe comment, bien entendu.
Chacun des convives de la soirée se verrait bien danser avec un certain partenaire de son choix, mais les sentiments humains ont ceci de particulier, qu'ils ne sont pas toujours réciproques. Toute personne présente à la soirée doit donc s'attendre à se voir préférer quelqu'un d'autre.
Et si l'on souhaite que la soirée se passe du mieux possible et que chacun soit satisfait de son sort, il paraît nécessaire que se constituent des "
couples stables", c'est-à-dire où chacun est satisfait de son partenaire et n'éprouvera pas le désir (au moins pour la soirée) d'en changer ; ce n'est pas encore le meilleur des mondes, mais c'est déjà beaucoup !
Doit-on laisser les choses se dérouler de manière naturelle ?
Peut-on donner un petit coup de pouce au destin ?
On peut, en effet, utiliser un algorithme (c'est-à-dire un procédé toujours identique, une méthode) qui va nous permettre d'aboutir à la meilleure soirée possible. D'abord chacun, garçon ou fille, préparera mentalement une liste ordonnée de ses préférences et se préparera à tenter sa chance, une ou plusieurs fois, en suivant l'ordre de sa liste.
Voici un exemple avec
trois garçons et
trois filles :
- Alex (A), Bertrand (B) et Claude (C) pour les garçons,
- Xavière (X), Yvette (Y) et Zoé (Z) pour les filles.
Imaginons les listes de préférence suivantes :
- Pour A : XYZ
- Pour B : XYZ
- Pour C': YXZ
- Pour X : CAB
- Pour Y : ABC
- Pour Z : BCA
Pour procéder de manière efficace, on envisagera d'abord le cas où les garçons prennent l'initiative et se dirigent chacun vers la fille qu'ils souhaitent inviter en premier. On donne alors pour consigne à chaque fille de ne pas respecter les usages et de
suspendre son acceptation d'un cavalier, le temps de voir si un autre, qu'elle préfère, ne va pas se présenter dans un second temps.
Dans la configuration présente, plutôt que d'accepter Claude, Yvette attend que Xavière ait choisit entre ses prétendants. Or Xavière hésite, aucun des deux qui se présentent à elle n'étant son préféré. Elle peut toutefois se permettre de repousser Bertrand. Celui-ci, une fois éconduit, se présente à Yvette. Celle-ci le voit arriver avec satisfaction, même si elle préférait Alex et signifie à Claude qu'il n'est pas retenu. Claude va donc se présenter à Xavière, qui l'accueille à bras ouvert, Alex déçu d'une telle conclusion, se console auprès d'Yvette, laquelle repousse finalement les avances de Bertrand.
La répartition finale est donc la suivante :
- Alex et Yvette,
- Bertrand et Zoé,
- Claude et Xavière.
Cette répartition ne satisfait, certes, pas tout le monde (au regard des listes de préférence), mais présente un indéniable avantage : elle constitue un
équilibre stable, au sens où
aucun couple infidèle n'a de chance de se former. Claude aura beau tenter de se défaire de Xavière, celle-ci n'acceptera pas de se séparer d'André pour lui. Et c'est la même chose pour tous ceux qui ont motif de se plaindre de la répartition. Quel que soit le tableau des préférences de chacun, on montre que cette méthode produit toujours une répartition stable.
Evidemment, la méthode présente ceci de particulier, qu'elle introduit une
dissymétrie entre les garçons et les filles.
Dans notre exemple, si ce sont les filles qui font le premier pas, on aboutira d'emblée à la même configuration stable, mais ce n'est pas toujours le cas. Simplement, on montre qu'
il vaut mieux être de ceux qui font le premier pas plutôt que de ne faire qu'attendre.
On peut même aller plus loin et montrer que
chaque garçon a toujours intérêt à ce que ce soient les garçons qui fassent le premier pas : c'est-à-dire qu'aucune configuration stable ne lui attribue une "meilleure" cavalière que celle qu'il obtient par notre méthode.
En tout cas, dans cette soirée, si un garçon et une fille se préfèrent mutuellement à tous les autres, alors, quoi qu'il arrive, ils danseront ensemble ce soir-là. Voilà qui est rassurant et très romantique.
Et bien, dansez maintenant !
Daniel Motteau, professeur de Mathématiques, mars 2008.
