Asymptotic Equivalence of Immediate and Deferred Acceptance

Imaginez que vous soyez le maire d'une ville bouillonnante où chaque enfant doit avoir une place dans une école, et où il y a exactement autant de sièges qu'il y a d'élèves. Le problème n'est pas seulement de trouver une place, mais de trouver la bonne place. Chaque famille possède une liste d'écoles qu'elle adore, de « Mon école de rêve » jusqu'à « Celle où j'irais si je n'avais pas le choix ». La ville a aussi ses règles : peut-être qu'une école donne la priorité aux enfants qui habitent à proximité ou qui ont déjà des frères et sœurs là-bas. La grande question pour les responsables est la suivante : Comment faire correspondre les enfants aux écoles de manière à ce que tout le monde soit aussi heureux que possible ?

Pendant des décennies, des experts ont débattu de deux manières principales de faire cela. La première est appelée l'Acceptation Différée (AD). Voyez cela comme une danse lente et prudente. Les élèves postulent pour leur premier choix. Les écoles retiennent leurs candidats préférés mais ne leur disent pas « oui » définitivement ; elles disent juste « peut-être ». Si un meilleur élève se présente plus tard, l'école peut l'échanger. Ce processus se répète jusqu'à ce que tout le monde soit installé. C'est célèbre pour être équitable et impossible à tricher, mais cela peut être un peu désordonné et inefficace.

La seconde méthode est l'Acceptation Immédiate (AI), souvent appelée le mécanisme de « Boston ». C'est plutôt comme une course effrénée. Les élèves font la queue et postulent pour leur premier choix. Les écoles regardent la file, choisissent leur favori selon la priorité, et disent : « Vous êtes dedans ! » immédiatement. Si vous êtes rejeté, vous courez instantanément vers votre deuxième choix. Le bémol, c'est que si vous postulez pour votre premier choix tardivement, vous pourriez perdre votre place au profit de quelqu'un ayant une priorité plus élevée qui a postulé plus tôt, même si vous vouliez vraiment cette école plus que n'importe qui. À cause de cela, l'AI est souvent critiquée pour être injuste ou facile à manipuler. Cependant, l'IA possède un superpouvoir : si tout le monde dit la vérité sur ce qu'il veut, l'IA garantit un résultat où personne ne peut être rendu plus heureux sans rendre quelqu'un d'autre mécontent. C'est ce qu'on appelle l'« efficacité au sens de Pareto ».

Voici donc la question à un million de dollars : Le superpouvoir de l'IA fait-il réellement une grande différence dans la vie réelle ? L'IA permet-elle d'inscrire les enfants dans des écoles qu'ils aiment bien plus que la méthode DA ? Ou la différence n'est-elle qu'un minuscule point invisible ? C'est l'énigme que Josué Ortega aborde dans son article.

---

La grande course scolaire : Un conte de deux mécanismes

Josué Ortega, un chercheur de l'Université Queen's de Belfast, a décidé de trancher ce débat en menant une immense expérience de pensée. Il n'a pas regardé les vraies villes avec leur histoire et leur politique complexes. Au lieu de cela, il a imaginé un « marché aléatoire » — un monde où la liste des écoles préférées de chaque étudiant est tirée complètement au hasard, comme si on tirait des noms dans un chapeau. Dans ce monde, il y a $n$ étudiants et $n$ écoles.

Ortega voulait mesurer le « rang moyen ». Imaginez que chaque étudiant reçoive un score basé sur la position de l'école assignée dans sa liste. Si vous obtenez votre choix n°1, votre rang est 1. Si vous obtenez votre choix n°100, votre rang est 100. Le but est de garder ce nombre le plus bas possible.

Pendant longtemps, nous connaissions la réponse pour la danse lente et prudente (AD). Dans les années 1970, des mathématiciens ont découvert que dans un marché aléatoire, l'étudiant moyen se retrouve dans une école classée environ à $\log n$ (logarithme de $n$). Si vous avez 1 000 étudiants, le rang moyen est d'environ 7. Si vous avez 100 000 étudiants, il est d'environ 11. Cela augmente, mais très lentement.

Mais qu'en est-il de la course effrénée (AI) ? Parce que l'IA fonctionne différemment — où l'ordre de candidature compte et où les étudiants peuvent être rejetés simplement pour avoir été « en retard » — les mathématiciens pensaient que cela pourrait être beaucoup plus complexe. Certains informaticiens avaient essayé de résoudre le problème, mais ils ne pouvaient déterminer que la probabilité d'obtenir un rang spécifique, et non le rang moyen pour tout le monde. Ils supposaient que ce serait également logarithmique, mais personne ne pouvait le prouver.

Le secret du « Collectionneur de Coupons »

La percée d'Ortega fut de réaliser que les deux mécanismes, malgré leurs apparences très différentes, jouent secrètement au même jeu. Il a utilisé un puzzle classique appelé le Problème du Collectionneur de Coupons pour l'expliquer.

Imaginez que vous essayiez de collectionner un ensemble complet de $n$ cartes de collection différentes. Chaque fois que vous achetez une boîte de céréales, vous obtenez une carte aléatoire. Combien de boîtes devez-vous acheter pour obtenir chaque carte au moins une fois ?
La réponse est environ $n \times \log n$. Vous passez beaucoup de temps à acheter des boîtes juste pour trouver les dernières cartes rares qui vous manquent.

Ortega a montré que l'Acceptation Différée est exactement comme cela. Les étudiants continuent de postuler à des écoles jusqu'à ce que chaque école ait reçu au moins une candidature. Le nombre total de candidatures faites par tout le monde est à peu près égal au nombre de boîtes de céréales qu'il faudrait acheter pour collecter tous les coupons. Puisque l'étudiant moyen fait environ $\log n$ candidatures, son rang d'école final est aussi d'environ $\log n$.

Ensuite, Ortega a tourné son regard vers l'Acceptation Immédiate. Au premier abord, cela semblait différent car les étudiants ne peuvent pas simplement continuer à postuler immédiatement ; ils doivent attendre qu'un « tour » se termine avant de réessayer. Mais Ortega a réalisé que si l'on regarde le processus d'une certaine manière, c'est aussi un collectionneur de coupons.

Il a imaginé une version légèrement « amnésique » du jeu. Supposons qu'un étudiant choisisse des écoles au hasard, même s'il a déjà essayé cette école. S'il choisit une école qu'il a déjà tentée, il l'ignore simplement (c'est un tirage « gaspillé »). Ortega a prouvé que même avec ces tirages gaspillés, le nombre de vraies candidatures nécessaires pour remplir chaque école est toujours à peu près le même que celui du problème du collectionneur de coupons.

La grande révélation

Voici la chute : La différence entre les deux méthodes est étonnamment petite.

Ortega a prouvé mathématiquement qu'à mesure que le marché devient immense (lorsque $n$ devient très grand), le rang moyen des étudiants dans le système d'Acceptation Immédiate (AI) est également d'environ $\log n$.

Cela signifie que même si l'IA est « efficace au sens de Pareto » (ce qui signifie qu'elle est théoriquement parfaite si tout le monde dit la vérité), elle ne donne pas un avantage massif aux étudiants en termes d'accès à leurs meilleurs choix par rapport à la méthode DA. L'amélioration de « premier ordre » — le gain notable — n'existe tout simplement pas.

L'article d'Ortega écarte explicitement l'idée que l'IA soit une solution miracle qui améliore radicalement les résultats des étudiants dans les grands marchés aléatoires. Bien que l'IA puisse être légèrement meilleure dans des scénarios très spécifiques ou avec des règles de priorité particulières, l'article montre que dans le cas général, les deux mécanismes sont asymptotiquement équivalents. Ils placent tous deux les étudiants dans des écoles classées de manière approximativement logarithmique par rapport à la taille du marché.

Pourquoi cela importe

Cette conclusion est un peu décevante pour les partisans du système d'« Acceptation Immédiate », mais c'est un soulagement pour les mathématiques. Cela nous indique que l'« efficacité de Pareto » de l'IA est un peu un mirage lorsqu'il s'agit du bonheur moyen. Le mécanisme qui est souvent critiqué pour être injuste et manipulable n'offre pas de résultat moyen nettement meilleur que celui qui est équitable et difficile à tricher.

Le travail d'Ortega étend cette conclusion à d'autres variations également. Que les écoles aient plusieurs sièges (correspondance de type « many-to-one ») ou que les étudiants soient autorisés à sauter par-dessus des écoles complètes (une variante appelée « IA avec sauts »), le résultat reste le même : le rang moyen reste autour de $\log n$.

Ainsi, la prochaine fois que vous entendrez quelqu'un argumenter que nous devons utiliser le « mécanisme de Boston » parce qu'il est plus efficace, vous pourrez sourire et dire : « Eh bien, c'est peut-être efficace, mais cela ne permet pas réellement d'inscrire les enfants dans de meilleures écoles en moyenne que l'autre méthode. » Dans la grande course du choix scolaire, les deux coureurs franchissent la ligne d'arrivée presque exactement au même moment.