Pour traiter ces problèmes éminemment pratiques d’affectations, les méthodes les plus répandues ne sont pas forcément les meilleures [1]. Voici un exemple de procédure « naïve » :

Chaque interne indique ses préférences puis chaque hôpital examine d’abord les candidats l’ayant demandé en premier choix, puis s’il reste des places les choix en deuxième position, etc.

Dans le cadre de cette procédure, les internes sont donc fortement incités à ne postuler qu’à coup sûr, et donc à chercher la cote des différentes institutions et à renoncer pour la plupart à leur vrai choix, tandis que les hôpitaux les plus prestigieux peuvent se retrouver avec un nombre insuffisant de candidats ou décider de proposer le recrutement un peu avant les autres (mais ces autres ont alors la même idée), etc...

Cet article présente la contribution fondatrice de Lloyd S. Shapley et David Gale : le lemme [2] des mariages stables. C’est en effet ce résultat (ou certains de ses « descendants ») qui fournit la base mathématique de nombreux travaux appliqués sur les problèmes d’affectation jusqu’à aujourd’hui.

Né en 1923, mathématicien, L. Shapley s’est largement consacré à la théorie des jeux (l’étude mathématique des interactions entre participants rationnels) et notamment à la recherche de bonnes propriétés de « stabilité » vis-à-vis de coalitions d’ensemble de stratégies (ce que Shapley a appelé le noyau du jeu). Le lemme des mariages stables est un exemple simple mais important, où on ne considère que les coalitions de deux joueurs.

Alvin Roth, né trente ans plus tard et spécialisé en recherche opérationnelle, reprend dans les années 1980 les travaux de Shapley pour les enrichir théoriquement de façon à pouvoir analyser de nouvelles situations. Dans cet article de vulgarisation mathématique, nous nous concentrerons toutefois sur le lemme des mariages stables de Gale et Shapley et laisserons de côté les résultats et les applications parfois spectaculaires d’A. Roth.

David Gale n’était pas éligible au prix « Alfred Nobel », étant décédé en 2008.

Du problème concret à son analyse mathématique

Gale et Shapley sont les premiers dans les années 1960 à considérer mathématiquement le problème de l’affectation dans le cadre de la théorie des jeux [3] alors encore récente.

L’analyse mathématique d’un problème pratique consiste typiquement en quatre étapes :

• la modélisation : définir une version mathématique du problème et de ses solutions ;
• le choix des propriétés que doit avoir « une bonne solution » [4] ;
• l’étude si une telle solution existe ;
• si oui, la recherche d’une méthode pratique pour trouver une solution.

Gale et Shapley présentent une forme simplifiée de leurs résultats dans l’American Mathematical Monthly (un journal qui parle de l’actualité mathématique aux mathématiciens non spécialistes du sujet considéré). Cet article intitulé « College Admissions and the Stability of Marriages » peut être lu en ligne gratuitement ici. Les auteurs ont fait l’effort de rester élémentaires, y compris dans leurs notations [5] .

Modélisation de Gale-Shapley

Gale et Shapley commencent par simplifier à outrance le problème des internes et des hôpitaux : ils traitent en premier lieu un problème de mariage collectif (constituer 100 couples à partir de 100 femmes et 100 hommes dont on connaît les préférences individuelles) – comme si chaque hôpital ne pouvait accueillir qu’un seul interne.

Un problème de mariage collectif consiste en :

• Le même nombre $N$ de femmes et d’hommes.
• Chacun est déterminé à se marier avec une personne de l’autre sexe.
• Chacun a déterminé une fois pour toutes ses préférences sous la forme d’une liste ordonnée des personnes de l’autre sexe (sans ex æquo, sans omission) et cette liste est connue.

Une solution à ce problème est une liste de $N$ couples (une femme, un homme) (!) prescrivant autant de mariages.

Qu’est-ce qu’une bonne solution ?

Gale et Shapley définissent une solution à un problème de mariage collectif comme raisonnable, ou plutôt stable, si cette solution a la propriété suivante :

La solution ne doit pas prescrire de mariages tels qu’une femme $A$ et un homme $b$ se préfèrent mutuellement à leurs conjoints prévus. Formellement, il ne doit pas y avoir deux mariages distincts $(A,a)$ et $(B,b)$ tels que $A$ et $b$ (ou $a$ et $B$) préféreraient être mariés ensemble. En effet, (on peut imaginer qu’alors) ils divorceraient pour se remarier.

Cette propriété est un cas particulier du problème général en théorie des jeux de la stabilité vis-à-vis de coalitions quelconques (et non pas réduites comme ci-dessus à deux éléments, ci-dessus $A$ et $b$). Shapley a étudié ce problème de façon détaillée au cours de sa carrière. Notons que la recherche de critères de stabilité ou de viabilité d’une combinaison de choix ou de stratégies des différents participants est un problème qui a valu à plus d’un chercheur un prix « Alfred Nobel » d’économie : John Nash, pour citer un mathématicien célèbre.

Nous pouvons maintenant énoncer le résultat mathématique de Gale et Shapley :

Le Lemme des mariages stables

Tout problème de mariage collectif admet au moins une solution stable.

Il existe d’ailleurs une unique solution stable qui soit optimale pour les femmes au sens que chaque femme ne puisse obtenir un meilleur mariage dans une autre solution stable.

Remarques.

1. Le lemme des mariages est un outil classique de combinatoire expliqué dans cet article d’Images des Mathématiques. Ce résultat classique permet également de produire un appariement entre les éléments de deux ensembles, mais sous une hypothèse de nature assez différente du lemme de Gale et Shapley.
2. Il y a symétrie complète entre hommes et femmes dans la définition du problème. Il existe donc aussi une solution optimale pour les hommes, mais attention ce n’est en général pas la même ! [6]
3. Gale et Shapley soulignent dans leur article comment ce résultat explique la procédure réellement utilisée pour l’affectation des internes aux hôpitaux aux Etats-Unis depuis les années 1950.
4. Une idée peut-être plus naturelle pour construire une solution serait de définir un ordre de désirabilité global sur les hommes et sur les femmes pour marier le plus désirable avec la plus désirable, etc. Le théorème d’impossibilité de Kenneth Arrow (voir aussi cet article-ci et celui-là) montre que cela ne marcherait pas.
5. On peut croire que ce résultat fournit une analyse complète de ce problème (au moins dans sa version simplifiée). Mais tout bon chercheur a une réserve de questions dans sa besace. Ici, les théoriciens des jeux vont par exemple se demander dans quelles conditions il est possible de tricher. Cela fait partie des problèmes que résout A. Roth.
6. Le problème de l’affectation considéré ici ne fait intervenir ni prix, ni marché. C’est un coordonnateur central qui propose une solution qui devrait être acceptée volontairement du fait de son caractère stable (du socialisme à visage humain, en somme). D’autres économistes ont analysé des problèmes mixtes, combinant listes de préférences (aspect combinatoire ou discret) et prix (aspect continu).

Un peu de lecture

• L’annonce officielle de l’attribution du prix de la banque de Suède pour les sciences économiques en la mémoire d’Alfred Nobel se trouve ici.
• L’informaticien bien connu Donald E. Knuth a écrit un petit livre en français sur ce type d’algorithmes et leur analyse.
• Le New York Times propose quelques liens dont ce site qui permet de jouer avec l’algorithme de Gale-Shapley.