Comment découper un wedding cake

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.

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.