13.1 The Adjusted Winner Procedure

1. The 1991 divorce of Ivana and Donald Trump was widely covered in the media. The marital assets included a 45-room mansion in Greenwich, Connecticut; the 118- room Mar-a-Lago mansion in Palm Beach, Florida; an apartment in the Trump Plaza; a 50-room Trump Tower triplex; and just over $1 million in cash and jewelry. Assume that points are assigned as follows:

Use the adjusted winner procedure to determine a fair allocation of the marital assets. (Exercise 1 courtesy of Catherine Duran.)

2. Suppose that Calvin and Hobbes discover a sunken pirate ship and must divide their loot. They assign points to the items as follows:

Use the adjusted winner procedure to determine a fair allocation of the loot. (Exercise 2 courtesy of Erica DeCarlo.)

3. This exercise illustrates how the adjusted winner procedure can be used to resolve disputes as well as to achieve fair allocations. Suppose that Mike and Phil are roommates in college, and they encounter serious conflicts during their first week at school. Their resident adviser decides to use the adjusted winner procedure to resolve the dispute. The issues agreed upon, and the (independently assigned) points, turn out to be the following:

Use the adjusted winner procedure to resolve this dispute. (Exercise 3 courtesy of Erica DeCarlo.)

4. Suppose that a labor union and management are trying to resolve a dispute that involves four issues: the base salary of the workers, the annual salary increase that workers can expect, the benefits package the workers will receive, and the amount of vacation time to which each worker will be entitled. Use the adjusted winner procedure to resolve this dispute, with the following point assignments:

5. Mary and Fred are serving as co-chairs of the mathematics department. There are a number of time-consuming tasks that must be done by one or the other. It really doesn’t matter who does which task, except that they disagree on how unpleasant particular tasks are. They decide to use the adjusted winner procedure by phrasing items as “The other co-chair will handle __________________.” The items and point assignments are as follows:

6. Make up an example involving two people and several objects for which the adjusted winner procedure can be used, and then use the adjusted winner procedure to determine a fair division.

7. Make up an example involving two people and several issues for which the adjusted winner procedure can be used, and then use the adjusted winner procedure to determine a fair resolution of the dispute.

8. Suppose we have three items ($X$, $Y$, and $Z$) and three people (Bob, Carol, and Ted). Assume that each person spreads 100 points over the items (as in the adjusted winner procedure) to indicate the relative worth of each item to that person.

For each of the allocations listed below, indicate the following:

Allocation 1: Bob gets $Z$, Carol gets $Y$, and Ted gets $X$. (This is not Pareto-optimal.)

Allocation 2: Bob gets $Y$, Carol gets $Z$, and Ted gets $X$. (This is not Pareto-optimal.)

Allocation 3: Bob gets $X$, $Y$, and $Z$. (This is Pareto-optimal; explain why.)

Allocation 4: Bob gets $Y$, Carol gets $X$, and Ted gets $Z$. (This is Pareto-optimal.)

Allocation 5: Bob gets $X$, Carol gets $Y$, and Ted gets $Z$. (This is Pareto-optimal.)

13.2 The Knaster Inheritance Procedure

9. If John bids $28,225 and Mary bids $32,100 on their aging parents’ old classic car, which they no longer drive, how would you reach a fair division?

10. John and Mary inherit their parents’ old house and classic car. John bids $28,225 on the car and $55,900 on the house. Mary bids $32,100 on the car and $59,100 on the house. How should they arrive at a fair division?

11. Can you modify your fair-division procedure in Exercise 10 so that both John and Mary receive one of the two objects while still considering the allocation as fair?

12. Describe a fair division for three heirs, $A$, $B$, and $C$, who inherit a house in the city, a small farm, and a valuable sculpture, and who submit sealed bids (in dollars) on these objects as follows:

13.3 Fair Division and Organ Transplant Policies

13. Construct the table showing how points would be allocated among the following four potential recipients for a kidney transplant, according to the criteria in Section 13.3.

14. Does the example in Exercise 13 give rise to the same kind of paradox as in Section 13.3? Explain why or why not.

13.4 Taking Turns

15. Suppose that Bob and Carol rank a series of objects, from most preferred to least preferred, as follows:

Assume that Bob and Carol use the bottom-up strategy and that Bob gets to choose first. Determine Bob’s first choice and the final allocation.

16. Repeat Exercise 15 under the assumption that Carol gets to choose first.

17. Mark and Fred have inherited a number of items from their parents’ estate, with no indication of who gets what. They rank the items from most preferred to least preferred, as follows:

Assume that Mark and Fred use the bottom-up strategy and that Mark gets to choose first. Determine Mark’s first choice and the final allocation.

18. Repeat Exercise 17 under the assumption that Fred gets to choose first.

19. Suppose that Donald and Ivana Trump decide to settle their divorce (described in Exercise 1 on page 563) by taking turns. Assume that they both use the bottom- up strategy, and Donald chooses first. Determine Donald’s first choice and the final allocation. (Assume that Donald values the Connecticut estate slightly more than he values the Trump Plaza apartment.)

20. Repeat Exercise 19 under the assumption that Ivana gets to choose first.

13.5 Divide-and-Choose

21. Suppose that Bob is entitled to one-fourth of a cake and Carol is entitled to three-fourths. In a few sentences, explain how divide-and-choose can be used to achieve an allocation in which each party is guaranteed to receive at least as much as he or she is entitled to.

22. Suppose that Bob, Carol, and Ted view a cake as having 18 units of value, with each unit of value represented by a small square (as in the accompanying illustration). Suppose, however, that the players value various parts of the cake differently (or that Bob views the cake as being perfectly rectangular, whereas Carol and Ted see it as skewed in opposite ways). We represent this pictorially as follows:

Assume that all cuts that will be made are vertical.

23. Assume that Bob and Carol view the cake as in Exercise 22, but assume also that each knows how the other values the cake, and that neither is spiteful. Suppose they are to divide the cake using the rules, but not necessarily the strategies, of divide-and-choose. Is Bob better off being the divider or the chooser?

13.6 Cake-Division Procedures: Proportionality

24. Suppose that Players 1, 2, and 3 view a cake as in Exercise 22. Notice that each player views the cake as having 18 square units of area (or value). Assume that each player regards a piece as acceptable if and only if it is at least $18/3=6$ square units of area (his or her “fair share”). Assume also that all cuts made correspond to vertical lines.

25. Suppose that Players 1, 2, and 3 view a cake as follows:

26. Suppose Players 1, 2, and 3 view a cake as in Exercise 25. Illustrate the last-diminisher method (still restricting attention to vertical cuts and, in addition, assuming that the piece potentially being diminished is a piece off the left side of the cake) by following steps (a) through (f) below.

27. The Banach-Knaster last-diminisher method is not the only well-known cake-division procedure that yields a proportional allocation for any number of players. There is also one due to A. M. Fink (sometimes called the lone-chooser method). For three players (Bob, Carol, and Ted), it works as follows:

28. In A. M. Fink’s procedure (described in Exercise 27), suppose that a fourth person (Alice) comes along after Bob, Carol, and Ted have already divided the cake among themselves so that each of the three thinks that he or she has a piece of size at least one-third. Mimic what was done in the three-person case to obtain an allocation among the four that is proportional. (Hint: Begin by having Bob, Carol, and Ted divide the pieces they have into a certain number—how many?—of equal parts.)

13.7 Cake-Division Procedures: The Problem of Envy

29. Suppose Players 1, 2, and 3 view the cake as in Exercise 25. Illustrate the envy-free procedure for $n=3$ (yielding an allocation of part of the cake) by following steps (a) through (c) below. Again, restrict attention to vertical cuts.

30. There is a two-person moving-knife cake-division procedure due to A. K. Austin that leads to each player receiving a piece of cake that he or she considers to be of size exactly one-half. It begins by having one of the two players (Bob) place two knives over the cake, one of which is at the left edge and the other of which is parallel to the first and placed so that the piece between the knives (A in the picture below) is of size exactly one-half in Bob’s estimation.

If Carol agrees that this is a 50-50 division, we are done. Otherwise, Bob starts moving both knives to the right—perhaps at different rates—so that the piece between the knives remains of size one-half in his eyes. Carol calls “stop” at the point when she also thinks the piece between the two knives is of size exactly one-half.

31. Here are the steps in the Selfridge-Conway procedure for three players.

(Thanks to Michael Rosenthal for suggesting this exercise topic.)

13.8 Vickrey Auctions

32. Consider the Vickrey auction for a lamp that is worth $100 to our bidder Bob (page 559). Suppose someone suggests that Bob would always do as well with a bid of $80. Show that this is false by playing the role of another bidder who could make Bob regret a choice of bidding $80 rather than his (sincere) bid of $100. You are free to make any assumptions that you want about the bids other than Bob’s and your own.

33. Consider the Vickrey auction for a lamp that is worth $100 to our bidder Bob (page 559). Suppose someone suggests that Bob would always do as well with a bid of $120. Show that this is false by playing the role of another bidder who could make Bob regret a choice of bidding $120 rather than his (sincere) bid of $100. You are free to make any assumptions you want about the bids other than Bob’s and your own.

Chapter Review

34. Beth and Harvey are co-captains of their intramural softball team. As in Exercise 5 (page 564), there are a number of time-consuming tasks that must be done by one or the other. It really doesn’t matter who does which task, except that they disagree on how unpleasant particular tasks are. Like Fred and Mary, Beth and Harvey decide to use the adjusted winner procedure by phrasing items as “The other co-chair will handle _____________.” The items and point assignments are as follows:

35. Describe a fair division for three children, $E$, $F$, and $G$, who inherit equal shares of their parents’ classic car collection and who submit sealed bids (in dollars) on these five cars as follows:

36. In the scheme for arriving at a priority ranking for organ transplants, how might one change the way points are assigned for “waiting time” so that the kind of paradox that arose in Section 13.3 could not occur?

37. Suppose that Mary and Fred decide to settle the question of which co-chair performs which tasks (described in Exercise 5 on page 564) by taking turns. Assume that they both use the bottom-up strategy, and Mary chooses first. Determine the final allocation of tasks.

38. Repeat Exercise 37 under the assumption that Fred chooses first.

39. If you and another person are using the divide-and-choose procedure to divide something between you, would you rather be the divider or the chooser? (Assume that neither of you knows anything about the preferences of the other.)

40. There is a moving-knife version of the Banach- Knaster procedure that is due to Dubins and Spanier. To describe it, we picture the cake as being rectangular and the procedure beginning with a referee holding a knife along the left edge, as illustrated below.

Assume, for the sake of illustration, that there are four players (Bob, Carol, Ted, and Alice). The referee starts moving the knife from left to right over the cake (keeping it parallel to the position in which it started) until one of the players (assume it is Bob) calls “cut.” At this time, a cut is made, the piece to the left of the knife is given to Bob, and he exits the game. The knife starts moving again, and the process continues. The strategies are for each player to call “cut” whenever it would yield him or her a piece of size at least one-fourth.