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:-
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 Ai = N means that
all the k portions Ai taken together make up N complete cakes.
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.
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) Ai = pAnd 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(Ai) = p
max(i=1..q) a(Ai) >= p/q
Thus Abel will choose the A such that:
a(A) = max(i=1..q) a(Ai)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.
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 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.
w(A) = (a(A)+c(A))/2 gives the total valuation for portion AThen the algorithm involves a simple adjustment of the bidding. We consider two bids to be equal if
r = fraction of the total valuation Abel is to get
1-r = fraction of total valuation Cain is to get
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/2The 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().
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.