Comment trouver un mari/une femme quand on est con et pleurnichard : Mariage et théorie des jeux

Ce n’est pas du jeu de la jarretière et autres joyeusetés dont il s’agira ici, mais de théorie des jeux coopérative, une branche de la microéconomie que j’ai étudiée, et qui s’est intéressée entre autres à : comment marier de manière optimale des individus appartenant à deux groupes distincts (hommes et femmes par exemple, mais aussi, dans d’autres applications, étudiants et universités, médecins et hôpitaux…)

Hypothèses

Posons d’abord les hypothèses de notre modèle, tirées de Gale et Shapley (1962). Nous nous intéressons ici au cas où on a deux groupes d’individus, les H et les F, et on cherche à les marier deux par deux – ce n’est pas toujours le cas : par exemple, un étudiant ne va qu’à une université, mais une université accepte plusieurs étudiants, c’est une situation de one to many.

– Comme dans la vraie vie (hors Afrique du Sud polygame), chaque H peut se marier avec au plus un F, chaque F peut se marier avec au plus un H, et les individus peuvent rester célibataires.

– On appelle matching une division des individus en paires (chacune comprenant un H et un F, Harvey Milk n’était pas encore passé par là) et en célibataires.

– On note m(i) le partenaire d’un individu i, donc si i et j forment un couple, m(i) = j et m(j) = i. Si k est célibataire, m(k) = k.

– Tous les individus ont des préférences strictes : c’est-à-dire que, entre deux partenaires possibles, il en existe toujours un qu’ils préfèrent. Les individus sont aussi d’un calme olympien, puisque tout ce qui leur importe est leur propre partenaire, pas celui des autres. Qu’il y ait une chanceuse qui sorte avec Hugh Jackman ne change rien à mon propre choix de t’épouser, mon chéri.

– Les partenaires acceptables sont, pour chaque individu, ceux qu’il préférerait épouser plutôt que de rester célibataire.

Objectif

Nous cherchons un matching stable, c’est-à-dire qui respecte deux conditions :

1. chaque individu marié préfère être avec son partenaire que d’être célibataire ;

2. pas d’adultère : il n’existe pas de paire (i,j) telle que i préfère j à son partenaire actuel et j préfère i à son partenaire actuel ; sinon, il leur suffirait de rompre et de se remarier ensemble, ce qui produirait un meilleur matching.

L’idée qui se trouve au cœur du matching stable est celle de Pareto-optimalité : une situation qui ne peut pas s’améliorer pour une personne sans que, simultanément, elle ne se dégrade pour au moins une autre personne. (Attention à ne pas prendre « optimalité » au pied de la lettre : si dans une société on décide de me donner toutes les richesses et de vous laisser sans rien, c’est Pareto-optimal parce que, pour améliorer la situation de tous les pauvres, un Robin des Bois doit dégrader au moins un peu ma situation à moi).

Théorème

Gale et Shapley prouvent que ce que nous cherchons existe : plus précisément, il existe toujours au moins un matching stable que tous les H aiment au moins autant que chaque autre matching stable possible ; il existe aussi toujours au moins un matching stable que tous les F aiment au moins autant que chaque autre matching stable possible – mais ce n’est pas forcément le même.

Algorithme

Mais concrètement ? Osborne (2004) propose un algorithme pour obtenir un tel matching stable, et vous allez voir, c’est assez rétro. Les deux groupes sont asymétriques dans leur manière de faire la cour. L’un des deux (disons les F) est composé d’individus sûrs d’eux, qui guident leur partenaire lorsqu’ils valsent, puis s’agenouillent, ouvrent un petit écrin et font une demande en mariage tandis que les violons de Strauss continuent à jouer. Les autres (les H, donc) se prennent un peu les pieds dans leur crinoline, battent de l’éventail, et décident d’accepter ou non le prétendant. Voilà ce que ça donne avec un exemple :

Les préférences des F et des H sont présentées ci-dessous (lire en colonnes, par exemple Florence aimerait épouser Henri, ou Hubert si ce n’est pas possible avec Henri, et si ni l’un ni l’autre ne veulent d’elle, elle se retire au couvent)

Florence demande donc Henri en mariage. Frida et Fabienne, toutes les deux, demandent à Hubert de les épouser. Henri aime bien Florence, ce n’est pas sa préférée mais pourquoi pas. Pour le moment, Henri ne refuse pas, il sera toujours temps de rompre les fiançailles si une meilleure opportunité se présente. Hubert a deux demandes : de Frida et Fabienne. Parmi elles, c’est Fabienne que Hubert préfère ; il éconduit donc Frida.

Pour le moment, on a donc deux couples (Henri-Florence et Hubert-Fabienne) et deux célibataires (Honoré et Frida).

Que fait la prétendante éconduite ? L’algorithme nous indique qu’elle va danser avec le prochain individu sur sa liste ; dans notre exemple, Frida ignore superbement Honoré qui se languit tout seul derrière une tapisserie et va danser avec Henri et lui faire sa déclaration d’amour. Henri est ravi : Florence était pas mal, mais si son chevalier servant préféré, Frida vient lui faire la cour, c’est encore mieux : au revoir Florence, je te rends la bague et pars sur le cheval blanc de Frida !

C’est à présent Florence qui est éconduite, Honoré fait toujours tapisserie, et les couples sont à présent Henri-Frida et Hubert-Fabienne. Florence va donc danser avec le suivant dans son carnet de bal, Hubert. Hubert est déjà en couple avec Fabienne, mais au fond de lui, il préfère Florence… Il accepte donc la demande de Florence, et laisse tomber Fabienne.

Fabienne va danser avec le partenaire qu’elle préfère après Hubert, à savoir Henri. Mais Henri ne l’entend pas de cette oreille : alors que sa prétendante préférée, Frida, lui a déclaré sa flamme, qu’a-t-il à faire de la demande de Fabienne, qu’il trouve bien moins séduisante ?

Fabienne est donc éconduite une deuxième fois. Elle pourrait inviter Honoré à danser, mais non, il est vraiment trop laid, mieux vaut rester célibataire ! A l’issue du bal on obtient donc deux couples, Hubert-Florence et Henri-Frida, et deux célibataires, Honoré et Fabienne.

Pour résumer, les F demandent en mariage leur H préféré parmi ceux qui ne les ont pas déjà éconduites ; les H acceptent les propositions des F qu’ils trouvent acceptables et, s’ils ont une deuxième proposition ensuite, choisissent entre leur fiancée actuelle et la nouvelle prétendante. Le processus s’arrête si toutes les propositions des F sont acceptées, ou si les F rejetées n’ont plus de H acceptable à demander en mariage.

Il est important de noter que, dans cette procédure asymétrique, c’est pour les F que la Pareto-optimalité est obtenue ; on n’aurait pas forcément le même résultat si c’étaient les H qui faisaient les demandes en mariage. La théorie des jeux semble donc nous indiquer que, certes, en faisant le premier pas on risque de se prendre des coups d’éventail et de se faire jeter, mais que c’est encore le meilleur moyen pour arriver à épouser celui/celle qu’on convoite…

Références

Gale D. et Shapley L. S. (1962). « College admission and the stability of marriage », American Math. Monthly vol 69, pages 9-15

Osborne M. J. (2004). An introduction to game theory, Oxford University Press, New York, NY.