Coupe le cake

Dimanche midi chez la belle-mère, l'heure du dessert est enfin arrivée. Chargé de la tâche difficile qui consiste à découper le gâteau, vous mettez à profit vos connaissance en géométrie pour couper des parts de tailles parfaitement égales, puis les attribuez à chacun des convives. Mais très vite, vous entendez...
- Hey, ya plein de croûte sur ma part, ça compte pas !
- C'est injuste, elle a une part avec plus de chocolat que la mienne !
- Mais... Pourquoi j'ai autant de fraises ? J'aime pas les fraises !

Il faut se rendre à l'évidence : vous avez coupé le gâteau n'importe comment, sans prendre en compte les envies de chacun ! Pour que le partage d'un gâteau (ou de n'importe quel mets partageable, comme une pizza, un plat de lasagnes, ou un lapin en chocolat) soit complètement équitable, il ne peut pas être l'œuvre d'un seul maître-coupeur tout puissant. Mais comment procéder ? La question est discutée depuis (au moins) les années 50, et de nombreuses réponses ont été apportées. La découpe d'un gâteau n'appartient pas qu'au domaine de la géométrie, il appartient aussi à celui de la théorie des jeux.

Un partage équitable pour un convive ne l'est pas forcément pour les autres...

Dans la suite, on appellera G1, G2, ..., GN les N gourmands appelés à partager le gâteau. Chacun d'eux a sa propre vision du gâteau (une mesure μ sur le gâteau) : une part d'un gâteau marbré contenant beaucoup de chocolat peut être considérée comme petite pour G1 qui n'en raffole pas, mais comme grande pour G2 qui adore le chocolat. Cependant, chacun est capable de décider entre plusieurs parts laquelle sera la meilleure ; de même, chacun est capable de couper le gâteau en plusieurs parts d'égales valeur à ses yeux. 

Pour toute part, chacun peut associer un nombre entre 0 et 1 : sa mesure (allant de 0 pour une part vide à 1 pour le gâteau entier).  Chaque convive a une mesure qui lui est propre. Pour qu'un partage soit équitable (plutôt appelé "proportionnel"), il faudra donc que chaque invité reçoive une part de mesure supérieure ou égale à 1/N à ses yeux (que j'appellerai par la suite "part acceptable"). L'équité parfaite (que pour chaque gourmand, chaque part soit de valeur 1/N) est la plus difficile à obtenir.

On supposera que chacun des gourmands ne connaît pas les préférences des autres. On supposera aussi que chacun utilise une stratégie qui garantit le gain maximal, sans aucune prise de risque.

Deux gourmands : "Je coupe, tu choisis"
Première situation : soirée pizza-cocooning en amoureux. Quand il est question de pizza, les choses deviennent sérieuses : comment partager la pizza sans qu'aucun ne soit lésé ? Le partage est en fait assez facile à faire :

Étape 1 : G1 coupe la pizza en deux parts (qu'il juge égales)
Étape 2 : G2 choisit la part de son choix (qu'il juge la plus grande), et G1 reçoit l'autre part.

Ainsi, si G1 choisit de ne pas couper la pizza en deux parts égales et que G2 choisit la part la plus grande, il sera le seul responsable de cette injustice. Evidemment, cette méthode ne fonctionnera pas avec votre chéri(e) qui se sacrifiera pour vous laisser la part la plus grande...

Trois gourmands : "Je coupe, vous choisissez" - Steinhaus - 1943
Deuxième situation : cake entre potes. Vous avez invité deux très bons amis à partager un cake aux olives, mais ceux-ci partagent la même envie que vous d'obtenir la part du lion. Hugo Steinhaus, célèbre pour un théorème en analyse fonctionnelle, est le premier à avoir mis en place en 1943 une méthode permettant le partage proportionnel entre trois personnes :

Étape 1 : G1 coupe le cake en trois parts (qu'il juge égales)
Étape 2 : G2 inspecte les trois parts, et peut décider :
     - soit de passer son tour (si il juge que au moins deux parts sont acceptables)
     - soit de marquer deux parts comme "mauvaises" (les parts qu'il estime non acceptables)
Étape 2 bis : si G2 a passé son tour, les parts sont réparties selon l'ordre suivant : G3, G2, G1.
Étape 3 : si G2 n'a pas passé son tour, G3 dispose des mêmes options : passer son tour ou marquer deux parts comme mauvaises.
Étape 3 bis : si G3 a passé son tour, les parts sont réparties selon l'ordre suivant : G2, G3, G1.
Étape 4 : si ni G2, ni G3 n'ont passé leur tour, G1 doit choisir la part (ou l'une des deux parts) marqué à la fois par G2 et G3 comme mauvaises.
Étape 5 : Il reste alors deux parts, que l'on réunit en une seule. G2 et G3 vont alors appliquer la méthode "Je coupe, tu choisis" : G2 coupe le cake en deux parts (qu'il juge égales), G3 choisit la part de son choix puis G2 prend la dernière part.

Si chacun agit de façon rationnelle, tous les gourmands auront une part acceptable. Dans tous les cas, G1 sera le dernier à choisir, il lui faut donc être égalitaire lors de sa première découpe. A l'étape 2, G2 ne passera que si cela lui assure d'avoir une part acceptable ; s'il ne passe pas, il aura une part acceptable quel que soit le choix de G3. Bref : ce partage assure à chacun la part de cake qui lui faut.

N gourmands : "Les enchères" - Banach & Knaster - 1944
Troisième situation : soirée Donjons et Dragons avec plusieurs amis geeks. Après trois heures de jeu, c'est le moment de faire une pause, puisque le MJ a préparé son fameux far breton qui fait sa renommée. En bons geeks que vous êtes, vous avez opté pour la méthode de Banach et Knaster, qui promet une découpe équitable pour tout le monde :

Étape 1 : G1 coupe une part P₁ (qu'il juge de taille 1/N)
Étape 2 : G2 a deux possibilités :
       - passer son tour (si'l juge la part non acceptable)
       - élaguer la part P₁, qui devient P₂ (de façon à ce que la part tronquée soit pour G2 de taille 1/N).
Étape 3 : Tous les gourmands, de G3 à GN, font de même (passer ou élaguer), transformant la part P_i en une part P_i+1 strictement plus petite. Le dernier qui a découpé une part repart avec celle-ci.
Etape 4 : On réassemble le surplus découpé avec le gros du far, puis on recommence les étapes 1 à 3 avec les N-1 gourmands restant, jusqu'à ce qu'il n'en reste plus que 2. On appliquera alors la méthode "Je coupe, tu choisis".

Évidemment, personne ne peut préjuger de l'état du far à la fin du processus, mais chacun est garanti d'obtenir une part qu'il juge de taille 1/N. En effet, les parts P₁, P₂, ..., P_k forment une suite de parts strictement décroissante pour tous les gourmands, et de taille exactement 1/N pour le dernier qui a fait la découpe.

N gourmands : "Le couteau glissant" - Dubins & Spanier - 1961
Quatrième situation : votre mariage ! Le plus important du repas est arrivé, le dessert ! Toute votre famille est présente pour célébrer la noce, mais elle est surtout là pour goûter la pièce montée. Mais vos 40 invités ne plaisantent pas avec l'équité, chaque invité doit recevoir une part acceptable. Tradition oblige, c'est aux mariés de faire la découpe, on est pas dans cette soirée D&D où le far breton s'est terminé en bouillie.

La méthode du couteau glissant est parfaite pour une telle occasion, puisqu'une seule personne tiendra le couteau pour toute la découpe. Encore une fois, elle assure que chaque invité reçoive une part de taille 1/N. Contrairement aux méthodes précédentes, il ne s'agit pas d'un protocole constitué d'une succession d'étapes (discret), mais d'un processus où tous les gourmands peuvent agir en même temps (continu). 

En partant du bord, les époux tiennent le couteau au-dessus du gâteau, puis ils le glissent lentement, de façon à balayer le gâteau. Dès qu'un invité est satisfait de la part qui sera découpée (dès qu'elle devient acceptable), il crie "stop !", et on lui attribue cette part. On continue alors avec le reste du gâteau et le reste des invités. Les deux derniers invités (on supposera qu'il sagit des époux) se partageront naturellement les deux dernières parts. Stratégiquement, il ne faut pas chercher à être plus gourmand que les autres, sous peine de se voir chiper sa part !

3 gourmands : "Pas de jalousie" - Selfridge & Conway - 1960
Cinquième situation : goûter d'enfants. L'heure est grave, vous devez partager un délicieux flan entre trois enfants. L'équité, ils s'en fichent ; tout ce qu'ils veulent, c'est de ne pas avoir une part plus petite que quelqu'un d'autre !

On ne cherche plus ici à ce que le partage soit proportionnel (que toutes les parts soient supérieures ou égales à 1/3), mais qu'il soit en plus "sans jalousie" : chaque gourmand doit avoir la part la plus grande, selon sa mesure. La méthode "Je coupe, tu choisis" pour deux personnes est sans jalousie, mais ce n'est pas le cas pour la méthode de Steinhaus. La procédure de Selfridge-Conway (découverte par Selfridge en 1960, mais non publiée, puis redécouverte par Conway dans les années 1990) répare cette injustice :

Étape 1 : G1 coupe le gâteau en 3 parts (qu'il juge égales)
Étape 2 : G2 a deux possibilités :
     - ne rien faire (si il juge que les deux plus grandes parts sont égales)
     - retirer un morceau M d'une des parts (de façon à rendre égales les deux plus grandes parts). Le morceau M est laissée de côté.
Étape 3 : G3, G2 et G1 choisissent à tour de rôle une part parmi les (au moins) trois restantes en suivant la règle suivante : si une part a été découpée à l'étape 2 et que G3 ne la choisit pas, elle reviendra impérativement à G2.
Étape 4 (si un morceau M a été mis de côté à l'étape 2) : La part recoupée à l'étape 2 a été attribuée soit à G2, soit à G3. Appelons GN celui qui l'a reçu, et GC l'autre. GC coupe alors le morceau M en 3 parts (qu'il juge égale)
Étape 5 : Ces trois parts sont attribuées selon l'ordre suivant : GN, G1 et GC

Ce protocole assure que personne n'obtienne une part plus petite que les autres, même si cela n'est pas forcément évident. A l'issue de l'étape 3, G1 reçoit une part de son découpage initial, donc, de taille 1/3 (si une part a été réduite, elle a été choisie par GC, c'est à dire, soit G2, soit G3). G3 ayant eu le choix dans les parts, il choisira la part la plus grande pour lui : pas de jalousie. Quant à G2, il a fait en sorte que les deux plus grandes parts soient égales, il reçoit donc l'une de ces deux parts : pas de jalousie non plus.
Dans le cas où il y a un morceau M, on peut remarquer que la grande part de G1 est, du point de vue de G1, strictement plus grande que celle de GN (à cause du déficit créé par le morceau M), et égale à celle de GC. Par ce fait, le morceau de M choisit par GN, quel qu'il soit, n'entraînera aucune jalousie de la part de G1. 

Ce partage sans jalousie entre trois personnes a l'avantage de ne demander que, au plus, 4 coups de couteau. Il existe des moyens de partager sans jalousie entre N personnes, mais ces méthodes peuvent entraîner un nombre arbitrairement grand de coups de couteau (mais toujours fini). La question du partage sans jalousie borné en temps entre N personnes est toujours ouvert !

Il existe aussi des variantes de la méthode du couteau-glissant, en particulier celle de Stromquist pour N=3 convives, qui demande d'avoir 4 couteaux, mais qui entraîne un partage sans jalousie. Il existe aussi des procédures permettant l'équité parfaite entre N gourmands, mais elle implique qu'un arbitre connaisse exactement les goûts de chacun. On peut aussi se poser la question du partage équitable d'une tarte aux concombres, où tous les invités cherchent à avoir la part la plus petite...

---

Sources :
En envy-free cake division protocol. Steven Brams, Alan Taylor, The Matematical Monthly
Better ways to cut a cake. Steven Brams, Michael Jones, Christian Klamler, Notices of the AMS.

Comments

[Julio974]

Le problème du partage sans jalousie non-borné entre N personnes a été résolu par Aziz et Mackenzie en 2016 ! https://arxiv.org/abs/1604.03655

[mimi1931]

J'ai déjà utilisé la méthode: je coupe, tu choisis, pour partager un gros roti acheté en commun sans le peser.

J'utilise souvent la méthode du couteau glissant lorsque nous ne sommes que 3 ou 4 pour manger une grande tarte.

Une méthode dont tu ne parles pas. J'avais 7 enfants. Pour couper un gâteau en 9, je retirais un petit huitième et je coupais le reste en 8.

[Erbaf]

Effectivement dans le protocole dont je parlais le dernier C a un certain pouvoir de " chantage", il peut refuser de partager le gateau (mais alors il ne mangera pas non plus). Donc ce n'est certainement pas sans jalousie...

[Erbaf]

Bonsoir

Je me rappelle avoir lu il y a quelque temps un protocole interessant pour un partage entre 3 convives, avec 2 couteaux (qui marchera mieux avec des gateaux allonges, style buche de noel)



A pose son couteau sur le gateau, a l'endroit ou il souhaite decouper sa part (mais sans couper tout de suite).



Ensuite B fait de meme, et indique la ou il souhaite decouper sa part.



C examine la part restante. Soit elle lui convient, il dit "coupez". Sinon,si il s'estime lésé, il demande a A puis a B de reduire leurs pretentions en deplacant leurs couteaux, jusqu'a ce que la part restante lui convienne.

De cette maniere, le partage ne se fait que quand chacun des 3 a une part qui lui convient. A et B ont chacun choisi la leur, et C n'autorise le partage que quand il est satisfait de ce qu'on lui a laissé !

Et en plus on evite de reduire le gateau en bouillie...

[Voon]

Les mariés risquent d'avoir une part extrêmement petite si ils doivent attendre la fin de la distribution pour prendre part au choix... :D