Partage équitable

En économie, mais aussi en mathématiques, et plus particulièrement en théorie des jeux, le problème du partage équitable, connu aussi sous le nom de problème de partage du gâteau (de l'anglais : cake cutting problem), est le problème du partage d'une ressource de telle sorte que tous les participants estiment en avoir reçu une part « satisfaisante ».

Le problème peut s'avérer plus simple si chaque participant a une mesure différente de la valeur de la ressource : dans le cas du gâteau, l'un peut aimer la pâte d'amandes, l'autre préférer les cerises, et ainsi de suite ; dans ce cas, il est même possible que chacun des n participants reçoive plus que le n^e de ce que serait la valeur du « gâteau » pour lui. Mais en général, la présence de mesures distinctes fait apparaître de nombreuses questions difficiles, et donne lieu à des recherches encore ouvertes.

Il y a de nombreuses variantes du problème. La définition de « équitable » peut simplement signifier que chacun reçoit ce qu'il estime être une juste fraction du total, ou des contraintes plus sévères telles que l’absence d'envie peuvent aussi être imposées. Les algorithmes théoriques s'intéressent essentiellement aux biens qui peuvent être partagés sans perdre de valeur, mais le partage de biens indivisibles, comme dans le cas d'un divorce, est également un problème pratique important. Le partage des tâches est une variante où les biens à partager sont indésirables.

La division de Berlin par la conférence de Potsdam

Hypothèses

La théorie du partage équitable est une théorie mathématique basée sur une idéalisation d'un problème réel, consistant à diviser équitablement des biens ou des ressources entre des participants, les « joueurs », qui y ont un droit. Le principe fondamental de la théorie est que les joueurs devraient faire le partage eux-mêmes, peut-être en utilisant un médiateur, mais certainement pas un arbitre, les joueurs seuls connaissant leur estimation des biens.

La théorie donne des critères explicites correspondant à différents types d'équité. Son but est d'obtenir des procédures algorithmiques aboutissant à un partage équitable, ou de démontrer leur impossibilité, et d'étudier les propriétés de ces partages, aussi bien en théorie qu'en pratique.

Les hypothèses sur l'évaluation des biens ou des ressources à partager sont que :

• Chaque joueur a une opinion sur la valeur de chaque partie des biens ou des ressources
• Pour chaque joueur, la valeur d'une union de parts est la somme des valeurs qu'il attribue à chaque part. Il est d'ailleurs souvent suffisant de demander que ces évaluations soient faiblement additives.
• On suppose souvent, pour simplifier, que les biens peuvent être divisés en parts de valeurs arbitrairement faibles.

Des biens indivisibles rendent la théorie beaucoup plus complexe. Ainsi, le partage d'une voiture et d'une moto est d'autant plus difficile que leurs valeurs ne s'ajoutent pas clairement, les deux pouvant être utilisés comme moyen de transport. Dans des cas de ce genre, l'utilisation de compensations monétaires simplifie nettement le problème.

Les critères d'un partage équitable sont énoncés, pour chaque joueur, en termes de son évaluation des biens et de ses droits sur eux. Les évaluations des autres joueurs ne sont pas prises en compte dans ces critères. En pratique, les joueurs ont parfois une idée précise des évaluations des autres participants, et cela peut modifier leur stratégie. Le cas où cette connaissance est complète peut être modélisé par la théorie des jeux. Il est en revanche difficile de modéliser le cas d'une connaissance imparfaite, et un des plus importants problèmes de la théorie du partage, en pratique, est de construire des procédures robustes face à de telles connaissances partielles, ou à de petites erreurs d'évaluation.

Une procédure de partage équitable définit les actions qui doivent être accomplies en termes des données (visibles) et de leurs évaluations. Une procédure est valide si elle garantit un partage équitable pour chaque joueur agissant rationnellement en fonction de ses évaluations. Lorsqu'une action dépend de l'évaluation d'un joueur, la procédure décrit la stratégie qu'un joueur rationnel doit suivre ; les actions d'un joueur donné doivent être cohérentes. Ainsi, si la procédure stipule que le premier joueur doit découper en parts égales, puis que le second doit en choisir une, le premier joueur ne peut prétendre que le second est avantagé à ce stade.

L'ensemble des joueurs dans un problème de partage équitable doit :

• S'accorder sur leurs critères concernant la notion d'« équité »
• Sélectionner une procédure valide et suivre ses règles.

On admet que le but de chaque joueur est de maximiser le résultat minimum qu'il obtiendra, en d'autres termes, d'atteindre le maximin.

On peut distinguer les procédures discrètes des procédures continues : une procédure discrète, par exemple, demanderait à chaque étape qu'un joueur (seulement) coupe ou marque le gâteau, alors qu'une procédure continue pourrait amener ce joueur à déplacer (continûment) le couteau jusqu'à ce qu'un autre joueur l'arrête.

Critères pour un juste partage

De nombreux critères peuvent être choisis pour caractériser un partage. Certains d'entre eux sont incompatibles, mais on peut souvent en combiner plusieurs autres. Ceux décrits ici supposent de plus que les joueurs aient les mêmes droits sur les biens à partager.

• Un partage est proportionnel (en) (ou simple) s'il garantit le même résultat à chaque participant, pour sa propre évaluation. Ainsi, si trois personnes se partagent un gâteau, chacune doit estimer en avoir reçu au moins un tiers.
• Un partage est sans jalousie si nul ne désire la part reçue par un autre plus que la sienne.
• Un partage est exact (en) si chaque joueur estime que tous ont reçu leur juste part, ni plus, ni moins.
• Un partage est efficient (ou est un optimum de Pareto) si aucun autre partage ne pourrait accroître l'avantage d'un joueur sans en léser un autre. Ce terme vient de la notion économique de marché efficient. Un partage léonin, dans lequel l'un des participants reçoit tout, est optimal à ce sens ; cette notion ne garantit donc nullement une quelconque « justesse » du partage.
• Un partage est équitable (au sens économique) quand, pour son estimation, chacun des n participants a reçu un n-ième de la valeur totale du bien à partager. Cet objectif est difficile à atteindre en pratique, les joueurs pouvant éventuellement dissimuler leurs véritables évaluations ; de plus, on a vu dans l'introduction qu'il n'est pas forcément efficient, dans le cas où les joueurs ont des évaluations très différentes les unes des autres.

Deux joueurs

Pour deux joueurs, il y a une solution simple fréquemment utilisée, connue sous le nom de « je coupe, tu choisis (en) » : l'un des joueurs divise la ressource en deux parties de valeurs qu'il estime égales, et l'autre joueur choisit la « moitié » qu'il préfère. Ainsi, le joueur effectuant le partage est motivé pour le rendre le plus juste possible, faute de quoi il risque fort de recevoir la part qu'il ne désire pas.

Cette solution donne un partage proportionnel et sans jalousie. Cependant, ce partage n'est pas équitable. Des procédures plus complexes, telles que la procédure du gagnant ajusté (en), permettent de traiter le cas de biens indivisibles, et sont plus équitables en pratique.

La procédure à couteaux mobiles de Austin (en) donne un partage exact (mais pas nécessairement efficace) pour une ressource continûment divisible. Le premier joueur place deux couteaux au-dessus du gâteau ; au départ, l'un des couteaux est à l'extrémité gauche, et l'autre partage le gâteau en deux portions de même valeur (pour lui). Il déplace les couteaux vers la droite de telle sorte qu'il y ait à tout moment la "moitié" du gâteau (toujours selon son évaluation) entre les lames (ainsi, s'il atteint la droite du gâteau, le couteau de gauche doit se retrouver à la position de départ de celui de droite). Le second joueur l'arrête lorsqu'il estime que la moitié du gâteau est entre les lames ; cela se produit nécessairement au moins une fois, à cause du théorème des valeurs intermédiaires.

La procédure des surplus (en) permet une forme d'équité connue sous le nom d’équité proportionnelle. Cette procédure est stratégiquement robuste (en) et peut se généraliser à plus de deux joueurs.

Davantage de participants

La théorie du partage avec trois joueurs ou plus est considérablement plus complexe que dans le cas de deux joueurs.

Le partage proportionnel (en) est le plus simple ; l'article détaillé décrit certaines des procédures qui peuvent être utilisées par un nombre arbitraire de participants. La détermination du nombre minimal de coupes nécessaires s'est avérée être un problème mathématique intéressant et difficile.

Le problème du partage sans jalousie, dans le cas de trois joueurs, fut résolu indépendamment en 1960 par John Selfridge et par John Horton Conway. Le meilleur algorithme utilise au maximum 5 coupes.

La procédure de Brams-Taylor (en) a été la première à donner un partage sans jalousie pour un nombre quelconque de participants ; elle fut publiée par Steven Brams et Alan Taylor en 1995. Le nombre de coupes que demande cette procédure n'est pas borné. Une procédure à couteaux mobiles en un nombre borné d'étapes fut trouvée en 1997 dans le cas de quatre joueurs.

Même pour deux joueurs, il n'y a pas d'algorithme discret permettant un partage exact, une procédure continue à couteaux mobiles est le mieux qu'on puisse faire. Il n'existe même pas de procédure continue donnant un partage exact pour 3 joueurs ou plus, mais on connait des algorithmes discrets "presque exacts", sans jalousie, permettant d'obtenir un partage à une précision aussi grande que l'on veut (ces partages, décrits plus bas, utilisent de manière surprenante un résultat mathématique de topologie combinatoire connu sous le nom de lemme de Sperner).

Une généralisation de la procédure des surplus (en), appelée procédure équitable, atteint l’équité proportionnelle, mais l'équité et l'absence d'envie sont en général incompatibles pour 3 participants ou davantage.

Variantes

Une importante variante du problème du partage équitable est le problème de la division des tâches (en) : c'est le "dual" du problème du partage du gâteau, quand l'objet à partager est indésirable ; dans le cas de deux joueurs, les mêmes procédures s'appliquent. Plus généralement encore, on peut avoir à partager des biens en payant pour leur usage ; c'est le problème des loyers. Un résultat fondamental à ce sujet, le Rental Harmony theorem (théorème de l'harmonisation des loyers) a été démontré par Francis Su en 1999. Une application intéressante de ce théorème peut être faite à la théorie du commerce international.

Le lemme de Sperner (utilisé également dans la démonstration de Francis Su) permet d'obtenir une approximation aussi précise que l'on veut à des partages sans jalousie pour un nombre quelconque de participants. Cet algorithme donne une procédure explicite et rapide résolvant de nombreux problèmes de partage.

La division de biens, notamment en cas de divorce ou d'héritage, contient souvent des objets indivisibles dont la distribution équitable ne peut se faire qu'à l'aide de compensations monétaires.

Des contraintes supplémentaires apparaissent parfois : ainsi, lors du partage de terrains, on souhaite que les parcelles restent d'un seul tenant. Un exemple emblématique est la partition de l'Allemagne, et tout particulièrement de Berlin, à la fin de la Seconde Guerre mondiale.

Historique

Selon Sol Garfunkel (en), les problèmes de partage équitable (à plus de deux joueurs) faisaient partie des plus importants problèmes ouverts des mathématiques du XX^e siècle, jusqu'à ce que la variante la plus fréquente du problème soit résolue grâce à la procédure de Brams-Taylor, en 1995.

La procédure « je coupe, tu choisis (en) » a été utilisée dès l'Antiquité, et probablement même déjà dans la Préhistoire. Les activités économiques primitives que sont le marchandage et le troc lui sont liées, et sont tout aussi anciennes.

Cependant, la théorie du partage équitable ne date que de la fin de la Seconde Guerre mondiale. Elle fut développée par un groupe de mathématiciens polonais, Hugo Steinhaus, Bronisław Knaster et Stefan Banach, qui avaient l'habitude de se réunir au Café écossais de Lwów (ville située en Pologne à cette époque). Une procédure de partage proportionnel (en) pour un nombre arbitraire de joueurs, connue sous le nom de procédure du dernier réducteur, fut découverte en 1944. Steinhaus l'attribua à Banach et Knaster, quand il exposa le problème pour la première fois à une réunion de l'Econometric Society, en 1947.

Le problème du partage sans jalousie, dans le cas de trois joueurs, fut résolu indépendamment en 1960 par John Selfridge (à la Northern Illinois University) et par John Horton Conway (à l'université de Cambridge) ; leur algorithme fut d'abord publié dans la rubrique de « Jeux mathématiques  » tenue par Martin Gardner dans le Scientific American.

Le même problème pour 4 joueurs ou plus resta ouvert jusqu'à la fin du XX^e siècle. La première solution de ce problème fut trouvée par Steven Brams et Alan Taylor en 1995. Une importante avancée sur le problème du partage équitable fut obtenue en 2006 par Steven J. Brams, Michael A. Jones, et Christian Klamler.

Dans la culture populaire

Dans l'épisode 'One Hour' de la saison 3 de Numb3rs, Charlie parle de ce problème pour l'appliquer à la somme d'argent que demande un kidnappeur.

Hugo Steinhaus décrit diverses variantes dans son livre Mathematical Snapshots (instantanés mathématiques), et signale que des cas particuliers du problème pour 3 joueurs avaient été résolus par G. Krochmainy et Mrs L Kott dès 1944.

Martin Gardner et Ian Stewart ont tous deux publiés des livres contenant des sections consacrées à ce problème. Martin Gardner introduisit le problème dual de la division des tâches. Ian Stewart popularisa le problème avec ses articles dans Scientific American et New Scientist.

Un épisode de la série en bande dessinée Dinosaur comics (en) détaille ce problème.

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Fair division » (voir la liste des auteurs).

Sources

• (en) Steven J. Brams et Alan D. Taylor (1996). Fair Division - From cake-cutting to dispute resolution Cambridge University Press (ISBN 0-521-55390-3).
• (en) T.P. Hill (2000). "Mathematical devices for getting a fair share", American Scientist, Vol. 88, 325-331.
• (en) Jack Robertson et William Webb (1998). Cake-Cutting Algorithms: Be Fair If You Can, AK Peters Ltd (ISBN 1-56881-076-8).

Voir aussi

Bibliographie

• (en) Vincent P. Crawford (1987), « Fair division », The New Palgrave: A Dictionary of Economics, v. 2, p. 274-75
• (en) Hal Varian (1987), « Fairness », The New Palgrave: A Dictionary of Economics, v. 2, p. 275-76
• (en) Bryan Skyrms (1996). The Evolution of the Social Contract Cambridge University Press (ISBN 978-0-52155583-8)
• Jean-Paul Delahaye, « Les partages équitables d'une tarte », Pour la science, n^o 476,‎ juin 2017, p. 80-85
• Jérôme Cottanceau, Le choix du meilleur urinoir : Et 19 autres problèmes amusants qui prouvent que les maths servent à quelque chose !, Paris, Belin, coll. « Science à plumes », 2016, 216 p. (ISBN 978-2-7011-9766-1), chap. 6 (« À quoi servent les maths... À partager équitablement une tarte aux ananas, aux kiwis et aux cerises ? »)

Articles connexes

• Théorie des jeux
• Commerce international
• Règle du gâteau
• Problème du sac à dos
• Théorème du sandwich au jambon
• Lemme de Sperner
• Steven Brams
• Tragédie des anticommuns
• Tragédie des biens communs
• Théorème de Hobby-Rice

Liens externes

• (en) Short essay about the cake-cutting problem par S. Abbas Raza, de 3 Quarks Daily.
• (en) Fair Division, Discrete Mathematics Project, University of Colorado.
• (en) The Fair Division Calculator (applet java)
• (en) Fair division sur cut-the-knot : Method of Lone Divider, Method of Markers, Method of Sealed Bids