Chapter 3: Fair Division



Section 3.1 Fair-Division Games

• Elements of a Fair Division Game:

o GOODS (S): items to be divided

Example:

o PLAYERS, P: parties entitled to share goods

Example:

o VALUE SYSTEM: A player’s internal ability to quantify (assign value) the goods or any part of it

ABSOLUTE Terms: RELATIVE Terms:

• FAIR SHARE: A share is FAIR if the it is worth at least 1/N of the total value of goods in the opinion of a player, where N = Total Number of Players

Example #1: Paul is one of 4 players. He values s1 at 12% of S, s2 at 27% of S, s3 at 18% of S, and s4 at 43% of S.

Fair is greater than or equal to what percent?

Which shares are fair to Paul? ________________________________________

Example #2: Geoff is one of 5 players. He values s1 = $35, s2 = $40, s3 = $23, s4 = $22, s5 = $30.

Fair is greater than or equal to what dollar value?

Which shares are fair to Geoff? ____________________________

**GOAL of the GAME: Each player gets a fair share of S**

• FOUR ASSUMPTIONS about Players:

(1) RATIONALITY: each player is a thinking, rational agent seeking to _______________ share of the booty.

(2) COOPERATION: players are willing participants and _____________________ the rules of the game.

(3) PRIVACY: each player has ___________useful information about other players’ value systems

(4) SYMMETRY: players have ________________________________________ in sharing the goods

Fair – Division Method: set of rules that define how a game is to be played

CONTINUOUS: Goods are divisible in infinitely many ways and shares can be increased and decreased by arbitrarily small amounts (almost nothing like a sliver of pie)

DISCRETE: Goods are made up of indivisible objects (at a certain point you can’t break it down smaller)

MIXED: both continuous and discrete goods

| |Chocolate |Strawberry |

|Value | | |

|Fraction | | |

|Physical | | |

|Fraction | | |

• Example #1: Dan buys a huge cake for $20. Half is chocolate and half is strawberry. Dan values chocolate 3 times as much as he values strawberry.

VALUE FRACTIONS:

Chocolate:

Strawberry:

What is the value of any piece of cake: Sum of (Value Fraction * Fraction of Physical Amount)

“Multiply Columns and Add”

RELATIVE Value = ABSOLUTE Value =

How much is each half of the cake (Strawberry or Chocolate) worth to Dan?

Relative: Absolute:

Strawberry =

Chocolate =

If a piece of cake includes 30 degrees of chocolate and 30 degrees of strawberry, how much will that piece be worth to Dan?

Relative: Absolute:

• Example #2: Greg orders a pizza that is 1/3 Hawaiian, 1/3 Cheese and 1/3 is Pepperoni. Greg values Hawaiian 3 times as much as he values Cheese, and Pepperoni 5 times as much as cheese.

| |H |P |C |

|Value | | | |

|Fraction | | | |

|Physical | | | |

|Fraction | | | |

If Greg wanted to share the pizza with 2 other friends, he cut 3 pieces.

Piece One: 400 of H and 800 of P

Piece Two: 800 of H and 400 of C

Piece Three: 800 of C and 400 of P

WHICH PIECE WOULD GREG WANT? (ie what pieces are fair shares for 3 players)

HOMEWORK: p.111 #1 - 3, 5, 7

Section 3.2 2 Players: Divider-Chooser Method (CONTINUOUS)

• REQUIREMENTS:

• Divider – Chooser Method: “you cut – I choose”

o DIVIDER: Divides goods into 2 fair shares (divider’s value perspective)

o CHOOSER: Picks the share believed to be fair or better and leaves other for divider

Is it better to be the chooser or the divider? Explain.

|Jordan |RV |A |

|Value | | |

|Fraction | | |

|Physical Fraction | | |

Example #1: Scotty and Jordan order a cake to celebrate their birthdays. Half is angel food and the other half is red velvet. Scotty values angel food and red velvet exactly the same while JORDAN hates angel food (does not value at all) and loves red velvet. Scotty divides the cake with 60 degrees of angel food and 120 degrees of red velvet on one half of the cake.

Which side will Jordan choose? Why?

|Myca |CC |S | |Miles |CC |S |

|Physical Fraction | | | |Physical Fraction | | |

Example #2: Myca and Miles are trying to split half chocolate chip (CC) and half sugar (S) cookie cake. Myca like CC four times as much as S. Miles likes CC three times as much as S. The cookie cake was sliced into pieces. One piece was 720 of CC and 1620 of S as pictured.

Which player Myca or Miles divided the cake? Which piece would the chooser take?

If you are the divider, how would you cut an object once to create two fair shares?

EXAMPLE #3: An ice cream cake is ½ chocolate and ½ strawberry. If you like chocolate three times as much as strawberry, where can you can you cut the ice cream cake to create two pieces of equal value?

| |C |S |

|Value | | |

|Fraction | | |

|Physical Fraction | | |

GOAL: Reduce the size of a section that is greater than 50% of the value to make to equally valued pieces.

Set Up Proportions: What you HAVE to what you WANT between Physical Information and Value Information.

EXAMPLE #4: A foot long sub from subway is 6 inches of veggie and 6 inches of Italian.

3a. Would a vegetarian cut in the Veggie or Italian part to create two fair shares of the sandwich? Why?

3b. Would a carnivore cut in the Veggie or Italian part to create two fair shares of the sandwich? Why?

3c. Suppose you liked Italian twice as much as Veggie. Would you cut in the Veggie or Italian part to create two fair shares of the sandwich? Why?

Section 3.3 Lone-Divider Method (CONTINUOUS)

• Method for 3 Players

1) Assign Players: Assign a player to be the divider (D)

2) DIVISION: Divider makes 3 fair shares (s1, s2, s3) from the goods

3) BIDDING: Choosers identify value of each share to put them in a bid list of fair shares

Fair Shares: valued ≥ 1/3 Unfair Shares: valued < 1/3

4) DISTRIBUTION: Shares are given to players based on bid lists

CASE #1: Each Chooser can receive a DIFFERENT FAIR share from bid list

Optimal Distribution: “ Every player wants to maximize their share of the booty”

| |s1 |s2 |s3 |Bid List |

|Dale |33 1/3% |33 1/3% |33 1/3% | |

|Cindy |35% |10% |55% | |

|Claire |40% |25% |35% | |

EXAMPLE#1: CASE 1- 3 siblings Dale, Cindy, and Claire are dividing their backyard into 3 pieces of land. Determine which piece of the backyard each sibling will get.

Distribution:

CASE #2: CONFLICT = Choosers want and should only receive the SAME FAIR share.

• DIVIDER gets a share that is unfair to both Choosers (is possible least preferred)

• Remaining shares are reconnected and the two choosers will perform DIVIDER-CHOOSER method on this new combined goods

| |s1 |s2 |s3 |Bid List |

|Dale |33 1/3% |33 1/3% |33 1/3% | |

|Cindy |20% |30% |50% | |

|Claire |10% |20% |70% | |

EXAMPLE #2: CASE 2 - Now the 3 siblings are dividing a pie their grandmother baked for them. Determine which piece of pie each sibling will receive.

What is the conflict in Cindy and Claire’s Bid Lists?

Distribution:

How much is the “new combined goods” valued to Cindy and Claire?

What is the minimum amount each would receive in divider-chooser?

Lone – Divider with more than 3 Players (N players):

1) Assign Players: 1 Divider and N-1 Choosers

2) Division: Create N fair pieces (Total Value/N)

3) Bidding: Each Chooser creates a bid list for what they believe is fair to them

4) Distribution: Compare choosers’ bid lists

▪ Case #1: All choosers value a different share

Each chooser gets a fair share and Divider gets remaining piece

• EXAMPLE #3: CASE 1

| |s1 |s2 |s3 |s4 |Bid List: |

|Annie |40% |20% |20% |20% | |

|Beth |25% |25% |25% |25% | |

|Claire |20% |35% |25% |10% | |

|Destiny |15% |35% |45% |5% | |

ANNIE: ___________ BETH: _____________ CLAIRE: _____________ DESTINY: .______________

▪ Case #2: CONFLICT = There are more choosers than items they think are fair in bid lists (Exp: 2 choosers 1 piece, 3 choosers 1 or 2 pieces)

• Non-conflicted choosers get one of their fair shares

• Divider gets an unfair share of all conflicted choosers

• Conflicted choosers combine remaining shares and repeat the method between them

• EXAMPLE #4: Case 2

Marcus is the Divider and Aaron, Kim, and Amy are Choosers.

| |s1 |s2 |s3 |s4 |Bid List: |

|Marcus |25% |25% |25% |25% | |

|Aaron |20% |20% |20% |40% | |

|Amy |15% |35% |30% |20% | |

|Kim |22% |23% |20% |35% | |

Distribution: Marcus: _________ Aaron: ________ Amy: __________ Kim: _________

HOMEWORK: pp. 113 - 115 #13, 17, 19, 21, 25, 27

Section 3.6 Method of Sealed Bids (DISCRETE)

Two Required Conditions: (1) Each Player Must Have ENOUGH MONEY for their Bids

(2) Players will ACCEPT MONEY in equivalent value to items

• Method:

1) Bidding: each player bids for each item honestly

2) Allocation: Each item will go to the highest bidder of the item

3) First Settlement: Players either owe or are owed money by the estate based on items allocated

▪ Fair Dollar Share (FDS): add a player’s bids together and divide by total number of players

▪ Owed “Get” Money: if the fair dollar share > value of player’s allocated items

▪ Owe “Pay” Money: if the fair dollar share < value of player’s allocated items

Each Player pays or gets difference of their fair dollar share and total item value

4) Division of Surplus: surplus money is divided _______________ among all players

5) Final Settlement: First settlement and surplus money given to each player

(Combine PAY/GET with SURPLUS)

• EXAMPLE #1: Three heirs (Andre, Bea, Chad) must divide up an estate of a house, farm, and painting.

| |Andre |Bea |Chad |

|House |$150,000 |$146,000 |$175,000 |

|Farm |$430,000 |$425,000 |$428,000 |

|Painting |$50,000 |$59,000 |$57,000 |

|Fair Dollar Share | | | |

|Items Allocated | | | |

|Get/ Pay Amount | | | |

|Surplus? | |

|Final Settlement: | | | |

• EXAMPLE #2: Zach’s, Wendy’s, Liam’s, and Caroline’s friend tanner is moving out of town and is planning to give away stuff from his apartment.

| |Zach |Wendy |Liam |Caroline |

|Furniture |2,200 |2,500 |2,110 |1,980 |

|Electronics |400 |300 |470 |520 |

|Kitchen |2,800 |2,400 |2,340 |1,900 |

|Fair Dollar Share | | | | |

|Items Allocated | | | | |

|Get/ Pay Amount | | | | |

|Surplus | |

|Final Settlement | | | | |

Example #3: The players are Al, Ben, Cal, Don, and Ed who are splitting up an inheritance comprising a house, a vacation cottage, two cars (a BMW and a Saab), a yacht, and two valuable paintings (a Miro and a Klee). The brothers agree beforehand that any ties for high bid will be resolved with a coin toss.

|Item |Al |Ben |Cal |Don |Ed |

|House |$200,000 |$215,000 |$195,000 |$175,000 |$205,000 |

|Cottage |$60,000 |$49,000 |$62,500 |$59,500 |$55,000 |

|Saab |$25,000 |$19,000 |$22,500 |$24,500 |$19,500 |

|Miro |$95,000 |$89,000 |$50,000 |$75,000 |$65,000 |

|TOTAL | | | | | |

|FAIR SHARE | | | | | |

|Items | | | | | |

|PAY or GET | | | | | |

|Surplus | |

|FINAL | | | | | |

HOMEWORK: p.120 #51 - 53, 55

Section 3.7 Method of Markers (DISCRETE)

Two Required Conditions: (1) MORE ITEMS than PLAYERS

(2) Items are RELATIVELY CLOSE in value

• Method:

o All Items are arranged in a RANDOM order

o BIDDING: each player will separately split the arrangement of items into fair segments based on total number of players.

▪ 4 players ( 4 segments created by 3 markers

o ALLOCATION: Compares all player’s segments simultaneously from Left to Right Order

▪ 1st Segment: 1st Segment that ends the soonest will be given away

▪ 2nd Segment: All Remaining players will have second segments compared.

2nd segment that ends the soonest will be given to that player

▪ REPEAT: with remaining players until all players have received ONE segment

o Dividing Leftovers:

▪ Random Lottery if less remaining items than players

▪ Repeat Method of Markers if more items than players remain

EXAMPLE 1: p. 106 #3.11 Greg, Josh, Michelle, and Sarah are cousins who are trying to split leftover Halloween candy. In total they have 20 pieces of Reese’s, M&Ms, Milky Way, Crunch Bars, Snickers, Mr. Good Bar, Baby Ruth, and Hershey candy.

|1 |2 |3 |4 |5 |6 |

|Michelle |1 – 6, 7 – 9, 10 – 14, 15 - 20 | | | | |

|Sarah |1 – 5, 6 – 10, 11 – 16, 17 - 20 | | | | |

• EXAMPLE #2: Use the method of markers to assign the following shapes to 4 players (A, B, C, D)

Marks Represent the start and end of each segment for a given player:

Example: B1 to B2 is the second segment for player B

[pic]

Player A: Player B: Player C: Player D:

• EXAMPLE #3: Alice, Beth, and Carol want to divide what is left of a can of mixed nuts. There are 6 cashews, 9 pecan halves, and 3 walnut halves to be divided. The women’s value systems are as follows:

1. Alice does not care at all about pecans or cashews but loves walnuts.

P = _______ C = _______ W = _________ FAIR:

2. Beth Likes walnuts twice as much as pecans and really does not care for cashews.

P = _______ C = _______ W = _________ FAIR:

3. Carol likes all the nuts but likes cashews twice as much as the others.

P = _______ C = _______ W = _________ FAIR:

| |P P W C P C P P P W W C P C P P C C |

|Alice | |

|Beth | |

|Carol | |

(a) Determine where each player places her markers. (Segments that are fair in value)

ALICE: BETH: CAROL:

(b) Describe the allocation of the nuts.

ALICE: BETH: CAROL:

(c) Describe the surplus and what would you do with it.

HOMEWORK: p.121 #59 – 67 (odd), 68

-----------------------

#1

Chocolate

Strawberry

Chocolate

Strawberry

C

P

H

1

2

3

#2

RV

A

1200

600

CC

S

1620

720

Chocolate

Strawberry

Veggie

Italian

#3

#4

#5

B1

B2

B3

[pic] !BCHJKLMNdkqx{|?¦©µ¶·¸ |

" * 0 1 3 4 5 6 A Q R T e q r „ ° íáØÑÍƿѿѺͺÍÆѺͳÍƺͯͫͤѺͤѺÍÑÍ ÑÍœ˜œ?…}ÍhÈRTh?

L>*[pic]hÈRTh?

L5?>*[pic]\?hÈRTh0&t>*[pic]h&DFh0&th

4Œ

hyBŽ5?>*[pic]

D1

D2

D3

A1

A2

A3

C1

C2

C3

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download