Fair division dates back to the ancienttimes and has found applications such as border settlement in internationaldisputes, greenhouse gas emissions reduction, allocation of mineral riches inthe ocean bed, inheritance, divorces, etc. In the era of the Internet, it appearsregularly in distributed resource allocation and cost sharing in communicationnetworks.Nowadays, whether it is two kids sharinga candy bar or a couple splitting assets during a divorce, there are times inlife where items of value need to be divided between two or more parties. Whilesome cases can be handled through mutual agreement or mediation, in others theparties are adversarial or cannot reach a decision all feel is fair. In thesecases, fair division methods can be utilized. A fair division method is a procedurethat can be followed that will result in a division of items in a way so thateach party feels they have received their fair share. This problem arises in various real-world settings: auctions, divorcesettlements, airport traffic management, or exploitation of Earth Observation Satellites.
One of themost common issues concerning fair division is the allocation of seats in acouncil between several regions. It is called apportionment which isa process that allocates seats to a district for election. There aresome Properties of an Apportionment Methodas 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 losepopulation 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 totheir population. The quota of a state means (total number of seats) x(state population) / (total population). According to this calculation, a quotais sometimes not an integer, so there was calculation method invented byAlexander Hamilton in 1792 and known as Hamilton’smethod of Apportionment which rounds all quotas down to the nearest integerand allocate the seats accordingly. However this method only can satisfy themonotonicity property and quota property, but not the population property.
Hamilton’s method is as follows.Step 1: Calculate each state’s StandardQuota Standard Divisor = Total Population / Numberof Seats Standard Quota = State Population / StandardDivisor 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 thestate with the largest fractional parts until no more surplus seatsHamilton’s method is not only tocalculate number of seats in a council but also can be applied on the dailylife issues such as the following example.Example:A mother wishes to distribute 11 pieces of candy among 3 children based on thetime each child spends studying: Child Bob Peter Ron Time 54 243 703 Calculate Standard quotas StandardDivisor = (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-YoungImpossibility Theorem stated that there is no apportionment method thatalways satisfies the monotonicity property, the quota property and thepopulation property. However there are other methods that satisfy thepopulation property, such as Jefferson’sMethod of Apportionment. This method satisfies monotonicity and populationproperty. However it favours bigger states.
In this method, the divisor isintroduced that represents the desired population size of a congressionaldistrict. Choose an integer called a ‘divisor’. Allocate each state one seatfor its population divided by and then rounddown to the nearestinteger.Based on the same calculation method,there are two variations, namely Adem’sMethod of Apportionment (which is same as Jefferson’s only except it usesround up) and Webster’s Method ofApportionment (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 theoriesto resolve. For example, Proportional property is a common issue that we alwayscome across in our daily life. Its principle is when there are N partiesequally 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% ofthe whole. More specifically, they are entitled to a share that they valueas 25% of the whole. The following example will demonstrate the detail. Example: Suppose that 4 friends have pooled money to buy a $12 pizzathat is halfpepperoni, half veggie.Since they all put in the same amount of money, each person’s fairshare is $3, or a piece theyvalue as 25% of the pizza.It is important to keep inmind that each party might value portions of the whole differently.For example, a vegetarianwould probably put zero value on the pepperoni half of the pizza.Suppose that Steve likespepperoni twice as much as veggie.
He would value the veggie halfas being worth $4 and thepepperoni half as $8, twice as much. If the pizza was divided upinto 4 pepperoni slices and4 veggie slices, he would value a pepperoni slice as being worth$2, and a veggie slice asbeing worth $1. A fair share for Steve would be one pepperoni sliceand one veggie slice, 1½pepperoni slices, 3 veggie slices, or a variety of more complicated possibilities. You will find that many examples andexercises in this topic involve dividing food – dividingcandy, cutting cakes, sharing pizza,etc. This may make this topic seem somewhat trivial, butinstead of cutting a cake, we might bedrawing borders dividing Germany after WWII.Instead of splitting a bag of candy,siblings might be dividing belongings from an inheritance. Mathematicians oftencharacterize very important and contentious issues in terms of simple itemslike cake to separate any emotional influences from the mathematical method.
However the proportional propertyallocation also causes another problem, namely envy. An envy-free divisionis one in which no party would prefer another party’s share over their own. Ifwe take the above example of sharing the pizza, the vegetarianwill envy the others, because he got pepperoni half of the pizza which is novalue in his view while the others got more veggie. There are more criteria offair division such as Equitability and Efficiency. Equitability means a division in which theproportion of the whole each party receives, judged by their own valuation, isthe same. Efficiency means if thereis no other allocation possible that is at least as good for all parties andstrictly better for at least one party. There is a procedure to allocate theitems for the result of envy-free, equitable and efficient that is Adjusted Winner Procedure which canallocate 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 initiallyallocated 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 pointtotals 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 isthe initial winner. Calculate the ratio of initial winner points to loser’spoints and order the items from lowest ratio to highest (ratio always ? 1).
Itis from lowest to highest, transfer items (or fractions of items) from initialwinner to loser until point totals equal. The following example will demonstratethe application of Adjusted Winner Procedure.Example: Mary and David share an inheritance fromtheir 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 calculatepreference 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 ofinvestments. Let x be this share. Equitability tells us that we want 60 + 20 x= 75 – 25 xwhich 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 notparticularly easy) • It’s envy-free. Why? Remember with 2people proportional ?envy-free. Suppose it’s not proportional. By equitable, this implies both getless than . But this violates efficient (they couldswitch bundles and both be better off).
Thus, it’s proportional, and soenvy-free. However the above Adjusted WinnerProcedure is only valid for two persons and some of the items to be separableinto parts. If the issue is with three or more people, it is impossible todesign a procedure that is guaranteed to satisfy all three fairness criteria:equitability, envy-freeness and efficiency.
There is another dispute in division ona lump sum of money which we may come across in daily life. If the dispute isbetween two people, one reasonable way might be to divide in proportion to theclaim amount / individual cost. However, using the Nash Bargaining Model is another way of fair division.
In thiscalculation 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 toresolve same kind of dispute. However the method of Nash Bargaining Model isusing a specific formula (where we need to know the values of m, D1and 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 iscontested. The most typical case in daily life isthe ownership of a flat.
For instance Paul claims half of the flat while Johnclaims of the flat. So the contested part is . In this case, Paul will get: .John will get: . For the same case that calculated byNash 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 itshould be noted that a fair division method simply needs to guarantee that eachparty will receive a share they view as fair. A basic fair division does notneed to be envy free; and also does not need to be equitable. Basically, a simple fair division doesn’t have to bethe 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 kindsof contentious issues such as auctions, divorcesettlements, electronic spectrum and frequencyallocation.
Therefore fair division is a powerful tool that helps us to resolvemany disputes in our daily life.