Cake Cutting with Full Knowledge

8 May 1999

Introduction

The rule 'one cuts, the other chooses' is the well known method to divide something, the 'cake', fairly between two people. This work was inspired by the book ref [RW] which surveys the field of algorithms for fair division. The very first exercise in the book is to decide whether you would prefer to be the cutter or the chooser. With the standard assumptions the right answer is the chooser. However in actual practice with siblings who know each other well the cutter has a large advantage.

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.

Example of Cut and Choose

To signify that they know each other so well, and because I haven't been able to extend the theory to three people, I shall call the two doing the division Cain and Abel instead of the usual Tom, Dick and Harry.

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.

Assumptions

The notation used and the assumptions made are detailed here:

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:-

If A is Abel's portion of the cake then 1-A is Cain's portion.
a(A) is Abel's proportion of the total by his valuation,
and c(1-A) is Cain's proportion by his valuation.
0 <= a(A), c(1-A) <= 1
v is the maximum possible valuation such that there is
an A with both a(A) and c(1-A) >= v
The agreed accuracy is e
We want an algorithm which ensures an A is chosen which ensures
both a(A)+e >= v and c(1-A)+e >= v
We also need the following:
Sum(i=1..k) of A_i = N means that
all the k portions A_i taken together make up N complete cakes.

The Algorithm

Firstly Cain and Abel choose the small fraction e that they are willing to stop arguing over by each saying a value and the lower being used.

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 q portions of the cake which cover every part p times in total. For example if he said 2/3 then he must offer 3 different pieces which if they could be put together would make 2 whole cakes.

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

Why it Works

Firstly if the algorithm was exact then both Cain and Abel's portions would have the same valuation for each. This is because if for instance Abel's valued his portion as v and Cain valued his higher then there must be some portion that Cain has which also has value to Abel. Since the portions can be divided in any ratio we could trim off a part of Cain's portion that has value for Abel without reducing Cain's total portion to value v, whilst at the same time increasing Abel's valuation. Therefore assuming the valuations can be different gives a contradiction.

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:

Sum(i=1..q) A_i = p Sum(i=1..q) a(A_i) = p max(i=1..q) a(A_i) >= p/q

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.

Thus Abel will choose the A such that:

a(A) = max(i=1..q) a(A_i) p/q + e/2 >= v >= a(A) >= p/q

The bid p/q must be less than v otherwise Cain would not be able to give himself more than Abel, and it can't be much less otherwise Abel would be able to outbid and get himself a better portion.

So we see Abel gets within e/2 of the optimum. Cain if he is lucky could get more than v+e but we were only trying to optimize the minimum, not do down the maximum. If Abel was going to be unhappy about this he could always have chosen an e that reduced the possible difference as much as desired.

Unequal Division

The algorithm can be extended to where the two portions are to have overall values in a certain ratio, e.g. 60% to Cain and 40% to Abel. This is only where the overall valuation is given by the average (or sum but that then doesn't sum to 1) of the individual valuations.

Suppose that:-

w(A) = (a(A)+c(A))/2 gives the total valuation for portion A
r = fraction of the total valuation Abel is to get
1-r = fraction of total valuation Cain is to get

Then the algorithm involves a simple adjustment of the bidding. We consider two bids to be equal if

Abel's bid + r = Cain's bid + (1-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.

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

p/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

The approximation can be made as exact as required by reducing e but the accuracy of the approximation depends on the particular measures a() and b().

Discussion

The assumptions in this algorithm are quite close to the conditions that hold for many important real world conflict resolution problems, for example divorces and civil wars. Ref [IS1] says about fair division applied to problems like these:

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.

References

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