Chapter 3: Fair Division



Section 3.1 Fair-Division Games

• Initial Introduction: Give students 3 oddly shaped objects and ask them to divide it evenly.

(No axis of symmetry, Amorphous shapes) – GOAL: From every student’s personal opinion they are correct

• Elements of a Fair Division Game:

o Goods/ “Booty”, S: items to be divided

▪ Example: physical objects (pie, land) or intangibles (rights or obligations)

o Players, P: parties entitled to share goods

▪ Example: individuals, groups, institutions, etc

o Value System: each player’s internal ability to quantify (assign value) the goods or any part of the goods

not necessarily the same for every player

▪ Absolute Terms: worth money Relative Terms: worth a percentage of Goods

• FAIR SHARE: A share is FAIR to a player 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 (EQUAL PROPORTION)

o 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? s2 and s4

o Example #2: Geoff is one of 5 players. He values s1 = $25, s2 = $30, s3 = $13, s4 = $12, s5 = $20. Fair is greater than or equal to what dollar value? Which shares are fair to Geoff? s1, s2 and s5

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

o INDIVIDUAL GOAL: “Every player wants to maximize their share of the booty”

• ASSUMPTIONS about Players:

o Rationality: each player is a thinking, rational agent seeking to Maximize share of the booty.

moves based on reason alone (not emotions, psychology, etc)

o Cooperation: players are willing participants and accept the rules of the game as binding.

The game will terminate in a finite number of moves = rules

o Privacy: each player has NO useful information about other players’ value systems

o Symmetry: players have equal rights in sharing the goods

At a minimum, each player is entitled to a proportional share of S.

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

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

▪ Examples: land, pizza, …

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

▪ Examples: houses, cars, jewelry, …

o Mixed: both continuous and discrete goods

▪ Example: will or estate

| |Chocolate |Strawberry |

|Value |¾ |¼ |

|Fraction | | |

|Physical |C/ 1800 |S/1800 |

|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: 3

3 + 1 = 4 = denominator

Strawberry: 1

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

“Multiply Columns and Add”

o Relative Terms = ((3/4) (fraction of physical amount of C) + (1/4) (fraction of physical amount of S))

o Absolute Terms = Relative * (total dollar amount)

How much is each half of the cake worth to Dan?

Relative Terms: Absolute Terms:

(3/4)(180/180) + (¼)(0/180) = 3/4 $20 (3/4) = $15 for C

(3/4)( 0/180) + (¼)(180/180) = ¼ $20 (¼) = $5 for SB

If we cut a slice that includes 30 degrees of chocolate and 30 degrees of strawberry, how much will that slice be worth to him?

Relative: (3/4)(30/180) + (¼)(30/180) = 1/6 Absolute: $20(1/6) = $3.33

• Example #2: Greg orders a pizza, 1/3 is 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 |3/9 |5/9 |1/9 |

|Fraction | | | |

|Physical |H/1200 |P/1200 |C/1200 |

|Fraction | | | |

value of any piece of pizza:

(1/3) (H/1200) +

(5/9)( P/1200) +

(1/9)( C/1200)

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)

Piece One: (3/9) (40/120)+ (5/9)(80/120) = 13/27

Piece Two: (3/9) (80/120) + (1/9)( 40/120)= 7/27

Piece Three: (5/9)( 40/120) + (1/9)(80/120) = 7/27

Piece One! > 1/3

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

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

DEMO FOOD ACTIVITY: DIVIDER CHOOSER WITH ONE STUDENT

• REQUIREMENTS:

2 players and Continuous Goods

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

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

o Divider always views the two shares as 50% based on their value

o Chooser: Picks the share he or she believes to be fair or better and leaves other for divider

o Both players therefore receive what they believe to be fair shares of S

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

Chooser because you always get 50% or more.

Divider always gets exactly 50%

|Scotty |RV |A | |Jordan |RV |A |

|Physical Fraction |RV/ 1800 |A/1800 | |Physical Fraction |RV/ 1800 |A/1800 |

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 (i.e. does not value that half at all) and loves red velvet. Scotty divides the cake as follows: 60 degrees of angel food and 120 degrees of red velvet on one half of the cake.

Which side will Jordan choose? Why?

1 (2/3) + 0(1/3) = 2/3 = wants piece with more velvet

1 (1/3) + 0(2/3) = 1/3

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

|Physical Fraction |CC/ 1800 |S/1800 | |Physical Fraction |CC/ 1800 |S/1800 |

Example #2: Myca and Miles are trying to split a cookie cake that is have chocolate chip (CC) and half sugar (S) cookie. 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?

Myca: (4/5)(72/180) + (1/5)(162/180) = 0.5 Miles: (3/4)(72/180) + (1/4)(162/180) = 0.525

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 |C/ 1800 |S/1800 |

GOAL = create two pieces worth ½ or 50%

Currently have two halves that are worth ¾ and ¼

You want to cut in the half or section with more value to create two equal pieces by making a proportion.

Proportion: [pic]

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 half to create two fair shares of the sandwich? Why?

Veggie = 1 => 1 Italian = 0 => 0

CREATE PROPORTIONS: [pic]

3b. Would a carnivore cut in the veggie or Italian half to create two fair shares of the sandwich? Why? Veggie = 1 => 0 Italian = 1 => 1

CREATE PROPORTIONS: [pic]

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

Veggie = 1 => 1/3

Italian = 2 => 2/3

CREATE PROPORTIONS: [pic]

Section 3.3 Lone-Divider Method (CONTINUOUS)

Introduction with odd shape on board and 4 students to pick

• Method for 3 Players

1) Assign Players: Randomly assign a divider (D)

2) Division: Goods into 3 fair shares s1, s2, and s3 by divider

3) Bidding: 2 Choosers identify value of each share to them in a bid list

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”

If possible players will receive the more preferred fair share, but still ok with anything that is fair.

| |s1 |s2 |s3 |

|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.

Bid List: Dale = {s1, s2, s3}, Cindy = {s1, s3}, and Claire = {s1, s3}

Distribution: Dale = s2, Cindy = s3, and Claire = s1 remember Optimal Distribution

CASE #2: CONFLICT = Choosers can 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

o According to both C1 and C2 remaining value > 2/3 and Both C1 and C2 will receive a share > 1/3

| |s1 |s2 |s3 |

|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.

Bid List: Dale = {s1, s2, s3}, Cindy = { s3}, and Claire = { s3}

Distribution: Dale = s1 (least preferred),

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

Cindy = 80 % and Claire = 90%

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

Cindy = 40 % and Claire = 45% of original

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

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

2) Division: for N fair pieces now (1/N = Value)

3) Bidding: bid lists from all choosers now

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 |

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

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

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

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

Bid List: Annie = {s1}, Beth = {s1, s2, s3, s4}, Claire = {s2, s3}, Destiny = {s2, s3},

Distribution: Annie = S1, Beth = S4, Claire = S2, Destiny = S3

▪ 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 |

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

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

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

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

Bid List: Marcus = {s1, s2, s3, s4}, Aaron = {s4}, Amy = {s2, s3}, Kim = {s4}

Distribution: Amy gets s2, Marcus gets s3 (least valued from Aaron and Kim)

Kim = 28.5% of original and Aaron = 30% of original

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

introduction demo - Section 3.6 Method of Sealed Bids (DISCRETE)

• Discrete Fair Division

• Players become buyers and sellers of items

• Conditions:

o Players must have own money to play.

o Players must accept money as a substitute for an item.

• Method:

1) Bidding: each player bids for each item honestly

Done independently without knowledge of other bids

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

Players may be allocated more than one item

Ties broken arbitrarily (random, coin flip idea)

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

GOAL IS TO MAKE PLAYERS HAVE EXACT FAIR AMOUNT IN PHYSICAL ITEMS OR CASH

▪ Fair Dollar Share (FDS): add a player’s bids together and divide by total number of players (1/Nth the total value of all goods to a player)

Total Value/ # of players

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

(money needed to make fair dollar share) Item < FDS

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

(excess money to remove to make fair dollar share) Item > FDS

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

a. Surplus Money = Total Pay – Total Get Money

b. Division = Surplus/ # of Players

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

• EXAMPLE #1: Three heirs (Andre, Bea, Chad) must divide up an estate consisting ofa house, farm, and painting. Here are their bids:

| |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 |210,000 |210,000 |220,000 |

|Items Allocated |Farm: 430,000 |Painting: 59,000 |House: 175,000 |

|Get/ Pay Amount |FDS - ITEM = -220,000 pay |FDS - ITEM = +151,000 |FDS - ITEM = +45,000 |

| | |get |get |

|Surplus? |220,000-151,000-45,000 = 24,000 … 8,000 to each player |

|Final Settlement: |Farm, -220,000 and $8,000 |Painting, $151,000 and 8000 |House 45,000 and 8,000 |

• EXAMPLE #2: Zach, Wendy, Liam, and Caroline’s friend tanner is moving out of town and is planning to give away stuff from his apartment. He let’s them decide who will get what.

| |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 |1,350 |1,300 |1,230 |1,100 |

|Items Allocated |Kitchen 2,800 |Furniture 2500 |Nothing 0 |Electronics 520 |

|Get/ Pay Amount |FDS - ITEM = -1,450 |FDS - ITEM = -1200 |FDS - ITEM = +1,230 get |FDS - ITEM = +580 |

| |pay |pay | |Get |

|Surplus |1450+1200-1230-580 = 840 … 210 to each player |

|Final Settlement |Kitchen, -1,450 , 210 |Furniture, -1200, 210 |Nothing 1230, 210 |Electronics, 560, 210 |

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 |

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

|Yacht |$120,000 |$125,000 |$119,000 |$129,000 |$132,500 |

|Klee |$150,000 |$135,000 |$99,000 |$179,000 |$149,000 |

|FAIR SHARE |$135,800 |$131,300 |$114,600 |$133,900 |$130,700 |

|Items Allocated |BMW, Saab, Miro |House |Cottage |Klee |Yacht |

|PAY or GET |-$13,200 pay |-$83,700 pay |+$52,100 get |-$45,100 pay |- $1,800 Pay |

|Surplus | [(13200 + 83700 + 45100) – (52100 + 1800)]/5= $91700/5 = 18340 |

HOMEWORK: p.120 #51-53, 55

INTRO – JOLLY RANCHER DEMO - Section 3.7 Method of Markers (DISCRETE)

• Player’s DON’T put up any of their own money

• Conditions:

o Many More items to be divided than players

o Items are all reasonably close in value

• Method: N players with M items

o All M items are arranged in a random order

o Bidding: each player will separately split the arrangement of items into N segments

Each segment is considered a fair share by player that made it and most contain at least one item

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

Ties between players are broken at random

the player’s segment that ends the soonest = allocation

Each Player will be allocated exactly ONE of their segment from bidding

▪ 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 Allocation:

▪ 1st Segment: From Left to Right find the 1st marker of any player.

That player receives 1st segment and ties are broken randomly

That player’s remaining markers are removed from the array

▪ 2nd Segment: Scan Left to Right to find the 1st 2nd marker of any remaining player

That player receives their 2nd Segment and ties are broken randomly

▪ Repeat allocation until all players have received a segment

o Dividing Leftovers: Random lottery if less items than players

Repeat Method of Markers if many 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 | | | | |

Leftovers: Depends on whether Greg or Sarah is picked to break tie

Pieces 5 and 6 or Pieces 5, 6, and 10

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

[pic]

• 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 = 0, C = 0, W = 1

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

P = 1, C = 0, W = 2

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

P = 1, C = 2, W = 1

The nuts are lined up as shown:

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

|Alice |0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 |

|Beth |1 1 2 0 1 0 1 1 1 2 2 0 1 0 1 1 0 0 |

|Carol |1 1 1 2 1 2 1 1 1 1 1 2 1 2 1 1 2 2 |

(a) Determine where each player places markers.

Alice: total value is 3 => fair share is 1: PPW, CPCPPPW, WCPCPPCC

Beth: total value is 15=> fair share is 5: PPWCP, CPPPW, WCPCPPCC

Carol: total value is 24 => fair share is 8: PPWCPC, PPPWWCP, CPPCC

(b) Describe the allocation of the nuts.

Alice: PPW Beth: CPPPW Carol: CPPCC

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

C P W C P

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

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

Chocolate

Strawberry

Chocolate

Strawberry

C

P

H

1

2

3

1

2

3

RV

A

1200

600

CC

S

1620

720

Chocolate

Strawberry

Veggie

Italian

B1

B2

B3

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