CS70, Fall 2003 Discussion #4 Amir KamilUC Berkeley 9/19/03Topics: Bad Proofs, Stable Marriage, Cake Cutting1 Bad ProofsConsider the following proof:Claim: Every natural number can be described in fifteen English words or less.Proof by well-ordering.Let P (n) = “n can be described in fifteen English words or less”.Let us assume that there are numbers n for which P (n) is not true. In this case, by the well-orderingprinciple, there must be a least such number, and let that number be k. But then k can be described bythe following sentence “It’s the smallest natural number that cannot be described in fifteen English wordsor less.” However, this is a description that requires fifteen words or less, and so we have a contradiction.Thus P (n) is true for all numbers n.What, if anything, is wrong with the above proof? The claim itself is easy to disprove. Let N be thenumber of words in the English language. Then there are about N15possible descriptions of 15 words orless. Thus if the claim were true, there would be at most N15natural numbers. We know this is not thecase, so the claim is false.The problem in the proof is that P (n) is actually not a well-defined proposition. In fact, being “describablein fifteen English words or les s” depends not only on the encoding of the numbers, but also on the contextin which this is spoken, and to define it, we need more arguments which pin down the encoding and context.Consider the following scenario. I write down the number 10 on a piece of paper, and describe it as “thenumber on the paper.” Simultaneously, someone in China writes down the number 11 on a piece of paper andalso describes it as “the number on the paper.” As you can see, the same description can refer to differentnumbers depending on the context in which the description is given. This is why P (n) in not well-defined.2 Stable MarriageConsider a stable matching M on n boys and n girls. Suppose that Alice and Bob are married in M . Nowsuppose that Alice and Bob move to Canada. Then we are left with a matching, say L, on n − 1 boys andn − 1 girls. Is L stable?In fact, L is stable. Suppose it is not. Then there exist some couples (b1, g1) and (b2, g2) where b1likesg2more than g1, and g2likes b1more than b2. But these same two couples exist in M , and with the samepreferences, so b1and g2would be a rouge couple in M as well. Since M is stable, this is a contradiction.Now consider two (not necessarily stable) matchings M and M0on the same set of people. Let MSM0be the configuration in which each girl is married to the better of her two partners in M and M0. Is MSM0always a matching? Recall that in a matching, each boy is married to exactly one girl, and each girl ismarried to exactly on boy.Unfortunately, MSM0is not guaranteed to be a matching. Suppose M contains the couples (b1, g1) and(b2, g2), and that M0contains the couples (b2, g1) and (b1, g2). Suppose that both g1and g2prefer b1overb2. Then in MSM0, we have the pairings (b1, g1) and (b1, g2). Since b1is married to two girls, MSM0isnot a matching.Finally, consider the situation where there are n + 1 boys and n girls. Does the traditional marriagealgorithm pro duce a stable pairing between n of the boys and the n girls?In order to see that TMA does indeed produce a stable pairing, consider a virtual girl gn+1. Let thisgirl have an arbitrary preference list, and for each boy, add this girl to the end of their preference lists. The1addition of this virtual girl simulates the running of TMA on the n + 1 boys and n girls. Now TMA producesa stable matching on this new configuration, so it does for the original. This same procedure can be usedfor any k boys and m girls, by introducing virtual people into the problem.3 Cake CuttingConsider the following cake cutting algorithm for n = 3:1. A cuts the cake into three equal pieces.2. B trims the largest piece so it is equal to the second largest piece, throwing away the trimmings.3. C chooses the largest piece.4. B chooses between the two remaining pieces.5. A takes the last piece.Is this algorithm fair? Obviously not, since C can assign the trimmings a value of 1, in which case heends up with none of the cake. How about in a weaker sense of fair, call it fair0, where each person gets atleast13of the remaining cake? It is not even fair0, if A values the trimmings and ends up with a trimmedpiece. (The trimmed piece would have value <13of the original, while the other two would be exactly13of the original, resulting in the trimmed piece being less than13of the remaining.) However, it is fair0forB and C. It is for C since C gets to pick first. It is for B since at least two of the pieces are equally thelargest, and since he gets to pick second, he will get one of those.Now the above algorithm can be made fair0for A if we can somehow guarantee that A gets an untrimmedpiece. This can be done by forcing B to take the trimmed piece if C does not pick it. Now it is still fair0for C by the same reasoning as above. It is fair0for A since she gets an untrimmed piece, worth13of theoriginal cake, so it must be at least13of the remaining cake. It is fair0for B, since the trimmed piece is oneof the two largest pieces. Thus the modified algorithm is fair0.In order to modify the algorithm to be fair, we need to decide what to do with the trimmings. Nowit is already fair for A, since she gets an untrimmed piece. So only B and C need to participate in thepartitioning of the trimmings. The obvious choice is to use cut-and-choose. So consider a new algorithm:1. A cuts the cake into three equal pieces.2. B trims the largest piece so it is equal to the second largest piece.3. C chooses the largest piece.4. B takes the trimmed piece if it is still available, or chooses between the two remaining pieces if not.5. A takes the last piece.6. B and C cut-and-choose the trimmings.Is this new algorithm fair? As we said before, it is fair for A. Now consider B. Suppose he assigns a valueof x1to the largest piece A cuts, x2to the second largest, and x3to the smallest, where x1+ x2+ x3= 1.It is easy to see that x1≥13, and x3≤13. Then the trimmings have value x1− x2. So B gets at leas tx2+x1−x22=x1+x22=1−x32≥1−1/32=13of the cake. Thus it is fair for B. It is also fair for C, but I leavethe proof as an exercise .Is the algorithm envy-free? Recall that envy-free means that each person does the best according to hisown meas ure. Unfortunately, it is not envy-free for A, since one of B and C
View Full Document