# Knaster: Fair Division

During World War II three Polish mathematicians began to think about the problem of fair division. These three were Hugo Steinhaus, Bronislaw Knaster and Stefan Banach, all outstanding mathematics well-known for many remarkable contributions to mathematics. In this article we describe Knaster's Fair Division Procedure by giving some examples. First let us illustrate the problem.

If parents with three children leave money to be divided equally between their children there is no problem - each gets one third of the money. If, however, parents leave the family home to be divided equally between their three children, then this cannot be divided into three. How should it be done so that each of the children thinks they have been treated fairly? There are many inheritance problems of this type, for example if three children inherit three items of differing values, how can a fair division be made?

Each of Ann, Bob and Carol, independently, simultaneously and anonymously, make a sealed bid for what they believe the car is worth. Suppose Ann bids £9,000, Bob bids £8,100 and Carol bids £7,200. Ann, who has made the largest bid, gets the car. She knows, however, that she only deserves 1/3 of the value of the car, i.e. £3000, so she puts £6,000 into a temporary bank. Bob, who thinks the car is worth £8,100, knows he only deserves 1/3 of that, namely £2,700. Carol, who thinks the car is worth £7,200, knows she only deserves 1/3 of that, namely £2,400. Bob gets £2,700 from the temporary bank, and Carol gets £2,400. £2,700 + £2,400 = £5,100 so £900 remains in the bank. Divide this in three, and give £300 to each of Ann, Bob and Carol.

The final result is that Ann has paid £5,700 for a car she believes is worth £9,000 so she has got a reduction of £3,300, £300 better than the 1/3 of what she considers to be its value. Bob does not get the car but he gets £3,000, £300 more than the 1/3 of what he considers to be its value. Carol does not get the car but she gets £2,700, £300 better than the 1/3 of what she considers to be its value. They should all be happy!

Of course, Ann may not have £5,700 to pay to her siblings, but lets not worry about this little practical difficulty!

Each of Ann, Bob, Carol and David, independently, simultaneously and anonymously, make a sealed bid for what they believe the car is worth. Suppose Ann bids £8,000, Bob bids £7,600, Carol bids £8,400 and David bids £7,200. Carol, who has made the largest bid, gets the car. She knows, however, that she only deserves 1/4 of the value of the car, i.e. £2,100, so she puts £6,300 into a temporary bank. Ann does not get the car but she thinks the car is worth £8,000 and gets 1/4 of this, namely £2,000. Bob does not get the car but but he thinks the car is worth £7,600 and gets 1/4 of this, namely £1,900. David does not get the car but thinks it is worth £7,200 gets 1/4 of this, namely £1,800. Ann, Bob and David get £2,000 + £1,900 + £1,800 = £5,700 from the bank. This leaves £600 in the temporary bank which is divided in 4, so £150 goes to each.

The final result is that Carol has paid £6,150 for a car she thinks is worth £8,400 so she gains £2,250, £150 better than the 1/4 of what she believes to be its value. Ann does not get the car but gets £2150, Bob does not get the car but gets £2,050 and David does not get the car but gets £1,950, each getting £150 more than the 1/4 of the value they believe the car to have. They should all be happy!

It is clear now how to generalise the Knaster Fair Division Procedure when there are $n$ people to get their fair share of one item. Each of the $n$ makes a bid, say person $i$ bids £ $b_{i}$. Then if person $k$ is the highest bidder, they put £ $(n-1)b_{k} /n$ into the temporary bank. Each remaining person, $b_{j}$ gets £ $b_{j} /n$ from the bank. Each person then receives what is left in the bank divided by $n$.

What happens if there is more than one item to be shared out fairly to several people? Let us give an example which will illustrate how the Knaster Fair Division Procedure works in that case.

Each of Ann, Bob, Carol and David, independently, simultaneously and anonymously, make a sealed bid for what they believe the house, the boat, and the car is worth.

Suppose Ann bids £240,000 for the house, £60,000 for the boat, and £8,000 for the car.

Suppose Bob bids £200,000 for the house, £62,000 for the boat, and £7,600 for the car.

Suppose Carol bids £220,000 for the house, £58,000 for the boat, and £8,400 for the car.

Suppose David bids £230,000 for the house, £61,000 for the boat, and £8,200 for the car.

Ann has bid a total of £240,000 + £60,000 + £8,000 = £308,000. She expects 1/4 of this, namely £77,000.

Bob has bid a total of £200,000 + £62,000 + £7,600 = £269,600. He expects 1/4 of this, namely £67,400.

Carol has bid a total of £220,000 + £58,000 + £8,400 = £286,400. She expects 1/4 of this, namely £71,600.

David has bid a total of £230,000 + £61,000 + £8,200 = £299,200. He expects 1/4 of this, namely £74,800.

Ann gets the house and has to pay £240,000 - £77,000 = £163,000 to the bank.

Bob gets the boat and expects to get £67,400 - £62,000 - £5,400 from the bank.

Carol gets the car and expects to get £71,600 - £8,400 = £63,200 from the bank.

David gets none of the three items and expects to get £74,800 from the bank.

£5,400 + £63,200 + £74,800 = £143,400 is to come out of the bank, so £163,000 - £143,400 = £19,600 is left. Divide this by 4 to get £4,900 which goes to each of Ann, Bob, Carol and David.

Ann gets the house for £158,100. Bob gets the boat and £10,300, Carol gets the car and £68,100, David gets none of the three items but gets £79,700 in cash. All should be happy since each is £4,900 better off than the 1/4 of what they believe to be the total value of the three items.

Qe have given the Knaster Fair Division Procedure assuming that each person who is inheriting plays fair, that is bids what they genuinely believe each item is worth. Now, sadly, we know from experience that not everyone plays fair in such circumstances. If the people who are to inherit make a game out of the procedure and, rather than bid what they believe to be the value of the item, they bid what they believe will give them the best result, then we do not attempt to examine the possible consequences.

If parents with three children leave money to be divided equally between their children there is no problem - each gets one third of the money. If, however, parents leave the family home to be divided equally between their three children, then this cannot be divided into three. How should it be done so that each of the children thinks they have been treated fairly? There are many inheritance problems of this type, for example if three children inherit three items of differing values, how can a fair division be made?

**Example 1.**Suppose that three children, Ann, Bob and Carol, inherit a car from their parents. How do they decide who gets the car and how is it done so that all feel that they have been fairly treated? The Knaster Fair Division Procedure goes as follows.Each of Ann, Bob and Carol, independently, simultaneously and anonymously, make a sealed bid for what they believe the car is worth. Suppose Ann bids £9,000, Bob bids £8,100 and Carol bids £7,200. Ann, who has made the largest bid, gets the car. She knows, however, that she only deserves 1/3 of the value of the car, i.e. £3000, so she puts £6,000 into a temporary bank. Bob, who thinks the car is worth £8,100, knows he only deserves 1/3 of that, namely £2,700. Carol, who thinks the car is worth £7,200, knows she only deserves 1/3 of that, namely £2,400. Bob gets £2,700 from the temporary bank, and Carol gets £2,400. £2,700 + £2,400 = £5,100 so £900 remains in the bank. Divide this in three, and give £300 to each of Ann, Bob and Carol.

The final result is that Ann has paid £5,700 for a car she believes is worth £9,000 so she has got a reduction of £3,300, £300 better than the 1/3 of what she considers to be its value. Bob does not get the car but he gets £3,000, £300 more than the 1/3 of what he considers to be its value. Carol does not get the car but she gets £2,700, £300 better than the 1/3 of what she considers to be its value. They should all be happy!

Of course, Ann may not have £5,700 to pay to her siblings, but lets not worry about this little practical difficulty!

**Example 2.**Suppose that four children, Ann, Bob, Carol and David, inherit a house from their parents. How do they decide who gets the house and how is it done so that all feel that they have been fairly treated? The Knaster Fair Division Procedure goes as follows.Each of Ann, Bob, Carol and David, independently, simultaneously and anonymously, make a sealed bid for what they believe the car is worth. Suppose Ann bids £8,000, Bob bids £7,600, Carol bids £8,400 and David bids £7,200. Carol, who has made the largest bid, gets the car. She knows, however, that she only deserves 1/4 of the value of the car, i.e. £2,100, so she puts £6,300 into a temporary bank. Ann does not get the car but she thinks the car is worth £8,000 and gets 1/4 of this, namely £2,000. Bob does not get the car but but he thinks the car is worth £7,600 and gets 1/4 of this, namely £1,900. David does not get the car but thinks it is worth £7,200 gets 1/4 of this, namely £1,800. Ann, Bob and David get £2,000 + £1,900 + £1,800 = £5,700 from the bank. This leaves £600 in the temporary bank which is divided in 4, so £150 goes to each.

The final result is that Carol has paid £6,150 for a car she thinks is worth £8,400 so she gains £2,250, £150 better than the 1/4 of what she believes to be its value. Ann does not get the car but gets £2150, Bob does not get the car but gets £2,050 and David does not get the car but gets £1,950, each getting £150 more than the 1/4 of the value they believe the car to have. They should all be happy!

It is clear now how to generalise the Knaster Fair Division Procedure when there are $n$ people to get their fair share of one item. Each of the $n$ makes a bid, say person $i$ bids £ $b_{i}$. Then if person $k$ is the highest bidder, they put £ $(n-1)b_{k} /n$ into the temporary bank. Each remaining person, $b_{j}$ gets £ $b_{j} /n$ from the bank. Each person then receives what is left in the bank divided by $n$.

What happens if there is more than one item to be shared out fairly to several people? Let us give an example which will illustrate how the Knaster Fair Division Procedure works in that case.

**Example 3.**Suppose that four children, Ann, Bob, Carol and David, inherit a house, a boat and a car from their parents. How do they decide who gets the house, who gets the boat, who gets the car and how is it done so that all feel that they have been fairly treated? The Knaster Fair Division Procedure goes as follows.Each of Ann, Bob, Carol and David, independently, simultaneously and anonymously, make a sealed bid for what they believe the house, the boat, and the car is worth.

Suppose Ann bids £240,000 for the house, £60,000 for the boat, and £8,000 for the car.

Suppose Bob bids £200,000 for the house, £62,000 for the boat, and £7,600 for the car.

Suppose Carol bids £220,000 for the house, £58,000 for the boat, and £8,400 for the car.

Suppose David bids £230,000 for the house, £61,000 for the boat, and £8,200 for the car.

Ann has bid a total of £240,000 + £60,000 + £8,000 = £308,000. She expects 1/4 of this, namely £77,000.

Bob has bid a total of £200,000 + £62,000 + £7,600 = £269,600. He expects 1/4 of this, namely £67,400.

Carol has bid a total of £220,000 + £58,000 + £8,400 = £286,400. She expects 1/4 of this, namely £71,600.

David has bid a total of £230,000 + £61,000 + £8,200 = £299,200. He expects 1/4 of this, namely £74,800.

Ann gets the house and has to pay £240,000 - £77,000 = £163,000 to the bank.

Bob gets the boat and expects to get £67,400 - £62,000 - £5,400 from the bank.

Carol gets the car and expects to get £71,600 - £8,400 = £63,200 from the bank.

David gets none of the three items and expects to get £74,800 from the bank.

£5,400 + £63,200 + £74,800 = £143,400 is to come out of the bank, so £163,000 - £143,400 = £19,600 is left. Divide this by 4 to get £4,900 which goes to each of Ann, Bob, Carol and David.

Ann gets the house for £158,100. Bob gets the boat and £10,300, Carol gets the car and £68,100, David gets none of the three items but gets £79,700 in cash. All should be happy since each is £4,900 better off than the 1/4 of what they believe to be the total value of the three items.

Qe have given the Knaster Fair Division Procedure assuming that each person who is inheriting plays fair, that is bids what they genuinely believe each item is worth. Now, sadly, we know from experience that not everyone plays fair in such circumstances. If the people who are to inherit make a game out of the procedure and, rather than bid what they believe to be the value of the item, they bid what they believe will give them the best result, then we do not attempt to examine the possible consequences.

Last Updated April 2020