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'), 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 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.
vignette|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 euxEn théorie du partage, il s'agit d'un terme technique, correspondant (par exemple) aux investissements préalables des joueurs dans les biens à partager. Pour plus de détails, voir l'article anglais sur l'entitlement. 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 (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 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 « » : 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 équitableCette question est analysée plus en détail dans l'article . Des procédures plus complexes, telles que la , permettent de traiter le cas de biens indivisibles, et sont plus équitables en pratique.
La A.K. Austin. Sharing a Cake. Mathematical Gazette 66 1982 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 permet une forme d'équité connue sous le nom d’équité proportionnelle. Cette procédure est 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 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 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 , 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 : 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 1999Francis Edward Su, Rental Harmony: Sperner's Lemma in Fair Division Amer. Math. Monthly, 106(1999), 930-942. http://www.math.hmc.edu/~su/papers.dir/rent.pdf. Une application intéressante de ce théorème peut être faite à la théorie du commerce internationalShiozawa, Y. A New Construction of a Ricardian Trade Theory, Evolutionary and Institutional Economics Review 3(2)(2007) 141-187..
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 partageFrancis Edward Su,Rental Harmony: Sperner's Lemma in Fair Division (d'après les travaux de Forest Simmons en 1980)The Fair Division Calculatorhttp://www.maa.org/mathland/mathtrek_3_13_00.html A Fair Deal for Housemates. Ivars Peterson's MathTrek. March 13, 2000.
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.