MGF 1107

SUPPLEMENTAL HOMEWORK/ CHAPTER 13

 

1. Use the lone-divider method to parcel a plot of land into 3 parcels s1, s2, and s3 if the chooser bids are:

a) C1: {s2, s3}     b) C1: {s1, s2, s3}         c) C1: {s1}    d) C1: {s1}

    C2: {s1, s3}          C2: {s1}                      C2: {s2}          C2: {s1}

2. Use the lone-divider method to divide a cake into 4 slices s1, s2, s3 and s4 if the choosers make the following bids.  Give two different divisions.

C1: {s2, s3}

C2: {s1, s3}

C3: {s1, s2}

3. Five players want to divide a cake fairly using the lone-divider method.  The divider cuts the cake into 5 slices s1, s2, s3, s4 and s5 and the choosers make the following bids:

C1: {s2, s4}

C2: {s2, s4}

C3: {s2, s3, s4}

C4: {s2, s3, s5}

Give two different fair divisions.

4. Six players want to divide a piece of land using the lone-divider method.  The divider partitions the land into six pieces s1, s2, s3, s4, s5 and s6.  The choosers make the following bids:

C1: {s2, s3, s5}

C2: {s1, s5, s6}

C3: {s3, s5, s6}

C4: {s2, s3}

C5: {s3}

Describe a fair division of the land.

5. Four partners want to divide a piece of land valued at $120,000 using the lone-divider method.  The divider D slices the land into 4 parcels s1, s2, s3 and s4.  The value of each parcel (in thousands of dollars) in each chooser’s eye is given in the following table.

 

s1

s2

s3

s4

C1

$10

$10

$30

$70

C2

$30

$10

$45

$35

C3

$15

$ 5

$80

$20

a) What should each chooser’s bids be?

b) Describe a possible fair-division of the land.

6. Six players want to divide a piece of land using the lone-divider method.  The divider partitions the land into six pieces s1, s2, s3, s4, s5 and s6.  The choosers make the following bids:

C1: {s1}

C2: {s2, s3}

C3: {s4, s5}

C4: {s4, s5}

C5: {s1}

Describe how to proceed to obtain a fair division of the land.

7. Here are the steps in the Selfridge-Conway envy-free procedure for 3 players.

Stage 1:  The initial division

Step 1: Player 1 cuts the cake into, what in his view, is 3 equal pieces.

Step 2: Player 2, if he thinks one piece is largest, trims from that piece to create what he believes is a 2-way tie for largest piece.  The trimmings are set aside.  If player 2 thinks that the original split was fair, he does nothing.

Step 3: Player 3 may choose any piece.

Step 4: Player 2 chooses a piece. If the trimmed piece remains, he must choose it.  If not, he chooses the one he feels is tied with the trimmed piece for largest.

Step 5: Player 1 gets the remaining piece.

Stage 2: Dividing the trimmings.  Assume player 3 received the trimmed piece in stage 1.

Step 6: Player 2 divides the trimmings into what he considers 3 equal parts. 

Step 7: Player 3 chooses one part of the trimmings.

Step 8: Player 1 chooses a piece of the trimmings.

Step 9: Player 2 receives the remaining trimmings.

a) Explain why player 1 is envy-free after stage 1.

b) Explain why player 2 is envy-free after stage 1.

c) Explain why player 3 is envy-free after stage 1.

d) Explain why player 1 is envy-free after stage 2.

e) Explain why player 2 is envy-free after stage 2.

f) Explain why player 3 is envy-free after stage 2.

8. The 1996 presidential debates between Bill Clinton and Bob Dole were preceded by negotiations between their advisers.  The issues were:

1. Inclusion/exclusion of Ross Perot.  President Clinton wanted Perot included, apparently feeling that Perot would hurt Dole more than himself.  Dole’s advisors believed Perot would hurt Dole’s poll standings.  Their feelings were so strong on this issue that they preferred no debates to debates with Perot.  This despite the fact that Dole, who trailed in the polls, stood more to gain from debates than the frontrunner. 

2. Number and timing. Clinton wanted two debates.  Dole, who needed more opportunities to whittle away at the President’s lead, wanted 3, with the final one closer to Election Day.

3. Length. The President, younger and a more accomplished debater than Dole, wanted each debate to last two hours, believing that his opponent would not hold up as well as he would.  Dole preferred 60 to 75 minutes; claiming that a third debate would make up for the lost time.

4. Format.  Clinton wanted the first debate to have only a moderator and the second to have the format of a town hall meeting.  He flourished in the latter format in the 1992 debates.  Dole was less comfortable with the town hall format, although his opposition was not strong due to his desire to prove himself a “regular guy.”

Brams and Taylor assign the following hypothetical point allocations.

 

Clinton

Dole

Perot

40

50

Number

20

16

Length

20

18

Format

20

16

Apply the adjusted winner procedure to the negotiations.

9. Can the moving knife method be used to partition a piece of land into 4 pieces?  If so, what would you need?

10. What is the major drawback to:

a) the adjusted winner procedure?

b) the Knaster inheritance procedure?
11.Suppose we have two items (X and Y) that must be divided by Javier and Mary. Assume that Javier and Mary each spread 100 points over the items (as in the Adjusted Winner Procedure) to indicate the relative worth of each item to that person:
Mary
Javier
X
50
40
Y
50
60

a) Is there an allocation (without dividing an item) that is equitable?
b) If Mary gets X and Y and Javier gets nothing, is this allocation Pareto-optimal?
If Mary gets Y and Javier gets X, is this allocation:
c) proportional?
d) envy-free?
e) equitable?
f) Pareto-optimal?
12. Suppose we have four items (W, X, Y, and Z) and four people (Ralph, Alice, Ed, and Trixie). Assume that each of the people spreads 100 points over the items (as in the Adjusted Winner Procedure) to indicate the relative worth of each item to that person:
Ralph
Alice
Ed
Trixie
W
21
28
76
24
X
24
23
0
25
Y
25
25
24
25
Z
30
24
0
26

Suppose Ralph gets Y, Alice gets W, Ed Gets X, and Trixie gets Z.
a) Is this allocation proportional?
b) Who does Ralph envy?
c) Who does Alice envy?
d) Who does Ed envy?
e) Who does Trixie envy?
f) Is there an allocation that makes Ralph better off without making anyone else worse off?
g) Does your answer to the previous question mean that this allocation is Pareto-optimal?
h) Find an equitable allocation.
i) Is the allocation you found in part (h) proportional?
13. Consider the moving-knife method with n = 3 players. Suppose player A yells cut first, player B yells cut second, and player C gets the remaining piece.
a) Is it possible for player C to be envious?
b) Is it possible for player B to be envious?
c) Is it possible for player A to be envious?
14. What is the flaw (i.e. drawback or shortcoming) in the divide-and-choose method?
15. Name two flaws in the moving knife method.

 

 

 

Answers:

1a) There are 3 possible correct answers:

C1 gets s2            C1 gets s2         C1 gets s3

C2 gets s1   or    C2 gets s3   or   C2 gets s1

 D gets s3             D gets s1               D gets s2

1b) There are 2 possible correct answers:

C1 gets s2            C1 gets s3        

C2 gets s1   or    C2 gets s1  

D gets s3            D gets s2           

1c) C1 gets s1               

      C2 gets s2  

      D gets s3                   

1d) Give D either s2 or s3.  Combine the remaining two slices into one large slice and use the divide-and-choose method.

2) C1 gets s2                   C1 gets s3

    C2 gets s3      or        C2 gets s1  

    C3 gets s1                       C3 gets s2

     D gets s4                  D gets s4

3) C1 gets s2                   C1 gets s4

    C2 gets s4                 C2 gets s2  

    C3 gets s3       or            C3 gets s3

    C4 gets s5                 C4 gets s5

     D gets s1                  D gets s1

4) C1 gets s5                  

    C2 gets s1  

    C3 gets s6

    C4 gets s2

    C5 gets s3

     D gets s4

5a) C1: {s3, s4}, C2: {s1, s3. s4}, C3: {s3}

5b) C1 gets s4, C2 gets s1, C3 gets s3 and D gets s2

6) Give D s6.  Give s4 or s5 to C3, let’s say s4.  Then give s5 to C4. Give s2 or s3 to C2, let's say s2. Take the two remaining slices s3 and s1 and combine them into a big slice and let C1 and C5 employ the divide-and-choose method on the big slice. 

7a) Player 1 felt all 3 pieces were equal until the trimming was done, so he now feels two are equal and the trimmed piece is smaller   Since the trimmed piece must be gone after step 4, he is not envious.

7b) Player 2 is not envious since he created a 2-way tie for first and at least one of those two pieces is available when it is his turn to pick. 

7c) Player 3 is not envious since he had first choice. 

7d) Player 1 does not envy player 2 because he is choosing ahead of player 2.  Player 1 does not envy player 3 because player 3 has the trimmed piece and player 1 considers the trimmed piece plus all of the trimmings to be only one-third of the whole. 

7e) Player 2 envies no one because he made all 3 pieces of the trimmings equal in step 6.

7f) Player 3 is not envious because he chose first in step 7. 

8. Clinton prevails on the number and timing of the debates as well as the format.  Dole prevails on the Perot issue.  As to the issue of length, Clinton holds about 74% of the say and Dole about 26% of the say.  (By the way, the actual outcome of the negotiations closely mirrors our solution.  Perot was excluded from the debates.  There were two debates, one with a moderator and one in a town hall format.  And there was a compromise on the length issue with both being 90 minutes.)

9.  Yes.  Either a map of the land or the world’s largest knife.

10a) It only works when there are two players.

10b) The players must have large amounts of money available.
11a) No
11b) Yes, to make Javier better off, Mary would end up worse off.
11c) No, Javier does not get at least 50% of the whole.
11d) No, Javier envies Mary.
11e) No, Mary perceives her share to be greater than Javier perceives his share.
11f) No. By giving Javier Y and Mary X, we make Javier better off without making Mary worse off.
12a) No, Ed did not get at least 25% of the whole.
12b) Trixie
12c) no one
12d) Alice and Ralph
12e) no one
12f) No
12g) No. Before concluding that the allocation is Pareto optimal, we would also have to establish that there is no allocation that makes Ed better off without making anyone else worse off, and no allocation that makes Alice better off without making anyone else worse off, and no allocation that makes Trixie better off without making anyone else worse off.
12h) Give Ralph X, give Alice Z, give Ed Y, and give Trixie W.
12i) No, none of them get at least 25% of the whole.
13a) no
13b) no
13c) yes, if he thinks player B yelled cut too soon, A envies C. If he thinks player B yelled cut too late, A envies B.
14. It only works when n = 2.
15. It only works on continuous fair division problems and it is not envy-free.