Fair Division

Objective: divide one or more objects among two or more parties fairly.

An allocation among n players is

• proportional: each player receives a piece that he/she perceives to be at least 1/n of the whole (e.g. same number of points).
• envy free: each player receives a piece he considers at least tied for largest or most valuable (no player would be happier with what another player received).
• pareto-optimal:   no other allocation, arrived at by any means can make one party better off without making the other party worse off.

The Adjusted Winner Procedure:

Problem:
There is a dispute between two parties, say Donald and Ivana Trump over a collection of assets:
    a Connecticut mansion, a Palm Beach mansion, a Trump Plaza appartment, a Trump Tower triplex, and cash/jewelry.
Find a "fair" and equitable way of dividing up the property.

Fair: each player receives what he/she perceives to be at least half of the total value of the assets.

Solution Algorithm:
1.    each party distributes 100 points over the items in a way that reflects their relative worth to that party.

 

asset	Donald's points	Ivana's points
Connecticut mansion	10	38
Palm Beach mansion	40	20
Trump Plaza apartment	10	30
Trump Tower triplex	38	10
Cash and jewely	2	2

 

Donald's assets		Ivana's assets
Palm Beach mansion	40	Connecticut mansion	38
Trump Tower triplex	38	Trump Plaza apartment	30
	78		68

So Ivana gets the cash and jewelry. Her new total: 70. She is still the loser.

4.    Method:
            go through the items on the winner's list and compute the point ratio:

        (winner's point value for the item)/(loser's point value for the item)

 

Donald's assets	point ratio
Palm Beach mansion	40    ---- = 2    20
Trump Tower triplex	38    --- = 3.8    10

Transfer (fractional a part of) items in order of increasing point ratio.

So the Donald has to hand over a part  x of his Palm Beach mansion. He keeps the part 1 - x of his value of the mansion.

What part? The part that would make the point totals equal.
 

Donald's point total after handover	Ivana's point total after handover
38 + 40(1 - x)	38 + 30 + 2 + 20 * x

These two quantities have to be the same.
Solve for x.

x = 2/15.
Then the respective point totals are both equal: 72.67.
Each of Donald and Ivana perceive that he/she gets 72.67% of the total value. That's fair and equitable.

Theorem: The Adjusted Winner Allocation is equitable, envy free, and pareto-optimal.

Problem: Suppose Calvin and Hobbes discover a sunken pirate ship and must divide their loot. They assign points as follows:
 

Objects	Calvin's points	Hobbes' points
cannon	10	5
anchor	10	20
unopened chest	15	20
doubloon	11	14
figurehead	20	30
sword	15	6
cannon ball	5	1
wooden leg	2	1
flag	10	2
crow's nest	2	1

Use the adjusted winner procedure to find a fair allocation of the loot.

This is a mathematical contribution to world peace.

(Bronislaw Knaster 1945)

Problem: Three or more people inherit a collection of assets. Find a fair way of distributing the assets.

Example: Bob, Carol, Ted and Alice inherit their parents' house.

Solution by Knaster's Inheritance Procedure:
1.    Each heir makes a simultaneous and independent bid for the asset.

 

Bob	Carol	Ted	Alice
120,000	200,000	140,000	180,000

 

Bob	Ted	Alice
30,000	35,000	45,000

 

Bob	Carol	Ted	Alice
40,000	house - 140,000	45,000	55,000

Problem:Describe a fair division for three children E, F, G, who inherit equal shares in their parents' classic car collection and who submit sealed bids on these cars:
 

	E	F	G
Duesenberg	18,000	15,000	15,000
Bentley	18,000	24,000	20,000
Ferrari	16,000	12,000	16,500
Pierce-Arrow	14,000	15,000	13,500
Cord	24,000	18,000	22,000

Party A divides the object into two parts. Party B chooses whicever part she wants.

applied in the Convention of the Law of the Sea.

Cake Division Procedures:

Lone Divider Method (by Hugo Steinhaus)

for 3 players: Bob, Carol, Ted
Bob divides the cake into 3 pieces: X, Y, Z
case 1:    Carol approves of  X
               Ted approves of  Y
               give Z to Bob
case 2:     Carol and Ted both approve of X, and both disapprove of Z
                merge X and Y, then XY is greater than 2/3
                let Carol and Ted do a divide and choose for 2 on XY
                give Z to Bob

• guarantees proportionality
• not necessarily envy-free

Last Diminisher Method (by Stefan Banach and Bronislaw Knaster)

for 4 players: Bob, Carol, Ted, Alice.
Bob cuts a piece he thinks is 1/4.
If Carol thinks it is > 1/4, she trims it and adds the trimmings to the remaining cake.
If Carol thinks it is <= 1/4, she passes it to Ted.
Ted proceeds as Carol did  and passes it to Alice.
Alice proceeds as Carol and Ted did and then hands it to the last person who trimmed it (who must think that it is exactly 1/4).
That person exits.

We are left with 3 people who think that at least 3/4 of the cake are left.
again say Carol gets to cut a piece she thinks is 1/4 and the other 2 get to trim/not trim.
etc.

now we are left with 2 people, who do a divide and choose.
 

• proportional
• not envy-free

The Selfridge-Conway Method

three players: Bob Carol, Ted
1    Bob cuts the cake into three pieces he considers to be of the same size.
2    Alice trims at most one piece to create a tie for largest, setting aside the trimmings.
3    Ted chooses one that he considers to be at least tied for largest.
4    Alice chooses from the remaining pieces. If she trimmed one of the remaining pieces in step 2, she must choose it now.
5    Bob receives the last piece.

This leaves the trimmings T
since Bob received an untrimmed piece, he won't envy anybody however T is allocated.
Say Ted received a trimmed piece.
Let Alice cut T into tree pieces she considers equal.
Choose a part of the trimmings in this order:    Ted, Bob Alice