4 ms·

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

24 points by luu 3y ago

nomilk 3y ago
> The maximum number of queries required by the protocol is n^n^n^n^n^n I'm impressed that rendered correctly, never seen that before. Got a minimal version working: code: https://pastebin.com/CqCzH8H7 https://pastebin.com/CqCzH8H7 what it looks like: https://imgur.com/a/v2PU1mH https://imgur.com/a/v2PU1mH
- matt-tingen 3y ago
  Or with MathML: https://jsfiddle.net/31ug4kdw/ https://jsfiddle.net/31ug4kdw/
  - nomilk 3y ago
    I've somehow never come across <math> before. TIL! Thanks for sharing
deleted 3y ago
[deleted]
RcouF1uZ4gsC 3y ago
> The maximum number of queries required by the protocol is n^n^n^n^n^n With 2 people taking 1 second per query you end up with 2^2^2^2^2^2 which is 2^(2^65536) seconds. I guess if not only the cake has decomposed and the people involved have died, but the universe itself has lost all thermodynamic free energy, I guess technically we are in an envy free state.
- comnetxr 3y ago
  n^n^n^n^n^n is an upper bound for general n, but the special case of only 2 people can be done with just 1 query. the algorithm is just to have person A cut into two equal slices and then person B choose their favorite slice. it takes just 1 second, which is quite a speedup over the upper bound...
- charcircuit 3y ago
  And this is only for a 1D cake. In the real world cakes are 3D. I wonder how much worse it would be.
  - LodeOfCode 3y ago
    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
    - charcircuit 3y ago
      >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.
saagarjha 3y ago
Suddenly my exponential time algorithms don’t seem so bad anymore.

24 points by luu 3y ago

> The maximum number of queries required by the protocol is n^n^n^n^n^n I'm impressed that rendered correctly, never seen that before. Got a minimal version working: code: https://pastebin.com/CqCzH8H7 https://pastebin.com/CqCzH8H7 what it looks like: https://imgur.com/a/v2PU1mH https://imgur.com/a/v2PU1mH

matt-tingen 3y ago
Or with MathML: https://jsfiddle.net/31ug4kdw/ https://jsfiddle.net/31ug4kdw/
- nomilk 3y ago
  I've somehow never come across <math> before. TIL! Thanks for sharing

deleted 3y ago

[deleted]

RcouF1uZ4gsC 3y ago

> The maximum number of queries required by the protocol is n^n^n^n^n^n With 2 people taking 1 second per query you end up with 2^2^2^2^2^2 which is 2^(2^65536) seconds. I guess if not only the cake has decomposed and the people involved have died, but the universe itself has lost all thermodynamic free energy, I guess technically we are in an envy free state.

comnetxr 3y ago
n^n^n^n^n^n is an upper bound for general n, but the special case of only 2 people can be done with just 1 query. the algorithm is just to have person A cut into two equal slices and then person B choose their favorite slice. it takes just 1 second, which is quite a speedup over the upper bound...
charcircuit 3y ago
And this is only for a 1D cake. In the real world cakes are 3D. I wonder how much worse it would be.
- LodeOfCode 3y ago
  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
  - charcircuit 3y ago
    >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.

saagarjha 3y ago

Suddenly my exponential time algorithms don’t seem so bad anymore.