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)

Matching

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.

Publicités

Dans la série des recherches Google surréalistes, quelqu’un est arrivé sur ce blog en cherchant « algorithme rangement de cartons ». Je n’ai toujours pas saisi comment il/elle a atterri ici, mais si vous voulez des algorithmes, vous aurez des algorithmes !

Comme certains le savent, je suis étudiante en économie. Plus précisément, ce qui m’intéresse le plus c’est la théorie des jeux et l’économie comportementale. C’est ainsi que j’ai dû réaliser récemment un papier qui synthétisait l’état de la recherche en théorie des jeux, dans un domaine de mon choix parmi plusieurs proposés. Goinfre que je suis, j’ai choisi « cake cutting » : comment découper un gâteau (ou un terrain, ou un héritage…), non homogène de manière juste entre plusieurs personnes dont les préférences sont différentes ?

Par exemple, prenons une pièce montée.

via Flickr

par exemple, celui-là

Et prenons plusieurs mangeurs (« joueurs » en langage théorie des jeux) qui ont des préférences différentes. Une mariée qui n’aime que le chocolat, un marié qui adore la mangue, un témoin qui a horreur de la noix de coco, un beau-père qui aime le café mais déteste le chocolat, une belle-mère qui n’aime pas plus que ça le sucré mais mangerait bien les mariés en sucre au sommet du gâteau. Evidemment, le gâteau n’est pas uniforme, ce ne serait pas drôle sinon.

Comment découper le gâteau de manière juste ? Pour le savoir, on va commencer par définir ce qu’on veut dire par juste :

– on veut attribuer tout le gâteau. Ce qui n’est pas donné aux joueurs serait jeté, ce serait quand même dommage pour cette belle pâte d’amandes !

– ceci est un mariage. On veut maintenir la paix entre les convives, donc on veut éviter qu’ils ne s’envient, aucun d’entre eux ne doit penser qu’un autre n’a reçu une meilleure part que la sienne. Sinon ça dégénère en pugilat, comme à cette assemblée générale d’une grande banque française il y a quelques années, où un actionnaire s’est fait crever un oeil avec une fourchette par un autre qui n’arrivait pas à accéder au buffet.

– le partage doit être équitable. Si la mariée pense que sa part (selon ses critères à elle, à savoir la quantité de chocolat) vaut le tiers de la valeur du gâteau, alors que le marié pense avoir (en termes de quantité de mangue) la moitié de la valeur du gâteau, ce n’est pas équitable.

Comment satisfaire ces trois critères ? Il existe un algorithme bien connu avec deux joueurs, très efficace avec des enfants par exemple : l’un des deux coupe, et l’autre choisit la part qu’il préfère (c’est le partage du royaume de Charlemagne). Par exemple, avec notre marié qui aime la mangue et notre mariée qui aime le chocolat — exemple purement illustratif évidemment :

– le marié coupe le gâteau. S’il ne connaît pas les préférences de la mariée, il se dit que potentiellement n’importe laquelle de deux parts pourra lui revenir. Donc il les coupe de manière à ce qu’elles soient équivalentes pour lui. La mariée choisit alors sa part préférée.

– c’est efficace : tout le gâteau est distribué

– les mariés ne sont pas jaloux l’un de l’autre : la mariée a pris la part qu’elle préférait, donc elle n’est pas jalouse ; et le marié a l’autre part, qui correspond pour lui à la moitié exactement de la valeur du gâteau, il n’est pas jaloux non plus

– cependant… pour le marié, la part qu’il a représente la moitié du gâteau. Mais pour la mariée, sa part peut représenter beaucoup plus que la moitié du gâteau : par exemple, si chaque part contient la moitié du fourrage à la mangue mais que le chocolat est réparti pour un quart dans une part et trois quarts dans l’autre, la mariée choisit sa part préférée et obtient, à ses yeux, les trois quarts du gâteau. Ce n’est pas équitable.

Mais il y a pire. On peut supposer que, puisqu’ils se marient, le marié sait que sa fiancée est une goinfre qui n’aime que le chocolat. Il peut exploiter cette préférence à son avantage :

– il coupe le gâteau de manière à ce que toute la mangue soit dans une part, en laissant un peu plus de la moitié du chocolat dans l’autre. La candide mariée choisit alors la part qui contient le plus de chocolat.

– aucun d’eux n’est jaloux de l’autre, mais la disproportion entre leurs parts augmente : la marié s’arroge toute la valeur du gâteau à ses yeux, alors que la mariée n’en a qu’un peu plus de la moitié à ses yeux : en exploitant l’information dont il dispose, il augmente sa part en spoliant la mariée. Un partage qui aurait donné toute la mangue au marié et tout le chocolat à la mariée aurait été plus efficace : elle aurait eu une meilleure part, sans que lui n’en ait une moins bonne.

L’algorithme « partage de Charlemagne » est donc insuffisant : d’une part il ne satisfait pas tous nos critères, et d’autre part il ne peut s’appliquer qu’à deux joueurs. Que faire des témoins, de la belle-mère et des enfants qui piaffent d’impatience devant le gâteau ? A qui confier la pelle à tarte ?

… la suite au prochain épisode…

Source : Brams S. J. et Taylor A. D. (1996) Fair Division : From Cake-Cutting to Dispute Resolution. Cambridge University Press, Cambridge.