I describe here an algorithm which will ensure optimal fair division within any desired accuracy where both people have perfect knowledge of what the other wants. A small extension of the algorithm will ensure fair division in a given ratio of the average of each person's valuation.

Consider for simplicity a discrete case where Cain and Abel have to divide up 5 apples and 5 oranges. Suppose Cain values each apple the same as three oranges, and Abel values each orange the same as three apples. Then the optimal division is obviously 5 apples for Cain and 5 oranges for Abel.

However with the usual minimax conditions Cain would probably split them as 3 apples and 1 orange in one group and 2 apples and 4 oranges in the other so each group has the same value. Abel would then choose the 2 apples and 4 oranges. Thus in this case the chooser gets a far higher percentage of his valuation of the total value.

If Cain knows exactly what Abel wants though he can put 5 apples and one orange into one group and 4 oranges into the other. Abel would have to choose the 4 oranges and Cain comes out the clear winner.

Each person knows their own and the other person's valuation exactly and wishes to maximize the value of the portion they get. (This is the big difference from the usual fair division assumption that they don't know each others valuation and wish to maximize the minimum they could possibly get.)

The valuation of each part of the 'cake' can be given by a continuous measure for each person. A portion can be divided as finely as required in any ratio without the total value being changed.

The algorithm below only needs to be exact to within some fraction which has to be agreed beforehand - it need not be absolutely accurate.

A capital letter stands for a portion of the whole cake and a small letter for the measure on that portion. In short:-

Ifis Abel's portion of the cake thenAis Cain's portion.1-A

is Abel's proportion of the total by his valuation,a(A)

andis Cain's proportion by his valuation.c(1-A)

0 <= a(A), c(1-A) <= 1

is the maximum possible valuation such that there isv

anwith bothAanda(A)c(1-A) >= vThe agreed accuracy is

eWe want an algorithm which ensures an

is chosen which ensuresA

bothanda(A)+e >= vc(1-A)+e >= vWe also need the following:

means thatSum(i=1..k) of A_{i}= N

all theportionsktaken together make upA_{i}complete cakes.N

Cain and Abel then take turns in bidding to be the cutter. Their bids approximate the valuation of the portion of the cake they will offer the other.

The one to bid the highest fraction wins. Each bid
must be at least** e/2 **more than the last, this
ensures the bidding must eventually end.

Suppose the fraction is** p/q**. Then the winner,
suppose it is Cain, must offer

The chooser, Abel, must then choose one of the offered portions. Cain gets the remainder of the cake.

The cutter has an advantage therefore the bidding will force the fraction
bid up to within** e/2 **of the maximum it can be.

Supposing Cain does the cutting then he will try and ensure Abel chooses a portion such that the remainder of the cake has as high a value to himself, Cain, as possible. This necessarily means reducing as far as possible the value of the most desirable portion Abel can choose. The best way this can be accomplished by ensuring all the other portions offered have a very slightly lower value

So we can deduce:

And in fact there will only be a single maximum for the one Cain wants Abel to choose and the minimum will be only very slightly smaller.Sum(i=1..q) A_{i}= p

Sum(i=1..q) a(A_{i}) = p

max(i=1..q) a(A_{i}) >= p/q

Thus Abel will choose the** A **such that:

The bida(A) = max(i=1..q) a(A_{i})

p/q + e/2 >= v >= a(A) >= p/q

So we see Abel gets within** e/2 **of the optimum. Cain
if he is lucky could get more than

Suppose that:-

Then the algorithm involves a simple adjustment of the bidding. We consider two bids to be equal ifgives the total valuation for portionw(A) = (a(A)+c(A))/2A

fraction of the total valuation Abel is to getr =

fraction of total valuation Cain is to get1-r =

The bidding continues as before but with these adjusted values determining who wins the bidding. The one with the higher entitlement can win with a lower bid.Abel's bid + r = Cain's bid + (1-r)

If as before Cain wins with a bid of** p/q **then with
the previous reasoning:

The approximation can be made as exact as required by reducingp/q <= a(A) <= p/q + e/2

p/q + (1-r) <= B(1-A) + r

a(A) + (1-r) approx= b(1-A) + r

b(1-A) = 1 - b(A)

a(A) + b(A) approx= 1 + r - (1-r)

a(A) + b(A) approx= 2r

u(A) approx= r

u(1-A) approx= 1-r

It would be nice to think we lived in a world that was sufficiently rational for such an approach.However the algorithm as it stands unsuitable for direct use as a protocol in such cases as it is very unstable in the face of small errors in judgement. The best hope I see of any application in this area is the insight it may provide in designing a computer assist for negotiations.

On the theoretical side I have tried to solve the problem of three people where the minimum valuation of the three is to be maximized, but without any success, I've descended to the stage where I'm wondering if it's impossible - but then again I originally thought it wasn't possible to do what the algorithm above does.

[RW] | Cake-Cutting Algorithms; Be Fair If You Can Jack Robertson, William Webb. 1988 ISBN 1-56881-076-8 |

[IS1] | Your Half's Bigger than My Half. Ian Stewart. Scientific American. Dec 1998. |

[IS2] | Division Without Envy. Ian Stewart. Scientific American. Jan 1999. |