A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents

Re:A Discrete and Bounded Envy-Free Cake Cutting Protocol fo... by LodeOfCode on Sunday January 21, 2024 @01:32AM (#39076175)

Couldn't you just 1. Draw an arbitrary line through the cake 2. Set each person's valuation of a point on the line equal to their valuation of the cross section throgh that point 3. Use the algorithm to cut the 1D pseudocake 4. Make the corresponding cross sectional cuts to the real cake

Actually for round cakes you could even make normal (wedge-shaped) pieces by re-parameterizing distance along the line as angle and cross sections as infinitesimal wedges.

Edit: And for the rectangular cake you could slice the cake up along one axis and line those pieces up end-to-end first so that the cross sections would have a reasonable width instead of having slices as wide as the whole cake

[ Parent | on HN ]

Re:A Discrete and Bounded Envy-Free Cake Cutting Protocol fo... by charcircuit on Sunday January 21, 2024 @02:21AM (#39076401)

>3. Use the algorithm to cut the 1D pseudocake

Making multiple cuts along a line doesn't seem optimal. Remember that these slices of 3D cake can be of any shape. You can imagine different people liking different fillings or different toppings on the cake.

[ Parent | on HN ]