Learning Module 7 - Concepts
We're going to look at some problems and solutions regarding fairly dividing some goodies among a group of people. How do we divide an estate left to a group so that all are satisfied? How do you divide a multi-flavoured dessert among hungry and watchful kids? Some good algorithms - procedures - are known, but the one to select depends on what kind of goodies, and what kind of rules, the situation offers us.
First, the idea of fair. Say we're cutting up a cake, but it so happens that all I want is icing. (Please, don't judge me). A huge share of the cake might not tempt me at all, if it didn't have much icing (say, the bottom half of a cake iced on top!). On the other hand, you might look at this share and think it was way too much for my fair share.
The principal is, each person should get to determine what his or her valuation of the goodies is. Then that person's fair share, if we're dividing something evenly among a group of N people, is something the person would value at (at least) 1/N share of the total. It doesn't matter if you think my share is small or large; as long as I think I got my fair share, and you think you got your fair share, we're OK.
Then there's the question of whether the goods we're dividing can be cut up, or not. If the item(s) can be divided at will (like that cake), we say they're continuous goods; otherwise (like the Mona Lisa), let's call them discrete goods.
Let's look at a few situations, and see a few algorithms.
Anybody with a sibling knows about this one (and I have FOUR siblings...!). To divide the goodies between two people, pick (maybe by a coin toss) one of them, steady of hand, to split the goodies into two pieces. Then the other (the chooser), picks one of the two pieces. Let's convince ourselves this is fair, using our idea above. The cutter is wise to split the goods into two pieces he considers to be exact halves; so whichever piece he gets, he feels he has his fair share. The chooser will pick whichever piece looks better to her (or either piece if they look equal to her), so the worst she can do is 50%, her fair share. If the cutter and chooser disagree on what the value of the goodies are, the chooser might feel she's done better, even much better, than 50%.
Trying to generalise I cut/you choose to three people leads to at least one unfair scheme. Say, out of three people, Hamlet cuts the cake into three equal (according to him) pieces. Then Rosencrantz and Guildenstern take a piece each, in that order, leaving Hamlet with the last. Who might not be clutching 1/3 of the cake (according to his own valuation)?
It's easy to see how this works. With two people and an item or items to divide, what's wrong with tossing a coin, winner take all? Well, nothing, if everyone agrees - but this doesn't meet our definition of a fair division. The coin toss loser will always think he got nothing - less than his fair share. Again, the rules are that at the end everyone will feel she got her fair share of the goods.
One cake, three sharers, all with unique viewpoints on the cake. Let A cut the cake into two pieces, and B chooses one. Then each of these is looking at (at least) half the cake. A and B then cut "their" piece into three "equal" (to them) pieces; C chooses one of A's and one of B's. Time for an example: A. B and C are splitting a cake that is 50-50 chocolate and vanilla, as pictured:
Let's imagine the cake is worth $12. A dislikes chocolate: when eating his cake he'll cut off any chocolate he got and feed it to a dog (he doesn't like dogs, either, I guess). So A thinks the vanilla part is worth $12 and the chocolate part, $0. A will only be happy if he gets at least $4 worth of cake - which to him, means at least a third of the vanilla. The cake is 30 inches long, and 10 inches high; there's a total area of 300 sq. in, of which 150 are chocolate, 150 vanilla. A will cut the cake so that each half has 75 sq inches of vanilla. To do this, he could cut horizontally 2 1/2 inches down from the top - cutting the vanilla piece in half, and putting all the chocolate in one place. Picture:
B's turn. B likes chocolate and vanilla equally; she thinks the $12 cake has $6 worth of vanilla cake and $6 worth of chocolate cake. So A's pieces don't look equal to her! The big piece is $9 worth of cake, the small one is only $3 worth of cake, so B chooses the mixed choc/vanilla piece.
Each of A and B cut the cake into 3 equal area 10" wide portions for C to choose among. C's choices don't much matter: he'll get a geometric third of each of A's and B's cake - 25 square inches of vanilla from A, 25 square inches of vanilla and 50 square inches of chocolate from B.
Who got a fair share?
A got 50 sq inches of vanilla cake: since A thinks the 150 sq in of vanilla is worth the whole $12, he'll value his piece at $4, his exact fair share.
B got 50 sq inches of vanilla cake and 100 sq inches of chocolate cake: 1/3 of the total vanilla (worth $2 since the total vanilla's worth $6 to her) and2/3 of the total chocolate (worth $4 since the total chocolate portion's worth $6 to her) for a $6 value - HALF THE CAKE's value, well over her fair share.
C got - 1/3 of the vanilla (because he got 1/3 of 1/2 the vanilla from A's piece, and 1/3 of 1/2 the vanilla from B's piece, total 1/3) and 1/3 of the chocolate. Notice IT DOESN'T MATTER what C thinks of chocolate or vanilla. No matter what, this is a fair share.
This was just an example but it can be seen that each player, if they cut carefully and/or choose wisely, is guaranteed at least a fair share, according to whatever their own valuation of the goods to be divided is.