Deux groupes (Parcoursup)

Comment ça marche, précisément

Deux groupes distincts se classent mutuellement. Le côté 1 propose, le côté 2 dispose — et chaque entrée du côté 2 peut avoir une capacité de plusieurs places.

Chaque proposant sollicite son premier choix. Chaque receveur retient provisoirement les meilleurs candidats dans la limite de sa capacité et écarte les autres. Rien n'est définitif : c'est tout le sens de l'acceptation DIFFÉRÉE.

Les candidats écartés proposent à leur choix suivant, ce qui peut déloger un candidat provisoirement retenu, qui repropose à son tour. On s'arrête quand plus personne n'a de proposition à faire.

Le résultat est stable : aucun couple candidat-formation ne se préférerait mutuellement à son affectation. Il est de plus OPTIMAL pour le côté proposant — parmi tous les appariements stables, chaque proposant obtient le meilleur possible.

Un exemple chiffré

Trois candidats, trois formations d'une place chacune, classements croisés.

Candidat	Vœux	Formation	Classement
Chloé	A, B, C	A	Ali, Chloé, Bruno
Ali	A, C, B	B	Chloé, Bruno, Ali
Bruno	B, A, C	C	Bruno, Chloé, Ali

Tour 1 : Chloé et Ali proposent à A, Bruno à B. A préfère Ali et écarte Chloé ; B retient Bruno.
Tour 2 : Chloé propose à B. B préfère Chloé à Bruno et permute — Bruno est délogé.
Tour 3 : Bruno propose à A, qui garde Ali ; puis à C, qui l'accepte. Fin : Ali→A, Chloé→B, Bruno→C.

Bruno a été retenu puis délogé : c'est la mécanique du différé, et la raison pour laquelle les résultats de Parcoursup bougent pendant plusieurs semaines. Le résultat final est stable.

D'où ça vient

David Gale et Lloyd Shapley publient en 1962 « College Admissions and the Stability of Marriage » dans l'American Mathematical Monthly. Ils y démontrent qu'un appariement stable existe TOUJOURS entre deux groupes, et donnent un algorithme simple pour le construire : l'acceptation différée.

Coup de théâtre historique : le National Resident Matching Program, qui affecte depuis 1952 les internes américains aux hôpitaux, utilisait déjà un algorithme équivalent — découvert empiriquement, dix ans avant sa théorisation. Alvin Roth le démontre en 1984, et pilote sa refonte de 1998 pour traiter le cas des couples.

Roth et Shapley reçoivent le prix Nobel d'économie 2012 pour la théorie des allocations stables et la conception de marchés. En France, Parcoursup applique ce principe depuis 2018, en remplacement d'APB, avec un répondeur automatique qui joue le rôle de l'acceptation différée.

Où on s'en sert

Parcoursup et les affectations post-bac françaises.
Internat médical américain (NRMP) depuis 1952.
Affectation d'élèves aux écoles à New York et Boston, refondue par Roth et ses collègues.
Programmes de mentorat, stages, attributions de projets entre deux populations distinctes.

Limites et pièges

✓ AVANTAGES

Toujours un appariement stable
Gère les capacités (plusieurs places par entrée du côté 2)
Classer sincèrement est optimal pour le côté 1

✕ INCONVÉNIENTS

Favorise structurellement le côté qui propose
Le côté 2 peut être tenté de classer tactiquement
Des non-affectés si les places manquent

Asymétrie structurelle

Le côté qui propose obtient le meilleur appariement stable possible ; l'autre, le moins bon. Décider qui propose est donc une décision politique, pas technique.

Non manipulable d'un seul côté

Classer sincèrement est optimal pour les proposants — c'est démontré. Le côté receveur, lui, peut parfois gagner à classer tactiquement.

Des non-affectés

S'il manque des places, certains restent sans affectation. L'algorithme n'en crée pas.

Angoisse de l'attente

Les affectations provisoires bougent jusqu'à la fin. Mathématiquement sain, socialement éprouvant — Parcoursup en fait l'expérience chaque été.

Questions fréquentes

Pourquoi mon affectation change-t-elle en cours de route ?

Parce que l'acceptation est différée : une place vous est réservée provisoirement, et un candidat mieux classé peut vous en déloger — comme vous pouvez en déloger un autre ailleurs. Le processus ne se fige qu'à la fin, et c'est ce qui garantit la stabilité du résultat.

Ai-je intérêt à classer tactiquement mes vœux ?

Si vous êtes du côté proposant — les candidats, dans Parcoursup — non : classer sincèrement est prouvé optimal. Mettre en tête un vœu que vous jugez « réaliste » plutôt que celui que vous voulez vraiment ne peut que vous nuire.

Que veut dire « stable » ?

Qu'aucun couple candidat-formation ne se préférerait mutuellement à ce qu'il a obtenu. Sans cette propriété, des accords parallèles se noueraient hors du dispositif — c'est exactement ce qui arrivait aux États-Unis avant 1952.

Quelle différence avec le tour de choix ?

Le tour de choix ne fait classer qu'un seul côté : les options n'ont pas d'avis. Ici, les deux côtés se classent, et l'affectation doit satisfaire les deux — d'où la notion de stabilité, qui n'a pas de sens dans un tour de choix.

Sources

Les références primaires sur lesquelles s'appuie cette fiche.

Gale, David et Shapley, Lloyd S., College Admissions and the Stability of Marriage, The American Mathematical Monthly, 69(1), 9-15, 1962. DOI ↗
Dubins, Lester E. et Freedman, David A., Machiavelli and the Gale-Shapley Algorithm, The American Mathematical Monthly, 88(7), 485-494, 1981. DOI ↗
Roth, Alvin E., The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory, Journal of Political Economy, 92(6), 991-1016, 1984. DOI ↗
Roth, Alvin E. et Peranson, Elliott, The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design, American Economic Review, 89(4), 748-780, 1999. DOI ↗
Comité du prix de sciences économiques de l'Académie royale des sciences de Suède, Stable allocations and the practice of market design (Scientific Background, prix de sciences économiques en mémoire d'Alfred Nobel), Nobelprize.org, document « Advanced information », 15 octobre 2012, 2012. ↗