Comment diviser équitablement les biens d’un héritage, si tous les héritiers n’ont pas les mêmes préférences? Comment répartir les actifs d’une compagnie en faillite ou ceux d’un couple après un divorce? Comment se partager équitablement les tâches ménagères ou d’autres types de corvées quand les corvéables n’ont pas les mêmes aversions? Comment décider de l’impôt sur le revenu ou d’autres avantages sociaux? Tous ces problèmes font partie de la théorie du partage équitable.

La théorie du partage équitable¹ est un domaine de recherche conjoint aux mathématiques et à l’économie via la théorie des jeux, ainsi qu’à l’informatique théorique pour la recherche d’algorithmes efficaces. On voit tout de suite la difficulté. Que signifie équitable? Les mathématiques sont un langage permettant de donner une définition à un tel concept. Prenons un exemple :

Le partage du gâteau

Maryam et Caucher doivent se partager en deux un gâteau.

Les différents ingrédients sont inégalement répartis, et Maryam et Caucher n’ont pas exactement les mêmes préférences. Une technique proposée est la suivante :

Je coupe, tu choisis.

Ainsi, Maryam sépare le gâteau en deux morceaux qui, pour elle, ont la même valeur. Caucher choisit le morceau qu’il préfère. Ce partage est sans jalousie car ni Maryam, ni Caucher ne peut désirer la part de l’autre plus que la sienne.

Nous avons parlé de la valeur des deux morceaux. On va mathématiser ce concept. À chaque morceau $X$ du gâteau, Maryam et Caucher associent une valeur, qui est un nombre entre 0 et 1. Ce nombre vaut 0 pour l’ensemble vide, et 1 pour la totalité du gâteau. Chacun de nos deux comparses a donc sa fonction valeur définie sur l’ensemble des sous-ensembles du gâteau et prenant ses valeurs dans [0,1]. Appelons $v_M$ celle de Maryam et $v_C$ celle de Caucher. Si $X_M$ est le morceau de gâteau dont hérite Maryam et $X_C$ celui dont hérite Caucher, alors on a $v_M(X_M) = 1/2$ et $v_C(X_C) ≥ 1/2.$ On dit que le partage est proportionnel, ou encore simple, car chaque part a au moins valeur 1/2 pour la personne qui en hérite. Pour que le partage soit équitable il faudrait que $v_M(X_M) = v_C(X_C) = 1/2.$

Ici, il se peut que $v_C (X_C) > 1/2,$ auquel cas le partage n’est pas équitable. Et remarquons la dissymétrie : si c’était Caucher qui avait coupé le gâteau on aurait pu avoir $v_M(X_M) > 1/2$ et $v_C(X_C) = 1/2.$

On voit qu’il existe plusieurs définitions possibles de partage juste, certaines plus fortes que d’autres. Selon le problème et le nombre de comparses un partage équitable existera, alors que dans d’autres cas on ne pourra faire mieux qu’un partage proportionnel.

Un partage équitable existe (voir Problèmes) mais une des portions est en deux morceaux.

Un partage proportionnel d’un gâteau entre $n$ convives

On peut montrer qu’il existe un partage proportionnel du gâteau dans lequel chaque convive reçoit un morceau dont la valeur pour lui est au moins $1/n.$ La preuve et une manière de trouver ce partage sont données par la méthode du couteau mobile. Dans cette méthode un arbitre bouge un couteau parallèlement à une direction donnée. Dès qu’un convive, disons le convive 1, évalue que la portion à gauche du couteau a pour lui une valeur de $1/n,$ il crie « Stop ! ». L’arbitre coupe alors le gâteau à cette position du couteau et le convive 1 hérite du morceau à gauche du couteau. Si $n = 2,$ le deuxième convive reçoit le morceau à droite du couteau. Ceci nous donne un partage proportionnel sans jalousie. En effet, le deuxième convive n’a pas crié « Stop ! ». Donc, il considère que le morceau à gauche a une valeur inférieure ou égale à 1/2, si bien que le morceau qu’il reçoit a, pour lui, une valeur supérieure ou égale à 1/2.

Passer de 2 à $n > 2$ convives se fait très facilement par récurrence : une fois que le convive 1 a reçu le morceau à gauche du couteau, il suffit de partager ce qui reste en $n –1$ morceaux. L’arbitre recommence à bouger son couteau au dessus du morceau de gâteau restant jusqu’à ce qu’un deuxième convive crie « Stop ! » quand il évalue que la portion à gauche du couteau a pour lui une valeur de $1/(n – 1)$ du restant du gâteau, donc au moins valeur $1/n.$ L’arbitre coupe alors le gâteau à cette nouvelle position du couteau et le convive 2 reçoit le morceau à gauche du couteau, etc.

Le partage obtenu est proportionnel, mais il n’est pas nécessairement sans jalousie. Par exemple, il se peut qu’un des morceaux de droite ait une valeur plus grande que $1/n$ pour le premier convive. Dans le cas particulier $n = 3,$ un partage sans jalousie existe.

Un partage sans jalousie d’un gâteau entre trois convives

La méthode des couteaux mobiles de Stromquist permet un tel partage dans le cas de trois convives. On reprend l’idée précédente, mais c’est maintenant un sabre qui est déplacé par l’arbitre. Et cette fois, chacun des convives a aussi son couteau mobile qu’il déplace en même temps que le sabre de l’arbitre. Le sabre et tous les couteaux sont déplacés parallèlement les uns aux autres. Pour un partage sans jalousie les trois convives maintiendront leur couteau à droite du sabre. Dès qu’un convive crie « Stop ! » les couteaux et le sabre s’immobilisent, et le sabre, ainsi que le couteau du milieu sectionnent le gâteau.

Le couteau non transparent est celui qui fait le trait de coupe, de même que le sabre.

Le morceau de gauche va au convive qui a crié « Stop ! ». Le morceau du milieu va à celui des deux autres convives dont le couteau est le plus proche du sabre, donc le plus à gauche. Et le morceau de droite va au dernier convive. Appelons $M_g$ le morceau de gauche, $M_m,$ celui du milieu et $M_d,$ celui de droite, comme sur la figure qui montre les trois morceaux sur un schéma du gâteau de profil.

Chaque convive a une stratégie qui garantit qu’il n’enviera aucun des deux autres convives.

Première partie de la stratégie : chaque joueur place son couteau de telle sorte qu’il coupe la portion du gâteau à droite du sabre en deux portions d’égale valeur pour lui.

Lorsque les convives déplacent leur couteau, à tout instant leurs couteaux sont ordonnés de gauche à droite et, pour simplifier, supposons que les positions des couteaux sont distinctes. Appelons premier convive, celui dont le couteau est le plus à gauche, avec fonction de valeur $v_1,$ deuxième convive, celui dont le couteau est au milieu, avec fonction de valeur $v_2,$ et troisième convive, celui dont le couteau est à droite, avec fonction de valeur $v_3.$ Ainsi sur la figure ci-dessous, les deux morceaux hachurés ont la même valeur pour le premier convive.

Donc,

Et sur la figure ci-dessous les deux morceaux hachurés ont la même valeur pour le troisième convive,

d’où

Deuxième partie de la stratégie de chacun :

• Le premier convive crie « Stop ! » quand la valeur du morceau de gauche devient égale à celle du milieu, c’est-à- dire
  \[v_1(M_g ) = v_1(M_m ) > v_1(M_d ).\]
  Donc il n’est pas jaloux des autres quand il reçoit $M_g.$
• Le deuxième convive crie « Stop ! » quand les deux coupures divisent le gâteau en trois portions d’égale valeur pour lui, c’est-à-dire
  \[v_2(M_g ) = v_2(M_m ) = v_2(M_d ).\]
  Donc il n’est pas jaloux des autres.
• Le troisième convive crie « Stop ! » quand la valeur du morceau de gauche est égale à celle du morceau de droite, c’est-à-dire
  \[v_3(M_g ) = v_3(M_d ) > v_3(M_m ).\]
  Donc il n’est pas jaloux des autres quand il reçoit $M_g.$

Vérifions que, quel que soit le convive qui crie « Stop ! » avant les autres, aucun n’est jaloux des autres.

Le premier convive crie « Stop ! » :

• Pour le deuxième convive,
  \[v_2(M_g ) < v_2(M_m ),\]
  puisqu’il n’a pas crié « Stop ! », et
  \[v_2(M_m ) = v_2(M_d )\]
  par définition de $M_m$ et $M_d.$ Donc, il n’est pas jaloux de recevoir $M_m.$
• Quant au troisième convive,
  \[v_3(M_g ) < v_3(M_d ),\]
  puisqu’il n’a pas crié « Stop ! », et $v_3(M_m) < v_3(M_d),$ par la formule (**). Donc, il n’est pas jaloux de recevoir $M_d.$

Le deuxième convive crie « Stop ! » :

• Alors, pour le premier convive,
  \[v_1(M_g ) < v_1(M_m ),\] puisqu’il n’a pas crié « Stop ! » et $v_1(M_m ) > v_1(M_d ),$ par (*). Donc, il n’est pas jaloux de recevoir $M_m.$
• Quant au troisième convive,
  \[v3(Mg ) < v3(Md ),\]
  puisqu’il n’a pas crié « Stop ! », et $v_3(M_m ) < v_3(M_d )$ par (**). Donc, il n’est pas jaloux de recevoir $M_d.$

Le troisième convive crie « Stop ! » :

• Alors, pour le premier convive,
  \[v_1(M_g ) < v_1(M_m ),\] puisqu’il n’a pas crié « Stop ! » et $v_1(M_m) > v_1(M_d)$ par (*). Donc, il n’est pas jaloux de recevoir $M_m.$
• Pour le deuxième convive,
  \[v_2(M_g ) < v_2(M_m ) = v_2(M_d ),\]
  puisqu’il n’a pas crié « Stop ! ». Donc, il n’est pas jaloux de recevoir $M_d.$

Un partage sans jalousie de corvées entre trois personnes

On peut regarder l’ensemble des corvées comme un gâteau dont chacun veut une part de la plus petite valeur possible, selon sa fonction valeur. La même méthode des couteaux mobiles permet un tel partage sans jalousie avec la nouvelle règle du jeu :

Le morceau de droite va au corvéable qui a crié « Stop ! ». Le morceau du milieu va à celui des deux autres dont le couteau est le plus à droite, donc le plus loin du sabre, et le morceau de gauche va au dernier corvéable.

Première partie de la stratégie : chaque corvéable place son couteau de telle sorte que $M_g$ ait, pour lui, la même valeur que le morceau entre le sabre et son couteau.

Deuxième partie de la stratégie :

• Le premier corvéable crie « Stop ! » quand, pour lui, la valeur de $M_g$ devient égale à la valeur de $M_d.$
• Le deuxième corvéable crie « Stop ! » quand les deux coupures divisent en trois portions d’égale valeur pour lui.
• Le troisième corvéable crie « Stop ! » quand, pour lui, la valeur de $M_m$ devient égale à la valeur de $M_d.$

Nous vous laissons vérifier (voir section Problèmes) qu’aucun corvéable n’est jaloux des autres.

Partager équitablement un loyer

Un groupe de $n$ étudiants et étudiantes se partagent un appartement à n chambres. Certaines chambres sont plus petites, certaines plus éclairées, il y en a une qui est plus proche de la toilette, etc., si bien que tous s’entendent pour convenir de portions différenciées du loyer à payer. De plus, chaque personne est prête à s’accommoder de n’importe quelle chambre si le coût du loyer est nul. Francis Su a montré en 1999 qu’il existe un partage sans jalousie des chambres dans lequel chacune des chambres trouve preneur pour une part du loyer adéquate. Nous allons regarder les cas $n = 2$ et $n = 3.$

Le cas $n=2.$ Soient $x_1$ et $x_2$ les portions respectives du loyer payées pour les chambres 1 et 2. On a $x_1 + x_2 =1$ et $x_1,x_2\in[0,1].$ Donc l’ensemble des $(x_1,x_2)$ est le segment ci-contre.

À l’extrémité inférieure droite chacun choisit la chambre 2 qui est gratuite, alors qu’à l’extrémité supérieure gauche chacun choisit la chambre 1 qui est gratuite. Soit Ahmed et Bernard les deux étudiants. Il existe une valeur $y_A$ de $x_1$ au delà de laquelle Ahmed préfère la chambre 2. De même, il existe une valeur $y_B$ de $x_1$ au delà de laquelle Bernard préfère la chambre 2.

• Si $y_A=y_B,$ on fixe les loyers à $(x_1, x_2) = (y_A, 1–y_A)$ et les gars choisissent une chambre par tirage au sort.
• Si $y_A < y_B,$ on fixe les loyers à $(x_1, x_2) =(y, 1–y)$ pour un $y\in[y_A,y_B],$ Ahmed prend la chambre 2 et Bernard la chambre 1.
• Si $y_A>y_B,$ on fixe les loyers à $(x_1, x_2) =(y, 1–y)$ pour un $y\in[y_B,y_A],$ Ahmed prend la chambre 1 et Bernard la chambre 2.

On peut résumer les trois cas en prenant $y = (y_A+y_B)/2,$ soit le point milieu de l’intervalle d’extrémités $y_A$ et $y_B.$

Le cas $n=3$. Ici nous allons seulement donner les grandes idées de la preuve. Soient $x_1, x_2$ et $x_3$ les portions respectives du loyer payées pour les chambres 1, 2 et 3. On a
\[x_1+x_2+x_3=1, x_1,x_2,x_3\in[0,1],\]
et l’ensemble des $(x_1,x_2,x_3)$ est le triangle équilatéral ci-contre que l’on va projeter sur le plan. Divisons le triangle de cette projection¬ en $m^2$ petits triangles en divisant chacun des côtés en $m$ parties égales. Associons à chaque sommet de triangle l’initiale du nom d’une des trois locataires : Annabelle, Badia ou Cathy, de telle sorte que chaque triangle ait ses trois sommets annotés A, B, C.

La locataire associée à chaque sommet choisit la chambre qu’elle préfère pour les coûts des loyers associés à ce sommet, et ce sommet hérite du numéro de la chambre. Nous affirmons qu’il existe un petit triangle dont les trois sommets héritent des numéros 1, 2 et 3 (voir encadré).

Ceci signifie que, si on regarde les trois sommets du petit triangle, chacune des trois locataires préfère une chambre différente pour un sommet différent. Mais $m$ est arbitrairement grand. Donc, le triangle est très petit et, si l’on prend les loyers au centre du triangle, c’est une très bonne approximation d’une solution exacte. Dans notre exemple Cathy hérite de la chambre 1 (sommet supérieur du triangle), Annabelle hérite de la chambre 2 (sommet gauche) et Badia de la chambre 3 (sommet droit). Une solution exacte peut être trouvée en itérant ce processus avec des $m$ de plus en plus grands, mais les détails sont très techniques et nous ne les ferons pas ici.

L’argument se généralise en dimension quelconque.

Partager équitablement un ensemble d’objets

Jusqu’à maintenant on a partagé des objets « continus ». Mais comment partager équitablement un ensemble discret d’objets, par exemple lors d’un héritage? En effet, on ne peut séparer une maison, une voiture ou une guitare en morceaux. De plus, certains biens ont beaucoup plus de valeur que d’autres. Le sujet est traité abondamment dans la littérature. Nous ne traiterons qu’un exemple.

La méthode de la soumission scellée

Prenons trois héritières, Aissa, Béatrice et Clara qui doivent se partager une maison, une voiture, une guitare, un canot et une bicyclette. Chacune fait une soumission de la valeur qu’a, pour elle, chacun des cinq objets. Voici leurs soumissions respectives en milliers de dollars (notés K).

Que nous dit ce tableau? Que Aissa évalue la totalité des biens à 390K. Comme elle doit recevoir le tiers, alors ce qu’elle devrait recevoir devrait avoir, pour elle, valeur 130K. De même Béatrice évalue la totalité des biens à 330K et ce qu’elle va recevoir devrait avoir, pour elle, valeur 110K. Quant à Clara, ce qu’elle va recevoir devrait avoir, pour elle, valeur 95K.

Regardons encore ce tableau. La soumission montre que Aissa accorde plus d’importance à la maison, alors que Béatrice accorde plus d’importance à la voiture et à la guitare, et que pour Clara, ce sont les équipements sportifs qui sont les plus importants. Dans la méthode proposée, les biens vont être attribués aux plus hauts soumissionnaires. Donc, on va attribuer la maison à Aissa, la voiture et la guitare à Béatrice, et le canot et la bicyclette à Clara. Mais, alors Aissa aura une dette puisqu’elle aura reçu plus que sa part, alors que Béatrice et Clara auront reçu moins que leur part.

La valeur reçue en trop, 230K, sera versée dans un compte. Le montant de ce compte servira à payer les manques à gagner de Béatrice et Clara et le reste sera partagé à parts égales entre les trois héritières. Ainsi, Béatrice recevra d’abord 74K, et Clara, 88K. Il reste dans le compte 68K qui sera partagé à part égales entre Aissa, Béatrice et Clara, soit 22,66K pour chacune. Voici la répartition finale de l’héritage.

À vous de discuter pourquoi cette méthode est raisonnablement équitable et quelle est la meilleure stratégie pour chacune des soumissionnaires.

Pour en s\(\alpha\)voirplus !

• Walter Stromquist, How to Cut a Cake Fairly, The American Mathematical Monthly, Oct., 1980, Vol. 87, No. 8 (Oct., 1980), pp. 640-644, https://www.jstor.org/stable/2320951.
• Francis Su, Rental Harmony: Sperner’s Lemma in Fair Division, The American Mathematical Monthly, Dec., 1999, Vol. 106, No. 10 (Dec., 1999), pp. 930-942, http://www.jstor.com/stable/2589747.
• Dans Wikipedia, https://fr.wikipedia.org/wiki/Partage_équitable.
• Vidéo en anglais parlant du partage de l’héritage : https://www.youtube.com/watch?v=AmkPL2GRewQ.

PDF