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.

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

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.

Written by