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

L’EPITECH s’internationalise

Epitech LogoPour la quatrième année, les étudiants ont la posssibilité de partir en Chine au Dalian Institute of Light Industries[1]. En novembre 2005, une cinquantaine d’élèves y sont allés. Les français ont d’abord pris des cours de chinois intensifs, et leur collocataires ont fait des efforts pour améliorer leur anglais[2].

En TEK 4, il est également possible d’aller étudier à l’I2IT situé à Pune, une des plus grande ville de l’État indien.

L’École pour l’informatique et les nouvelles technologies (EPITECH) aussi appelée European Institute of Technology, est un établissement privé français de formation en expertise informatique et nouvelles technologies.

Copyright : Tous les textes sont disponibles sous les termes de la GNU Free Documentation License.