Quatre mariages et un prix Nobel
Demain, 10 décembre, nous célébrerons les 116 ans de la disparition d'Alfred Nobel. C'est ce jour qui a été choisi pour remettre à leur lauréat les prestigieux prix Nobel. Cette année, les travaux récompensés parlent de cellules souches, de protéines G ou d'optique quantique. A titre exceptionnel, les mathématiques (à travers la théorie des jeux) seront également mises en valeur, à travers le prix (de la Banque royale de Suède en mémoire d'Alfred) Nobel en sciences économiques.
Le cauchemar de Nobel s'est réalisé : des mathématiciens ont été récompensés d'un prix qui porte son nom !
Ce sont donc l'économiste Alvin Roth (61 ans) et le mathématicien Lloyd Shapley (89 ans) qui seront récompensés lundi pour leur utilisation malicieuse du théorème des mariages stables dans des problèmes où l'on doit accorder l'offre et la demande. Aucun aspect financier ici, on cherche plutôt à coupler au mieux internes et hôpitaux ou à donner à des patients en attente de greffe le rein de leur rêve. Le mathématicien David Gale (célèbre aussi pour avoir inventé le jeu de Chomp) aurait probablement été distingué cette année s'il n'a pas eu cette fâcheuse idée de mourir en 2008.
Ce n'est pas la première fois que la théorie des jeux fait l'objet du prix Nobel d'économie : en 2007, pour Hurwicz, Maskin et Myerson, mais surtout en 1994 pour Harsanyi, Selten et surtout John Nash (le mathématicien schizophrène qui ressemble à Russel Crowe) .
Episode 74088 : le problème des mariages stables
Résumé de l'épisode précédent :
Pamela rêve en cachette du beau Dr Sean, marié à l'odieuse Jessica, alors qu'elle a déjà déclaré son amour à Rodney. De plus, Pamela vient de dire "oui" à Bradley, qui ne pourrait jamais la quitter pour Jessica ou Kimberly. Mais Rodney sait, même s'il est marié à Kimberly, qu'il serait plus heureux avec Jessica. Sean révèlera-t-il à Pamela qu'il la préfère à Jessica ? Pamela révèlera-t-elle à Sean qu'elle le préfère à Bradley ? Rodney devra-t-il tout quitter pour Jessica qui, de toutes façon, ne l'aime pas ? Toutes les réponses dans le 74 088e épisode de Les Feux de la Passion !
Le problème est donc le suivant : trois femmes (Pamela, Jessica et Kimberly) et trois hommes (Bradley, Rodney et Sean) ont chacun une idée bien précise de leur idéal. Chaque femme a classé les trois hommes par ordre de préférence, et inversement :
| Pamela : | r > s > b | Bradley : | P > J > K |
| Jessica : | s > b > r | Rodney : | J > K > P |
| Kimberly : | b > r > s | Sean : | K > P > J |
Dans la situation actuelle, les mariages sont les suivants :
| Pamela | - | Bradley |
| Jessica | - | Sean |
| Kimberly | - | Rodney |
Cette situation n'est pas stable. Pamela préfère Sean à Bradley et Sean préfère Pamela à Jessica : ils ont donc intérêt à quitter leur conjoint respectif pour partir se marier à Las Vegas. Y a-t-il moyen de former des couples qui empêchent ces tentations d'infidélité ?...
Pour trois hommes et trois femmes, il existe en fait 6 façons de former trois couples. Parmi ces appariement, trois ne sont pas stables (comme dans l'exemple précédent, où un couple illégitime peut exister), et trois donnent des situations stables. En particulier, il y a la situation où chaque femme choisit son premier choix (solution non optimale pour les hommes), la situation où chaque homme choisit son premier choix (non optimal pour les femme) et une troisième situation où chacun choisit son deuxième choix :
| Pamela | - | Rodney | Pamela | - | Bradley | Pamela | - | Sean | ||
| Jessica | - | Sean | Jessica | - | Rodney | Jessica | - | Bradley | ||
| Kimberly | - | Bradley | Kimberly | - | Sean | Kimberly | - | Rodney |
Dans chacune de ces trois solutions, on ne peut pas créer de couple illégitime qui rendrait à la fois les deux membres plus heureux qu'il ne le sont déjà.
Episode 74089 : l'algorithme Gale-Shapley
Résumé de l'épisode précédent :
Pamela et Sean se sont mutuellement déclaré leur flamme, et ont décidé de laisser tomber Bradley et Jessica. Pour rendre jaloux Kimberly, Jessica a demandé en mariage Bradley. Mais Bradley restera-t-il insensible aux charmes des jumelles Ashley et Candyce qui viennent d'arriver en ville ? Daisy osera-t-elle dire la vérité à Astor à propos de Davy et de Barbra ? Charly aura-t-il sa greffe de rein à temps ? Toutes les réponses dans le 74089e épisode de Les Feux de la Passion !
De manière plus générale, le problème des mariages stables est le suivant :
N hommes et N femmes sont destinés à être mariés. Chaque homme a ses préférences, sous la forme d'une liste strictement et totalement ordonnée (pas d'ex-æquo, pas d'oubli), idem pour les femmes. Est-il toujours possible d'obtenir N couples stables, c'est à dire, sans qu'il existe de couples (A,α) et (B,β) tel que A préfère β à α et β préfère A à B ?
Cette question est reliée au problème des colocataires (l'équivalent "mariage pour tous" du problème des mariages stables) : 2n étudiants doivent se partager n chambres, chacun ayant des préférences (sous la forme d'une liste) sur celui qui partagera sa chambre. Ce partage doit être stable : il ne faut pas que deux étudiants non colocataires se préfèrent au dépit de leur réel colocataire.
En fait, ce problème n'a pas forcément de solutions. On peut imaginer un cas avec 3 étudiants A, B et C tel que A préfère B, B préfère C et C préfère A, ainsi qu'un "gros lourd" D classé dernier par tous les autres. Quel que soit le partage, celui qui se retrouvera avec D aura toujours intérêt à prendre une chambre avec l'un des deux autres.
Il existe également le lemme des mariages, variante du problème des mariages stables, mais c'est plus une question de combinatoire que de théorie des jeux.
Le problème des colocataires montre en fait que le problème des mariages stables n'est pas complètement évident, et pourtant, il existe toujours une solution stable, sans hypothèses supplémentaires !
La démonstration est algorithmique :
Dans un premier temps, chaque homme va se présenter à la femme qu'il préfère. Si une femme reçoit plus d'une proposition, elle ne gardera que le meilleur choix (sans pour autant accepter la demande en mariage).
Les hommes rejetés vont alors déclarer leur flamme à leur deuxième choix. Chaque femme choisit alors l'homme qu'elle préfère parmi les nouveaux prétendants et celui mis de côté à l'étape précédente (s'il existe).
Le speed-dating continue jusqu'à ce que chaque femme ait eu une proposition. Les mariages peuvent alors être célébrés.
Avec ce procédé, chaque femme reçoit forcément une proposition au bout d'un certain temps (au pire, après N²-2N+2 étapes), et un homme ne peut jamais se présenter plusieurs fois à une même prétendante. Surtout, les mariages qui en découlent sont stables. Imaginons que Rodney préfère Jessica à sa femme. Alors, Rodney aura rencontré Jessica avant sa femme, ce qui ne peut se passer que si Jessica a délaissé Rodney pour un meilleur postulant. Du coup, Jessica préfère son mari à Rodney : l'union est stable.
En fait, cet algorithme promet aux hommes une solution optimale. On peut évidement inverser les rôles, ce qui donnerait une solution optimale pour les femmes. Si les deux algorithme coïncident, c'est qu'il n'y a qu'une seule solution stable.
Remarquons de plus que l'algorithme fonctionne aussi dans le cas où le nombre d'homme et de femme n'est pas le même.
Essayons sur un exemple, avec quatre femmes (Ashley, Barbra, Candyce et Daisy) et quatre hommes (Astor, Bradley, Charly et Davy) dont les préférences sont les suivantes :
| Ashley : | d > c > a > b | Astor : | A > B > C > D |
| Barbra : | b > d > a > c | Bradley : | A > D > C > B |
| Candyce : | d > a > b > c | Charly : | B > A > C > D |
| Daisy : | c > b > a > d | Davy : | D > B > C > A |
A la première étape, Ashley aura deux propositions (Astor et Bradley) alors que Barbra et Daisy n'en auront qu'une. Ashley gardera Astor (3e choix) :
Ashley : Astor Bradley
Barbra : Charly
Candyce : ...
Daisy : Davy
En attente : Bradley
Bradley se risquera donc à aborder Daisy, son deuxième choix. Elle le préfèrera à Davy, qui se retrouve maintenant seul.
Ashley : Astor Bradley
Barbra : Charly
Candyce : ...
Daisy : Davy Bradley
En attente : Davy
Le défilé des prétendants continue alors. Davy trouvera du réconfort auprès de Barbra, qui délaissera Charly. Ce dernier trouvera Ashley, qui quittera alors Astor. Après une demande infructueuse auprès de Barbra, il prendra la main de Candyce. Les couples sont alors formés, et les mariages sont stables !
Ashley : Astor
Barbra : Charly Davy Astor
Candyce : Astor
Daisy : Davy Bradley
Grâce à l'algorithme, cette solution est optimale pour les hommes. Dans ce cas précis, il se trouve que ces couples sont aussi les meilleurs pour les femmes : cette configuration n'offrait en fait qu'une seule solution stable.
Episode 74090 : le prix Nobel est accordé à...
Résumé de l'épisode précédent :
Astor a, faute de mieux, déclaré son amour à Candyce. Mais comment va-t-elle réagir quand elle apprendra qu'elle n'est qu'un troisième choix ? Que fera l'impétueuse Jessica quand elle saura tout à propos de Bradley et Daisy ? Charly aura-t-il réellement une greffe de rein ? Sean est-il vraiment médecin ? Quel est le rapport entre le problème des mariages stables et l'économie ? Toutes les réponses dans le 74090e épisode de Les Feux de la Passion !
C'est dans un article paru en 1962 que Gale et Shapley ont posé les bases de ce théorème des mariages stables, en étudiant le problème de l'affectation de n postulants entre m universités, chaque université ayant des quotas. Un tel problème se résoud de la même façon que cette histoire de mariages stable, où chacun des postulants se présente aux différentes universités dans l'ordre de ses préférences.
Un autre problème étudié par Shapley est le cas où la moitié des partis en présence n'a pas de préférence. L'exemple type est celui de la répartition entre les donneurs d'organes et les patients attendant une transplantation. Le système composé par Shapley reste utilisé par de nombreux états américains.
Dans les années 80, Alvin Roth s'intéresse au NRMP, l'organisation chargée d'affecter les internes dans les hopitaux américains. Il découvre qu'ils utilisent l'algorithme Gale-Shapley, et que les attributions sont stables. Jusqu'au jour (en 1995) où le système commence à dérailler, quand un trop grand nombre de couples de médecins cherchent à s'installer dans la même région. Roth est appellé à la rescousse pour modifier l'algorithme. Ce système qu'il a élaboré reste toujours utilisé aujourd'hui.
Finalement, Shapley et Roth n'ont jamais travaillé ensemble, mais c'est la combinaison entre les travaux théoriques de l'un et les travaux pratiques de l'autre qui leur rapporte aujourd'hui le prix Nobel. Et surtout, les mathématiques sont récompensées (et non un domaine qui a davantage mérité sa mauvaise réputation), on ne va pas bouder son plaisir !
Sources :
College admission and the stability of marriage, l'article original de David Gale et Lloyd Shapley paru dans l'American Mathematical Monthly
Stable matching: Theory, evidence, and practical design, le communiqué de presse du prix Nobel d'économie.
/http%3A%2F%2Fstorage.canalblog.com%2F38%2F13%2F210892%2F99552251_o.png)
/http%3A%2F%2Fstorage.canalblog.com%2F93%2F48%2F210892%2F89760281_o.jpg)
/http%3A%2F%2Fstorage.canalblog.com%2F62%2F76%2F210892%2F88024191_o.png)
/http%3A%2F%2Fstorage.canalblog.com%2F11%2F46%2F210892%2F87126295_o.jpg)