justinpombrio 5 years 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.

  • waqf 5 years ago

    > In contrast to this cake division algorithm, it leaves awkward leftovers.

    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".)

  • jamesrom 5 years ago

    So the first person (P1) gets everything up to their second card. Are you saying that the second person (P2) gets everything from P1's second card up until P2's second card? How is that not a small unfair amount of candy?

    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?

    • justinpombrio 5 years ago

      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.

      I'm having a hard time explaining it concisely, but it should be pretty intuitive once you figure out what I'm babbling about.

  • anilakar 5 years ago

    Is it extendable to multidimensional preferences or does it require that whatever is being shared is quantizable with a single variable?

    • justinpombrio 5 years 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.

      • zwkrt 5 years ago

        A classic 'multidimensional' preference is a set of roommates all of whom have to decide both what space they want to take in an apartment and how much they want to pay for that space.

        https://www.youtube.com/watch?v=7s-YM-kcKME

      • Misdicorl 5 years ago

        Consider splitting a tract of land into four fair farms.

        That had two dimensions and a naive extension will clearly fail.

  • specialist 5 years ago

    Not comprehending. Sorry. I've always been a simple bear who struggles with word problems.

    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.

    • justinpombrio 5 years ago

      Sorry, it's not that hard, I'm just not explaining it well.

      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.

  • superlopuh 5 years ago

    Are you indexing from 1 or 0?

pierrebai 5 years 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.

  • kgwgk 5 years 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.

    • norswap 5 years ago

      Thanks I was hung up on why "it's fair for Charlie because he got to choose before Bob" part, but this explains it nicely.

  • jjnoakes 5 years 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 5 years 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.

tianshuo 5 years 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 5 years 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 5 years 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.

SamBam 5 years 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.

tuco86 5 years 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?

  • klipt 5 years 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?

  • sp332 5 years ago

    The problem is if after step 5, Charlie thinks one of the new pieces is really good, and "envies" it.

    • kgwgk 5 years 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.)

      • orthoxerox 5 years 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 5 years 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.

      • sp332 5 years 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.

    • sk5t 5 years 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.

  • CamperBob2 5 years 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.

  • QML 5 years ago

    Now generalize to the case where the number of people = n.

    • tuco86 5 years 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.

peterwwillis 5 years ago

Has this been in an episode of Silicon Valley yet?

mckirk 5 years ago

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