Un bal où la précipitation ne gâche rien ✛ ✎
La salle de bal bourdonne. Les invités arrivent au hasard — c'est un véritable flux aléatoire. Le maître de cérémonie doit trouver un partenaire de danse pour chacun. On peut former un couple immédiatement, mais que se passe-t-il si, une minute plus tard, quelqu'un de bien plus compatible se présente ? Et si l'on tarde, l'impatience monte : rester sans partenaire est ennuyeux et vexant. Ce problème est un casse-tête pour les programmes qui gèrent les livraisons ou le cloud computing, où il faut prendre des décisions sans connaître l'avenir.
La clé du succès réside dans la façon de comptabiliser le mécontentement des personnes qui attendent. Si la pénalité augmente avec le nombre d'invités isolés (chaque personne supplémentaire ajoute des soucis), alors le nombre de combinaisons de paires explose : il croît comme 2 puissance n, où n est le nombre d'invités.
L'idée de cette compétition contre un adversaire idéal a été introduite par John von Neumann pour l'analyse des jeux stratégiques. Pour une pénalité à grande échelle, tout plan prédéfini, non adaptatif, perd de manière exponentielle face à l'idéal.
Mais il suffit de changer le mode d'impatience — et le problème devient soudain simple. Imaginez que le mécontentement de chaque invité croît avec une accélération : la première minute d'attente est tolérable, mais la cinquième est exaspérante. Ajoutez à cela une petite pénalité, mais obligatoire, dès le simple fait du retard — et le comportement du maître de cérémonie change radicalement, comme si le système changeait de mode. Cette formule de mécontentement se décrit par f(t) = $t^k$/k + t, où t est le temps. À zéro, il n'y a pas de pénalité, mais dès le premier instant, le terme t apparaît, puis la croissance s'accélère. Une règle simple suffit : si quelqu'un attend plus longtemps que le seuil 4δ, on le connecte immédiatement à la paire la plus proche. Cet algorithme « impatient » ne regarde que l'horloge — et pourtant il fonctionne presque parfaitement, perdant face à un adversaire omniscient au plus d'un facteur constant.
Ainsi, le bal se termine sans drame : un peu de patience, mais pas trop. Cette leçon simple est désormais intégrée dans les services logistiques et cloud, pour que les paires — qu'il s'agisse de commandes ou de tâches — se rencontrent à temps.
Si la punition pour l'attente croît comme t², alors deux minutes sont quatre fois pires qu'une seule. Mais ajoutez une petite composante linéaire — et le problème, presque insoluble, devient simple.
Dans la série « Black Mirror » (épisode « Hang the DJ »), le système simule des relations en rejouant de nombreux scénarios — comme notre maître de cérémonie cherchant un équilibre entre patience et rapidité.