Ais Abel's portion of the cake then 1-Ais Cain's portion. a(A)is Abel's proportion of the total by his valuation,
c(1-A)is Cain's proportion by his valuation. 0 <= a(A), c(1-A) <= 1 vis the maximum possible valuation such that there is
Awith both a(A)and c(1-A) >= vThe agreed accuracy is eWe want an algorithm which ensures an Ais chosen which ensures
a(A)+e >= vand c(1-A)+e >= vWe also need the following: Sum(i=1..k) of Ai = Nmeans that
kportions Aitaken together make up Ncomplete cakes.
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
Sum(i=1..q) Ai = p
Sum(i=1..q) a(Ai) = p
max(i=1..q) a(Ai) >= p/q
a(A) = max(i=1..q) a(Ai)
p/q + e/2 >= v >= a(A) >= p/q
Then the algorithm involves a simple adjustment of the bidding. We consider two bids to be equal if
w(A) = (a(A)+c(A))/2gives 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
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
Abel's bid + r = Cain's bid + (1-r)
The approximation can be made as exact as required by reducing
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
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.