New Algorithm Solves Cake-Cutting Problem (2016)
quantamagazine.org
quantamagazine.org
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.
An important difference is that your rule only ensures that each person feels that they received at least 1/n of the total. This article is about the "envy-free" criterion, which is stronger: each person feels that nobody received more than they did. That's what makes the algorithm in the article so much more complicated.
(In particular, with the envy-free criterion it's very difficult to reduce the problem with a step like "That person is now out; they have their fair share", because the remaining people might subsequently divide the remaining cake in some bizarre way which makes one of the other divisions look enviable. Towards the end of the article it touches on how the new algorithm solves this: search for "domination relationships".)
I think after the first round, you need to remove all of P1's cards, and all of the 'second cards' from the remaining players too?
After that point, whichever remaining person has the leftmost third card gets everything between their second and third cards.
After that point, whichever remaining person has the leftmost fourth card gets everything between their third and fourth cards.
And so forth.
I'm having a hard time explaining it concisely, but it should be pretty intuitive once you figure out what I'm babbling about.
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.
That had two dimensions and a naive extension will clearly fail.
Is your notion similar to optimal matchmaking, score voting, other...?
If you ever illustrate this, please post a Show HN.
--
FWIW:
I use various voting systems to expedite team decision making problems. So I'm always curious about new algorithms, strategies.
For examples, use approval voting for triage (prioritization), use roman evaluation for go/no-go (releases).
Less talk (debate), more vote.
Everyone is going to get the segment of candy between two of their cards. If you try an example out, I'm confident you can figure out how to do this.
Alternatively, here's a better description I put in a followup comment:
-------------
Whoever has the leftmost second card gets everything between their first and second cards.
After that point, whichever remaining person has the leftmost third card gets everything between their second and third cards.
After that point, whichever remaining person has the leftmost fourth card gets everything between their third and fourth cards.
And so forth.
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.
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.
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.
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.
“I-Cut-You-Choose” Cake-Cutting Protocol Inspires Solution to Gerrymandering
https://www.cmu.edu/news/stories/archives/2017/november/i-cu...
The real problem was to find an algorithm that runs in a finite number of discrete steps.
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.
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?
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?
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.)
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.
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.
One devides and gets the worst based on the others opinions, then leaves with his piece. repeat.
https://www.newscientist.com/article/dn28743-mathematicians-...