Problème de partage du gâteau


Le problème du gâteau (de l’anglais cake cutting problem) est un problème de distribution de ressources (par la division) de telle façon que chaque participant reçoive une part équitable. Le problème est ardu puisque chaque protagoniste peut avoir une « mesure » différente d’une ressource, tel un gâteau : un destinataire aime la pâte d’amande, un autre la cerise, etc.

S’il y a deux personnes, la solution est simple : l’un divise, l’autre choisit. Explication : celui qui divise est obligé de couper en parts égales, au sens de l’équité, puisque sinon, il risquerait de recevoir une part qui ne lui conviendrait pas.

C’était un des problèmes importants du XXe siècle, jusqu’à ce qu’il soit résolu conjointement par Steven Brams et Alan Taylor en 1995.

Plusieurs personnes

La première personne divise la ressource en 2 dans des parts qui lui semble égale. La seconde personne choisit sa part. Les deux premières personnes découpent leur part en 3. La troisième personne choisit une part chez chacun des deux 1er participants. Les trois premières personnes découpent leur part en 4. La quatrième personne choisit une part chez chacun des 3 premiers participants et ainsi de suite.

Plus le nombre de personnes augmente, plus trouver la solution optimum devient complexe.

Notes et références

  • S. J. Brams, A. D. Taylor, An Envy-Free Cake Division Protocol, American Mathematical Monthly 102, 9-19, 1995.
  • Jack Robertson, William Webb, Cake-Cutting Algorithms: Be Fair If You Can, AK Peters Ltd, March 1998, (ISBN 1568810768).
  • B. Skyrms, The Evolution of the Social Contract Cambridge University Press, 1996, (ISBN 139780521555838).

Articles connexes

Liens externes

Laisser un commentaire

Choisissez une méthode de connexion pour poster votre commentaire:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s

%d blogueurs aiment cette page :