15-451 Algorithms 12/01/05 * Cake-cutting - 2 people - Fair cake cutting - Envy-Free cake cutting. ===================================================================== Today we'll be talking about the concept of fair division, which has many important applications in economics and the social sciences. The metaphor we'll be using is how to fairly divide a cake - while the ideas that we talk about will have many applications, they aren't so practical for actually cutting cake... 2 people ======== Start with a very simple problem - Alice and Bob want to find a way to divide a cake such that each gets at least half of the cake. The cake isn't necessarily uniform: it may have chocolate, vanilla, frosting, and fruit (by the way, Alice hates fruit). Formally, - each person has a personal value system for assigning a real positive value to each piece of cake. - value is a measure: fix a person; if a cake is divided into a finite number of pieces, then for that person, each piece has positive value, and the sum of the values of all the pieces of cake equals 1 (each person's value system gives value 1 to the entire cake.) - Each person has a steady hand and can cut a cake exactly as he chooses to cut it. Mathematically: take a piece of cake with value v. For any real number x, 0 < x < 1, a person can divide it into 2 pieces having values xv and (1-x)v respectively. Note that its possible for both people to end up with more than half of the entire cake [how?]. However, we only care about each person ending up with at least 1/2 of the cake (according to their own value system.) Simple idea (if both people are honest): have Bob cut the cake in half and give Alice a slice. Does this work? [no] Refinement: have Bob cut the cake in half and let Alice choose a slice. Note that its in Bob's best interest to tell the truth - if he lies, he can only hurt himself. Fair cake cutting ================= DEFINITION: A PROTOCOL is a set of instructions for n participants. A protocol is like an algorithm EXCEPT that the participants may choose be dishonest (not follow the protocol). Certain guarantees are made to those who follow the protocol. No guarantees are made to those who don't. Some more definitions to get out of the way: DEFINITION: A CAKE CUTTING PROTOCOL is a protocol for n participants to divide a cake among themselves. DEFINITION: A cake cutting protocol is FAIR if each participant who follows protocol is guaranteed to receive at least 1/n of the cake according to his own personal value system. The next logical step, of course, is to create protocols for more than 2 people. A rather elegant way is to use a reverse auction. Reverse auction method ---------------------- Start with everyone having their hand raised. Sweep a knife across the cake from right to left. Instruct players to lower their hand when the amount of cake to the LEFT of the knife is no longer at least 1/n of the cake. Once only one person has their hand up, cut the cake there and give them the left piece. Repeat. [is this fair? look at the first n-1 people, then look at the last person.] -- Why is this a reverse auction? In a regular auction, the value of the item is fixed and the price continually increases. Here, the price is fixed, but the value continually decreases. Note that we're cheating a bit here - at every instant of time, players have to make a decision whether the amount of cake to the left is >= 1/n or not. We term this a continuous protocol (an infinite number of evaluations are made). In contrast to this, we have discrete protocols, where only a finite number of cuts/decisions are made. Discrete reverse auction method ------------------------------- 1. Have first person cut piece P of size 1/n. 2. Anyone who has not yet raised their hand can raise their hand, take P for themselves, and trim off any amount they think is excessive. 3. Repeat step 2 until nobody has their hand up. 4. Remove the person who got the cake. -- [do example with 3 people] So for three people, this only requires 3 cuts. As an aside, it turns out that with one other assumption/factoid, you can prove that with a discrete protocol, you can't fairly divide a cake among 3 people using only 2 cuts. Envy-free cake cutting ====================== So this is pretty good. Unfortunately, one can argue that our definition of fair is insufficient. Going back to the three-person situation: even if I got 1/3rd of the cake, I'm not going to be happy if someone else got a bigger slice than me. DEFINITION: A cake cutting protocol is ENVY-FREE if each participant who follows protocol is guaranteed to receive at least as much cake by his measure as any other participant. Notice that ENVY-FREE -> FAIR (why?) but not the other way around (why not?). Also note that this is a very strong restriction - REGARDLESS of what other people do, its still guaranteed that nobody will have a bigger slice than me. Is the two person algorithm above envy-free? What about the reverse auction method? Creating an envy-free protocol for an arbitrary number of people is not easy. Thus, we limit our attention to n=3 (Alice, Bob, and Dilbert). 3-person envy-free division --------------------------- We're going to do this in two stages. First, let's create an envy-free division in which we have some extra "trimmings". Once we have that, we can then figure out a way to divide the trimmings so that this remains envy-free. First stage - Divide cake with trimmings Start by having Alice divide the cake in thirds (by her measure). Then have Bob trim the largest piece so that its equal in size to the second largest. This will be the extra "trimmings" that we divide up in the next stage. Now we're pretty golden. Just have Dilbert pick a slice, then Bob, and finally Alice. The one caveat we add is that Bob needs to pick the trimmed slice if possible (since Alice might not be happy with it). Dilbert: He picked first, so it has to be envy-free to him. Bob: He'd be happy with either of two slices, so he's envy-free. Alice: Since she can't receive the trimmed slice, she has to be happy. Second stage - Deal with trimmings So a more cynical person might think that we're just back at our original problem. However, we have one key new property that we can exploit - Alice will remain envy-free irregardless of the amount of cake that we give to the person who received the trimmed slice (she originally cut the cake into equal thirds). Thus, we can just use a simple cut and choose algorithm. Either Dilbert or Bob received the trimmed slice. WLOG, assume its Dilbert (if its Bob, just swap Bob and Dilbert in the following protocol). Have Bob cut the cake into thirds, and have slices chosen in the order: Dilbert, Alice, Bob. Dilbert: He picks first, so he remains envy-free. Alice: She doesn't care how much cake Dilbert gets, and she picks before Bob. Bob: He cut it into thirds, so he's happy. -- As a side note, there are many other types of fair division protocols (strong fair, super envy-free, exact division). We can also think about the inverse of these problems (say if you wanted to divide chores up such that any person got at most 1/n of the work).