Fair division dates back to the ancient

times and has found applications such as border settlement in international

disputes, greenhouse gas emissions reduction, allocation of mineral riches in

the ocean bed, inheritance, divorces, etc. In the era of the Internet, it appears

regularly in distributed resource allocation and cost sharing in communication

networks.

Nowadays, whether it is two kids sharing

a candy bar or a couple splitting assets during a divorce, there are times in

life where items of value need to be divided between two or more parties. While

some cases can be handled through mutual agreement or mediation, in others the

parties are adversarial or cannot reach a decision all feel is fair. In these

cases, fair division methods can be utilized.

A fair division method is a procedure

that can be followed that will result in a division of items in a way so that

each party feels they have received their fair share. This problem arises in various real-world settings: auctions, divorce

settlements, airport traffic management, or exploitation of Earth Observation Satellites. One of the

most common issues concerning fair division is the allocation of seats in a

council between several regions. It is called apportionment which is

a process that allocates seats to a district for election. There are

some Properties of an Apportionment Method

as follows.

·

Monotonicity property:

no state receives fewer seats than a state with less or same population

·

Quota property:

number of seats allocated to a state never differs from its quota by 1 or more

·

Population property:

no state should gain population and lose a seat while some other states lose

population and gains a seat.

For instance, in the House of Representatives of USA,

there are a fixed number of 435 seats allocated to all the states according to

their population. The quota of a state means (total number of seats) x

(state population) / (total population).

According to this calculation, a quota

is sometimes not an integer, so there was calculation method invented by

Alexander Hamilton in 1792 and known as Hamilton’s

method of Apportionment which rounds all quotas down to the nearest integer

and allocate the seats accordingly.

However this method only can satisfy the

monotonicity property and quota property, but not the population property.

Hamilton’s method is as follows.

Step 1: Calculate each state’s Standard

Quota

Standard Divisor = Total Population / Number

of Seats

Standard Quota = State Population / Standard

Divisor

Lower Quota – Round Down

Upper Quota – Round Up

Step 2: Allocate the Lower Quota (i.e.

Round Down)

Step 3: Give the surplus seats to the

state with the largest fractional parts until no more surplus seats

Hamilton’s method is not only to

calculate number of seats in a council but also can be applied on the daily

life issues such as the following example.

Example:

A mother wishes to distribute 11 pieces of candy among 3 children based on the

time each child spends studying:

Child

Bob

Peter

Ron

Time

54

243

703

Calculate Standard quotas Standard

Divisor = (54 + 243 + 703) /11 = 90.9

Child

Std Quota

Lower Quota

Bob

54/90.9 = 0.59

0

Peter

243/90.9 = 2.67

2

Ron

703/90.9 = 7.73

7

Allocate Lower Quota

Allocate Surplus

Total Allocated = 9

Total Surplus = 11 – 9 = 2

Ron gets one more, Peter gets one more

Total Allocation:

Bob = 0

Peter = 3

Ron = 8

As Balinski-Young

Impossibility Theorem stated that there is no apportionment method that

always satisfies the monotonicity property, the quota property and the

population property. However there are other methods that satisfy the

population property, such as Jefferson’s

Method of Apportionment. This method satisfies monotonicity and population

property. However it favours bigger states. In this method, the divisor is

introduced that represents the desired population size of a congressional

district. Choose an integer called a ‘divisor’. Allocate each state one seat

for its population divided by and then round

down to the nearest

integer.

Based on the same calculation method,

there are two variations, namely Adem’s

Method of Apportionment (which is same as Jefferson’s only except it uses

round up) and Webster’s Method of

Apportionment (which is same as Jefferson’s only except it uses round).

Besides the above apportionment issue,

there are some other daily life issues that we may use fair division theories

to resolve. For example, Proportional property is a common issue that we always

come across in our daily life. Its principle is when there are N parties

equally dividing something, that fair share would be 1/N. For instance,

if there were 4 parties, each would be entitled to a fair share of ¼ = 25% of

the whole. More specifically, they are entitled to a share that they value

as 25% of the whole. The following example will demonstrate the detail.

Example: Suppose that 4 friends have pooled money to buy a $12 pizza

that is half

pepperoni, half veggie.

Since they all put in the same amount of money, each person’s fair

share is $3, or a piece they

value as 25% of the pizza.

It is important to keep in

mind that each party might value portions of the whole differently.

For example, a vegetarian

would probably put zero value on the pepperoni half of the pizza.

Suppose that Steve likes

pepperoni twice as much as veggie. He would value the veggie half

as being worth $4 and the

pepperoni half as $8, twice as much. If the pizza was divided up

into 4 pepperoni slices and

4 veggie slices, he would value a pepperoni slice as being worth

$2, and a veggie slice as

being worth $1. A fair share for Steve would be one pepperoni slice

and one veggie slice, 1½

pepperoni slices, 3 veggie slices, or a variety of more complicated possibilities.

You will find that many examples and

exercises in this topic involve dividing food – dividing

candy, cutting cakes, sharing pizza,

etc. This may make this topic seem somewhat trivial, but

instead of cutting a cake, we might be

drawing borders dividing Germany after WWII.

Instead of splitting a bag of candy,

siblings might be dividing belongings from an inheritance. Mathematicians often

characterize very important and contentious issues in terms of simple items

like cake to separate any emotional influences from the mathematical method.

However the proportional property

allocation also causes another problem, namely envy. An envy-free division

is one in which no party would prefer another party’s share over their own. If

we take the above example of sharing the pizza, the vegetarian

will envy the others, because he got pepperoni half of the pizza which is no

value in his view while the others got more veggie.

There are more criteria of

fair division such as Equitability and Efficiency. Equitability means a division in which the

proportion of the whole each party receives, judged by their own valuation, is

the same. Efficiency means if there

is no other allocation possible that is at least as good for all parties and

strictly better for at least one party. There is a procedure to allocate the

items for the result of envy-free, equitable and efficient that is Adjusted Winner Procedure which can

allocate the items so that the two person / parties have the same total points

(equitability), as much as possible (efficient). The procedures are as follows.

Step 1: Each person is initially

allocated the items that they strictly value higher than the other person.

Next, tied items awarded one at a time, to person with fewest points. (If point

totals also tied, they are awarded to either person.)

Step 2: If the point totals are equal,

the procedure is done. Otherwise proceed to next step.

Step 3: The person with most points is

the initial winner. Calculate the ratio of initial winner points to loser’s

points and order the items from lowest ratio to highest (ratio always ? 1). It

is from lowest to highest, transfer items (or fractions of items) from initial

winner to loser until point totals equal.

The following example will demonstrate

the application of Adjusted Winner Procedure.

Example:

Mary and David share an inheritance from

their uncle and the points of each item are as follows.

Mary

Item

David

35

House

15

20

Investment

25

10

Piano

25

5

TV

15

25

Diamond

10

5

Car

10

David gets more points; we calculate

preference ratios for the things he won:

Investments = 25/20=1.25

Piano=25/10=2.5

TV=15/5=3

Car=10/5=2

We need to calculate Mary’s share of

investments. Let x be this share. Equitability tells us that we want 60 + 20 x

= 75 – 25 x

which gives us x = .

We wind up with Mary getting house,

Diamond and of investment portfolio. David gets of investment portfolio, TV, piano and car.

Each receives 66 points.

• Procedure is equitable (obvious)

• It’s efficient (proof is not

particularly easy)

• It’s envy-free. Why? Remember with 2

people proportional ?

envy-free. Suppose it’s not proportional. By equitable, this implies both get

less than . But this violates efficient (they could

switch bundles and both be better off). Thus, it’s proportional, and so

envy-free.

However the above Adjusted Winner

Procedure is only valid for two persons and some of the items to be separable

into parts. If the issue is with three or more people, it is impossible to

design a procedure that is guaranteed to satisfy all three fairness criteria:

equitability, envy-freeness and efficiency.

There is another dispute in division on

a lump sum of money which we may come across in daily life. If the dispute is

between two people, one reasonable way might be to divide in proportion to the

claim amount / individual cost. However, using the Nash Bargaining Model is another way of fair division. In this

calculation method, we need to define m, the values of m, D1 and D2.

The final result will be as follows.

In addition, the Talmud is a similar way to

resolve same kind of dispute. However the method of Nash Bargaining Model is

using a specific formula (where we need to know the values of m, D1

and D2) while Talmud needs bi-matrix method to define contested part.

There is a limitation of Talmud technique that when there are three claimers,

the situation is much more complicated as it is hard to find which part is

contested.

The most typical case in daily life is

the ownership of a flat. For instance Paul claims half of the flat while John

claims of the flat. So the contested part is .

In this case, Paul will get: .

John will get: .

For the same case that calculated by

Nash Bargaining Model, the result will be the same.

As a cooperative solution, m = 1.

Upon disagreement:

Paul will get at least since John will get at most . D1 =

John will get at least since Paul will get at most . D2 = .

=

In conclusion it

should be noted that a fair division method simply needs to guarantee that each

party will receive a share they view as fair. A basic fair division does not

need to be envy free; and also does not need to be equitable. Basically, a simple fair division doesn’t have to be

the best possible division – it just has to give each party their fair share.

As mentioned above, we might use fair division techniques to resolve some kinds

of contentious issues such as auctions, divorce

settlements, electronic spectrum and frequency

allocation. Therefore fair division is a powerful tool that helps us to resolve

many disputes in our daily life.