DOC PREVIEW
Berkeley COMPSCI 70 - CS 70 Discussion

This preview shows page 1 out of 3 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

Berkeley COMPSCI 70 - CS 70 Discussion

Documents in this Course
Notes 1

Notes 1

12 pages

Note 2

Note 2

6 pages

Notes

Notes

6 pages

Notes

Notes

7 pages

Note 10

Note 10

8 pages

n20

n20

10 pages

n19

n19

10 pages

n18

n18

10 pages

n17

n17

6 pages

n16

n16

9 pages

n15

n15

10 pages

n14

n14

9 pages

n13

n13

6 pages

n12

n12

7 pages

n11

n11

6 pages

n10

n10

8 pages

n9

n9

5 pages

n8

n8

7 pages

n7

n7

8 pages

n6

n6

5 pages

n5

n5

8 pages

n4

n4

7 pages

n3

n3

10 pages

n2

n2

7 pages

n1

n1

5 pages

Load more
Download CS 70 Discussion
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view CS 70 Discussion and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view CS 70 Discussion 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?