CS 15-451 Analysis of Algorithms 2 December 2004 Manuel & Avrim Blum Today: Fair Cake Cutting Envy-Free 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 to not follow the protocol. Certain guarantees are made to those who follow the protocol. No guarantees are made to those who don't. DEFINITION: A CAKE CUTTING PROTOCOL is a protocol for n participants to divide a cake among themselves. ASSUMPTIONS: * each person has a personal value system for assigning a real positive value to each piece of cake. * each person's value system gives value 1 to the entire 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. * for any real number x, 0 < x < 1, a person can divide any piece of cake having value v, say, into 2 pieces having values xv and (1-x)v respectively. Each person has a steady hand and can cut a cake exactly as he chooses to cut it. * cake is not necessarily uniform: it may have chocolate, vanilla, frosting, and fruit. Some parts of the cake (eg chocolate) may be more valuable to one person than another. * each person follows protocol except possibly in the matter of declaring honestly the size or value they assign each piece. For example, if the protocol calls for Alice to cut the cake into 3 equal pieces, she will indeed divide it into 3 pieces, not 2 or 4. However, the pieces may not have equal value to her (in which case she is not following protocol). 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. 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. For example, the standard 2-persone protocol is envy-free: Alice: cut cake into two equal pieces Bob: choose the piece of greater value If Alice follows protocol, she will divide the cake into two pieces of equal value to her. Suppose it turns out that the two pieces are worth 1/3 and 2/3 to Bob. If Bob follows protocol, he will get the piece worth 2/3 by his measure. If he does not follow protocol, he may or may not get the bigger piece (by his measure). Notice that ENVY-FREE => FAIR (why?) but not the other way around (why not?) . An Envy-free Cake Cutting protocol for n=3 by Selfridge and Conway STAGE 0. 0.1. Alice is to cut the cake into three equal pieces [by her measure]. 0.2. Bob is to trim the largest piece to create a 2-way tie for largest [by his measure], and set the trimmings aside. Note that no one has yet gotten a piece of cake. THIS ENDS STAGE 0. STAGE 1. Trimmings aside, there are now 3 "pieces," which together we call cake1, and the "trimmings," which we call cake2. Cake1 is distributed in reverse order (Charlie, Bob, Alice) as follows: 1.1 Charlie picks [what he considers to be] the largest piece. 1.2. Bob takes the trimmed piece if Charlie has not taken it; otherwise Bob takes [what he considers to be] the largest of the two pieces. 1.3. Alice takes the last remaining (untrimmed!) piece of cake1. THIS ENDS STAGE 1. As you may have noticed, this protocol has one gal, Alice, and two guys, Bob and Charlie. This helps to clarify the next and final stage 2: Call the guy who took the trimmed piece T, and the other guy NT. STAGE 2. Cake2 (the trimmings) is distributed as follows: 2.1. NT divides cake2 into [what he thinks are] thirds. 2.2. T picks first, Alice picks second, NT gets the last of it. THIS ENDS STAGE 2. THIS ENDS THE PROTOCOL. THEOREM: The above protocol is envy-free. PROOF: By the end of stage 0, the protocol has generated 2 cakes: cake1 (in 3 pieces) and cake2 (trimmings). By the end of stage 1, as we shall see, cake1 has been distributed among the participants in an envy-free fashion. By the end of stage 2, as we shall see, cake2 has been divided into 3 pieces and distributed also in envy-free fashion. Thus the entire cake is distributed among the 3 participants in envy-free fashion*. ---------- * Here we use the fact that if participant Pi values his piece of cake1 at least as much as he values any other person's piece of cake1, and if he values his piece of cake2 at least as much as he values any other person's piece of cake2, then Pi values his final 2 pieces of cake at least as much as he values any other participant's two pieces of cake. ---------- It remains to prove that the protocol is envy-free to each of the participants, Alice, Bob, and Charlie. Proofs for the latter 2 are divided into 2 cases, depending on whether Bob or Charlie is T. In each case, we show that the protocol is envy-free immediately after stage 1, then extend this to show that it is envy-free at the end of stage 2. ENVY_FREE to ALICE: Alice divides the cake into 3 equal pieces. By the end of stage 1, she gets one of the untrimmed pieces. So at that point she will not envy either of the 2 guys, one of which got a trimmed piece, the other an untrimmed piece. In fact, A will not envy T, the guy who got the trimmed piece, even if that guy gets ALL the trimmings. Thus it is okay that T gets first pick at a so-called "third" of the trimmings. So Alice will not envy T. After that, she will get at least as much of the remaining trimming as NT. Thus Alice will not envy NT. ENVY-FREE to BOB: At the end of stage 1, Bob has one of the two largest pieces, so at that point he envies neither Alice nor Charlie. We now consider 2 cases: CASE BOB = T: At the end of stage 1, Bob has the trimmed piece, which by his measure is at least as large as each of the other two pieces of cake1. In stage 2, he is given first pick at one of three pieces of trimming, so he will not envy whoever gets second or third choice. CASE BOB = NT: At the end of stage 1, Bob does not envy Alice or Charlie. At the start of stage 2, Bob divides the trimmings into 3 equal parts, so he will not envy either of the other two even though he gets last pick on the trimmings. ENVY-FREE to CHARLIE: In stage 1, Charlie gets first choice of the 3 pieces. So at the end of stage 1, he does not envy either Alice or Bob. We now consider 2 cases: CASE CHARLIE = T: Charlie gets first choice on the 3 pieces of trimming, so he will not envy the other 2 after they get their (smaller) pieces of trimming. CASE CHARLIE = NT: Charlie decided that the untrimmed piece is the largest of the 3 pieces, and took that piece, so he does not envy the other two at the end of stage 1. As NT, he divides the trimmings into 3 equal pieces, so he will not envy the other two even though he gets last pick at the trimmings. THIS ENDS THE PROOF.