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