7 ms·

New Algorithm Solves Cake-Cutting Problem (2016)

deleted 8y ago
[deleted]
tuco86 8y ago
1. Alice, Bob and Charlie want to share a Cake so that none of them envies other pieces 2. Charlie cuts the cake into three pieces that are equally valuable from his perspective 3. Alice identifies her first choice. 4. Bob identifies his first choice from the remaining two. Charlie gets the remaining one. 5. Bob trims either his or Alices piece. 6. Alice identifies her first choice. Simpler. Is there a fault i don't see?
- QML 8y ago
  Now generalize to the case where the number of people = n.
  - tuco86 8y ago
    I'm no mathematician. I just figured this whould work with 4 or 5 people by always removing one and extrapolated that it works for n. One devides and gets the worst based on the others opinions, then leaves with his piece. repeat.
- sp332 8y ago
  The problem is if after step 5, Charlie thinks one of the new pieces is really good, and "envies" it.
  - sk5t 8y ago
    It's not a problem because Charlie starts by creating three slices of equal-to-Charlie value, and is guaranteed to receive one of those unmolested. If the other two participants value the pieces in some strange way, Charlie has no right to interfere.
    - deleted 8y ago
      [deleted]
  - deleted 8y ago
    [deleted]
  - kgwgk 8y ago
    [edit: not good, see next paragraph] Charlie did cut the pie in the first place, and he thought all the three pieces were equally good so he has to accept that he got a fair share. It's irrelevant that he finds that Alice and Bob didn't share fairly the rest of the cake. Edit: come on, are we really expected to read TFA or even to read carefully the first comment in the thread where it was clearly written “so that none of them envies other pieces” before commenting? (Seriously: I was obviously wrong. As punishment I leave my original comment here and now I’ll read the article five times.)
    - sp332 8y ago
      An allocation is envy-free if no agent would prefer to take another agent's allocation instead of his own. The problem they solved is much more difficult than the one you are describing.
    - orthoxerox 8y ago
      It's very relevant. Suppose the cake has 3 butter roses, and Charlie LOVES them. He cuts the cake into 3 pieces each with a rose on it, to get one in any case. Alice picks one piece, Bob picks another, Charlie gets the third. Now Bob thinks his piece is a bit too small compared to Alice's and transfers Alice's butter rose onto his piece. Alice either swaps or doesn't. Charlie now sees that either Alice or Bob has a cake piece with TWO butter roses and is VERY envious.
      - tuco86 8y ago
        He sees alice or bob with two butter roses on top of a smaller piece. Charlie has the first cut, so he can cut horizontally and make a tiny piece with 3 butter roses on top. he either gets his three butter roses or a bigger piece of cake, their relative value is still the same for him.
- klipt 8y ago
  > Is there a fault i don't see? What if Alice thinks that the piece Bob gave to Charlie was the 2nd best piece, and after Bob's trimming, the remaining pieces are both worse than what Charlie has?
- deleted 8y ago
  [deleted]
- CamperBob2 8y ago
  Why do you need to go past step 5? Knowing that he will go last, Charlie has an incentive to cut the cake as evenly as possible. If he isn't happy with the result, he has no one but himself to blame. He can optimize his own share only by giving everyone the same amount.
- deleted 8y ago
  [deleted]
pierrebai 8y ago
I have to admit that I find this result unsatisfying. I don't see why mathematicians consider that trimming the remaining pieces cannot trigger envy from earlier cake splitters. (They call it dominating in the paper.) Once the remaining slice are modified, it's unclear to me why the original cutter would not envy the new slices. For the three persons scenario and using integers, the first cutter divides the number 3 into 1/1/1. If one of the other participants change the ratio of two slices to 0.5/1.5, it's clear that the original cutter would not be happy to get only 1 in the new 1/0.5/1.5 cuts. The original decision was contingent on the original split. In fact, given this, it seems that being the last to act is the best position as other are locked into the previous choices. I other words, being last allow you to profit from any possible mistakes previous cutters made. This is especially egregious if each have a different way to value things, since once A has chosen, B could modify the remaining pieces so that A preference is now different.
- jjnoakes 8y ago
  > It's unclear to me why the original cutter would not envy the new slices The original cutter gets second choice of the "trimmed" section's 3-way split, so your 1/1/1 doesn't go to 1/0.5/1.5, it goes to 1.2/1.2/0.6 or something, but (crucially) the original 1.0 guy gets to pick 0.2 more before the 0.5 guy gets to pick the remaining 0.1.
- jm_l 8y ago
  No participant is incentivized to alter the cake if they agree that it's value is already equally split in 3. The person making the trim is also not incentivized to make it 1.5/0.5, because they don't get first choice of those slices. When dividing cake, if one slice is bigger it may be because there is less frosting on it when frosting is desirable, or it might be because the slicer thought they could trick the others. Then when someone contests this division it's either because their preferences don't match, or they are correctly calling out the trick. In short, the algorithm is meant to deal with differing preferences and incentivized lying.
- kgwgk 8y ago
  > If one of the other participants change the ratio of two slices to 0.5/1.5 This is not what happens. From the point of view of the first cutter, he got a piece he values at 1 and the others got pieces he values at 1-x and 1. Then they make the repartition of the remaining x. The person who got previously the piece that the first cutter valued at 1-x chooses first, but can’t get more than 1 (as valued by the first cutter) in total. And the first cutter chooses before the other person who got a piece he values at 1, so he cannot end worse off.
justinpombrio 8y ago
I remember learning about a neat way to allot fair divisions. To illustrate it, suppose you have a line of various candy bars, and 4 people to divide them among. Everyone gets 5 notecards with their name on them. Each person places their notecards at places in the line that they think splits the line into 4 (approximately) equally valuable segments. (One notecard will be at the very beginning of the line; one will be at the very end; the other three are in the middle where the person thinks is fair.) The neat trick is that you can now pick one segment for each person, such that the segments don't overlap. Give each person the candy from that segment, and everyone receives their fair share. And there's (probably) some candy leftover. Here's how you do that: start scanning the line of candy from left to right. When you get to the second notecard of a given person, give that person all the candy between their first and second notecards. That person is now out: they have their fair share. Remove their remaining notecards. Now continue scanning from their second notecard. You can prove that by the end, everyone will have received one of their segments. (If two people's notecards are in the same place, pick one at random.) In contrast to this cake division algorithm, it leaves awkward leftovers. It's also gamable - if you know other people's preferences you might want to lie about your own.
- anilakar 8y ago
  Is it extendable to multidimensional preferences or does it require that whatever is being shared is quantizable with a single variable?
  - justinpombrio 8y ago
    It requires is that everyone be able to split the line into segments, such that they think it would be fair for them to receive any of their segments, i.e., such that they would rate all segments as equally valuable. This allows people to have different preferences than each other. But I'm not sure what a multidimensional preference is. If your utility for a set of candy is, say, a pair of real numbers (which I presume is the sort of thing you mean by "multidimensional"?), what does it mean for two sets of candy to have equal value? Would both of the real numbers have to be equal? If so, this method isn't going to work: in general you wouldn't be able to split the line into segments of equal value.
SamBam 8y ago
Two observations I find interesting: 1. Order matters. In the the-slice solution, it is much better to be Charlie. This is because there is a chance you will get more than your expected share if value of the cake, because you start out with a guaranteed 1/3 value (from your perspective) plus a chance of extra if Bob trims. This seems to break the "no envy" clause in a very human way: it is true that no player is envious of the other person's choice (that is, no one wants to swap), but Alice and Bob may be envious of Charlie's increased happiness, feeling it unfair. (It sounds like this may have changed in the new algorithm, with the sending away of dominant players. But I believe it then may be better to be A or B.) 2. Along similar lines, none of the algorithms concern themselves with maximizing total happiness. Point 2 can be seen even in the two-player version: Say a cake is half chocolate and half vanilla. Suppose A adores vanilla and assigns zero value to chocolate, while B can't even tell the difference between them. If A cuts first, she will need to divide it in half across the two flavors to make two "equal" slices of chocolate-and-vanilla ("equal" in her eyes). B choose at random and gets half a cake's worth of happiness, while A gets a quarter of a cake's worth, leading to an inefficiency of a quarter cake. If B cut first (presumably in half at random, since he doesn't distinguish between the flavors), there is a good chance A's happiness will increase, although there's very little chance it will come out perfect.
analog31 8y ago
I wonder if similar math could lead to a way of setting up voting districts, as a fair alternative to gerrymandering. Of course you wouldn't want to cut people into pieces, so it would have to be an approximation of some sort.
- DerekL 8y ago
  Already done: “I-Cut-You-Choose” Cake-Cutting Protocol Inspires Solution to Gerrymandering https://www.cmu.edu/news/stories/archives/2017/november/i-cut-you-choose-cake-cutting-protocol-inspires-solution-to-gerrymandering.html https://www.cmu.edu/news/stories/archives/2017/november/i-cu... https://news.ycombinator.com/item?id=17459008 https://news.ycombinator.com/item?id=17459008
tianshuo 8y ago
The new algorithm is so awkward. There is an easier way to divide the cake for n people (n>=2). For a rectangular cake move the knife with a slow uniform velocity, for a circular cake, cut to the center, and start rotating the cake with a slow uniform rotational velocity. The first person to yell stop will get the part of the cake that is split by the knife's current position. The process continues until there is only one person who doesn't get a cake. Although not every piece is guaranteed average, the game is fair.
- nightcracker 8y ago
  This algorithm is not new - it is well known in fact. The issue with it is that it's continuous-time. For example, you can't run your algorithm on a Turing machine. The real problem was to find an algorithm that runs in a finite number of discrete steps.
  - waqf 8y ago
    Also, it's not envy-free. Say n=3: A might accept (in their opinion) 1/3 of the cake, but then watch as B and C divide the cake (in A's opinion) unevenly, so that (in A's opinion) either B or C has taken more than 1/3 and A is envious.
peterwwillis 8y ago
Has this been in an episode of Silicon Valley yet?
social_quotient 8y ago
Reminds me of the monohedral pizza cutting https://www.newscientist.com/article/dn28743-mathematicians-invent-new-way-to-slice-pizza-into-exotic-shapes/ https://www.newscientist.com/article/dn28743-mathematicians-...
mckirk 8y ago
See, I'd read it as "algorithm solves coke-cutting problem" and gotten excited :(

deleted 8y ago

[deleted]

1. Alice, Bob and Charlie want to share a Cake so that none of them envies other pieces 2. Charlie cuts the cake into three pieces that are equally valuable from his perspective 3. Alice identifies her first choice. 4. Bob identifies his first choice from the remaining two. Charlie gets the remaining one. 5. Bob trims either his or Alices piece. 6. Alice identifies her first choice. Simpler. Is there a fault i don't see?

QML 8y ago
Now generalize to the case where the number of people = n.
- tuco86 8y ago
  I'm no mathematician. I just figured this whould work with 4 or 5 people by always removing one and extrapolated that it works for n. One devides and gets the worst based on the others opinions, then leaves with his piece. repeat.
sp332 8y ago
The problem is if after step 5, Charlie thinks one of the new pieces is really good, and "envies" it.
- sk5t 8y ago
  It's not a problem because Charlie starts by creating three slices of equal-to-Charlie value, and is guaranteed to receive one of those unmolested. If the other two participants value the pieces in some strange way, Charlie has no right to interfere.
  - deleted 8y ago
    [deleted]
- deleted 8y ago
  [deleted]
- kgwgk 8y ago
  [edit: not good, see next paragraph] Charlie did cut the pie in the first place, and he thought all the three pieces were equally good so he has to accept that he got a fair share. It's irrelevant that he finds that Alice and Bob didn't share fairly the rest of the cake. Edit: come on, are we really expected to read TFA or even to read carefully the first comment in the thread where it was clearly written “so that none of them envies other pieces” before commenting? (Seriously: I was obviously wrong. As punishment I leave my original comment here and now I’ll read the article five times.)
  - sp332 8y ago
    An allocation is envy-free if no agent would prefer to take another agent's allocation instead of his own. The problem they solved is much more difficult than the one you are describing.
  - orthoxerox 8y ago
    It's very relevant. Suppose the cake has 3 butter roses, and Charlie LOVES them. He cuts the cake into 3 pieces each with a rose on it, to get one in any case. Alice picks one piece, Bob picks another, Charlie gets the third. Now Bob thinks his piece is a bit too small compared to Alice's and transfers Alice's butter rose onto his piece. Alice either swaps or doesn't. Charlie now sees that either Alice or Bob has a cake piece with TWO butter roses and is VERY envious.
    - tuco86 8y ago
      He sees alice or bob with two butter roses on top of a smaller piece. Charlie has the first cut, so he can cut horizontally and make a tiny piece with 3 butter roses on top. he either gets his three butter roses or a bigger piece of cake, their relative value is still the same for him.
klipt 8y ago
> Is there a fault i don't see? What if Alice thinks that the piece Bob gave to Charlie was the 2nd best piece, and after Bob's trimming, the remaining pieces are both worse than what Charlie has?
deleted 8y ago
[deleted]
CamperBob2 8y ago
Why do you need to go past step 5? Knowing that he will go last, Charlie has an incentive to cut the cake as evenly as possible. If he isn't happy with the result, he has no one but himself to blame. He can optimize his own share only by giving everyone the same amount.
deleted 8y ago
[deleted]

pierrebai 8y ago

I have to admit that I find this result unsatisfying. I don't see why mathematicians consider that trimming the remaining pieces cannot trigger envy from earlier cake splitters. (They call it dominating in the paper.) Once the remaining slice are modified, it's unclear to me why the original cutter would not envy the new slices. For the three persons scenario and using integers, the first cutter divides the number 3 into 1/1/1. If one of the other participants change the ratio of two slices to 0.5/1.5, it's clear that the original cutter would not be happy to get only 1 in the new 1/0.5/1.5 cuts. The original decision was contingent on the original split. In fact, given this, it seems that being the last to act is the best position as other are locked into the previous choices. I other words, being last allow you to profit from any possible mistakes previous cutters made. This is especially egregious if each have a different way to value things, since once A has chosen, B could modify the remaining pieces so that A preference is now different.

jjnoakes 8y ago
> It's unclear to me why the original cutter would not envy the new slices The original cutter gets second choice of the "trimmed" section's 3-way split, so your 1/1/1 doesn't go to 1/0.5/1.5, it goes to 1.2/1.2/0.6 or something, but (crucially) the original 1.0 guy gets to pick 0.2 more before the 0.5 guy gets to pick the remaining 0.1.
jm_l 8y ago
No participant is incentivized to alter the cake if they agree that it's value is already equally split in 3. The person making the trim is also not incentivized to make it 1.5/0.5, because they don't get first choice of those slices. When dividing cake, if one slice is bigger it may be because there is less frosting on it when frosting is desirable, or it might be because the slicer thought they could trick the others. Then when someone contests this division it's either because their preferences don't match, or they are correctly calling out the trick. In short, the algorithm is meant to deal with differing preferences and incentivized lying.
kgwgk 8y ago
> If one of the other participants change the ratio of two slices to 0.5/1.5 This is not what happens. From the point of view of the first cutter, he got a piece he values at 1 and the others got pieces he values at 1-x and 1. Then they make the repartition of the remaining x. The person who got previously the piece that the first cutter valued at 1-x chooses first, but can’t get more than 1 (as valued by the first cutter) in total. And the first cutter chooses before the other person who got a piece he values at 1, so he cannot end worse off.

justinpombrio 8y ago

I remember learning about a neat way to allot fair divisions. To illustrate it, suppose you have a line of various candy bars, and 4 people to divide them among. Everyone gets 5 notecards with their name on them. Each person places their notecards at places in the line that they think splits the line into 4 (approximately) equally valuable segments. (One notecard will be at the very beginning of the line; one will be at the very end; the other three are in the middle where the person thinks is fair.) The neat trick is that you can now pick one segment for each person, such that the segments don't overlap. Give each person the candy from that segment, and everyone receives their fair share. And there's (probably) some candy leftover. Here's how you do that: start scanning the line of candy from left to right. When you get to the second notecard of a given person, give that person all the candy between their first and second notecards. That person is now out: they have their fair share. Remove their remaining notecards. Now continue scanning from their second notecard. You can prove that by the end, everyone will have received one of their segments. (If two people's notecards are in the same place, pick one at random.) In contrast to this cake division algorithm, it leaves awkward leftovers. It's also gamable - if you know other people's preferences you might want to lie about your own.

anilakar 8y ago
Is it extendable to multidimensional preferences or does it require that whatever is being shared is quantizable with a single variable?
- justinpombrio 8y ago
  It requires is that everyone be able to split the line into segments, such that they think it would be fair for them to receive any of their segments, i.e., such that they would rate all segments as equally valuable. This allows people to have different preferences than each other. But I'm not sure what a multidimensional preference is. If your utility for a set of candy is, say, a pair of real numbers (which I presume is the sort of thing you mean by "multidimensional"?), what does it mean for two sets of candy to have equal value? Would both of the real numbers have to be equal? If so, this method isn't going to work: in general you wouldn't be able to split the line into segments of equal value.

SamBam 8y ago

Two observations I find interesting: 1. Order matters. In the the-slice solution, it is much better to be Charlie. This is because there is a chance you will get more than your expected share if value of the cake, because you start out with a guaranteed 1/3 value (from your perspective) plus a chance of extra if Bob trims. This seems to break the "no envy" clause in a very human way: it is true that no player is envious of the other person's choice (that is, no one wants to swap), but Alice and Bob may be envious of Charlie's increased happiness, feeling it unfair. (It sounds like this may have changed in the new algorithm, with the sending away of dominant players. But I believe it then may be better to be A or B.) 2. Along similar lines, none of the algorithms concern themselves with maximizing total happiness. Point 2 can be seen even in the two-player version: Say a cake is half chocolate and half vanilla. Suppose A adores vanilla and assigns zero value to chocolate, while B can't even tell the difference between them. If A cuts first, she will need to divide it in half across the two flavors to make two "equal" slices of chocolate-and-vanilla ("equal" in her eyes). B choose at random and gets half a cake's worth of happiness, while A gets a quarter of a cake's worth, leading to an inefficiency of a quarter cake. If B cut first (presumably in half at random, since he doesn't distinguish between the flavors), there is a good chance A's happiness will increase, although there's very little chance it will come out perfect.

analog31 8y ago

I wonder if similar math could lead to a way of setting up voting districts, as a fair alternative to gerrymandering. Of course you wouldn't want to cut people into pieces, so it would have to be an approximation of some sort.

DerekL 8y ago
Already done: “I-Cut-You-Choose” Cake-Cutting Protocol Inspires Solution to Gerrymandering https://www.cmu.edu/news/stories/archives/2017/november/i-cut-you-choose-cake-cutting-protocol-inspires-solution-to-gerrymandering.html https://www.cmu.edu/news/stories/archives/2017/november/i-cu... https://news.ycombinator.com/item?id=17459008 https://news.ycombinator.com/item?id=17459008

tianshuo 8y ago

The new algorithm is so awkward. There is an easier way to divide the cake for n people (n>=2). For a rectangular cake move the knife with a slow uniform velocity, for a circular cake, cut to the center, and start rotating the cake with a slow uniform rotational velocity. The first person to yell stop will get the part of the cake that is split by the knife's current position. The process continues until there is only one person who doesn't get a cake. Although not every piece is guaranteed average, the game is fair.

nightcracker 8y ago
This algorithm is not new - it is well known in fact. The issue with it is that it's continuous-time. For example, you can't run your algorithm on a Turing machine. The real problem was to find an algorithm that runs in a finite number of discrete steps.
- waqf 8y ago
  Also, it's not envy-free. Say n=3: A might accept (in their opinion) 1/3 of the cake, but then watch as B and C divide the cake (in A's opinion) unevenly, so that (in A's opinion) either B or C has taken more than 1/3 and A is envious.

peterwwillis 8y ago

Has this been in an episode of Silicon Valley yet?

social_quotient 8y ago

Reminds me of the monohedral pizza cutting https://www.newscientist.com/article/dn28743-mathematicians-invent-new-way-to-slice-pizza-into-exotic-shapes/ https://www.newscientist.com/article/dn28743-mathematicians-...

mckirk 8y ago

See, I'd read it as "algorithm solves coke-cutting problem" and gotten excited :(