Fair Division 2

Francis Edward Su <su@math.hmc.edu> said that what I proposed is what Brams and Taylor would call "equitability"--- a solution in which each person gets the same fraction of the value of the cake in their own estimation. Also I'm looking for "efficiency"-- a division such that all parties cannot do better simultaneously.

That is correct. They won't all get exactly the optimum, the winner of the bidding below for instance will get slightly more and the other less but they'll get as close to it as will satisfy them.

I go into more detail here about what I meant by:

"For the two player case the solution is quite straightforward Both bid up the fraction till the difference is too small and one wins. This fraction V offered will be a tiny bit smaller than the real amount - this is the cut the winner of the bidding gets and why they bid up."

I describe an algorithm below to do the various bits so you can see how it all works.

I'll refer to the two people sharing a cake as Abel and Cain.

If A is Abel's portion of the cake then I-A is Cain's portion where I stands for the whole cake. The total valuation of the cake for each of them is 1. va(A) is Abel's valuation of his bit by his valuation, and vc(1-A) is Cain's valuation of his portion.

0 <= va(A), vc(Total-A) <= 1

vmax is the maximum possible valuation such that there is an A with both va(A) and vc(1-A) >= vmax

We want an algorithm which ensures an A is chosen so both va(A) >= vmax-ea and vc(1-A) >= vmax-ec where ea and ec are the amounts they will settle for less than the optimum.

Since they both have full knowledge of what the other wants they can each divide up the cake equitably and near full efficiently - it may be fractal which means full efficiency can't be attained anyway even if they were co-operative which they aren't. This is done by dividing the cake into tiny bits and then accumulating the ones with the highest va/vc till the equitable point is reached.

A similar trick works with any number of people, if the bits are put into a n-1 simplex using their valuations as barycentric co-ordinates then there is a point inside which gives an optimal partition by accumulating all the bits for a corner that have that corners valuation ratio higher - for three if (opta, optb, optc) is the point then A gets all those with va(x)/vb(x) > opta/optb and va/vc > opta/optc, with a proportion going either way for equality.

The bidding I was talking about is a way for them to come to an agreement. They have to state an ea and eb they will be satisfied with and split the cake into small regions that are numerous enough to satisfy them the following is okay

Then they bid up to vmax where each bid must be greater than ea/2 or eb/2 than the previous, winning the bidding gives a slightly better than optimum portion to the winner but only if he chooses a value < vmax. Thus they will try to beat the other and not exceed vmax.

The winner then has to put a value onto each little bit. Say Cain wins with vbid. He then puts an offer valuation onto each bit offer(x) close to va(x). The total of the offer valuations must add up to 1. Abel then may choose any bits he likes such that the total of the offer valuations <= vbid. Cain then takes the remaining portions.

Abel is assured of getting a valuation > vmax-ea since vbid will be greater than that - otherwise he could have bid again himself. All he has to do is pick the bits with the highest va(x)/offer(x) to give his portion A. With enough small bits there isn't a problem with having too big a valuation just at the break point. Taking the bits x with the highest va(x)/offer(x) and having va(Total)=offer(Total) automatically

ensures va(A) >= vbid when offer(A) = vbid.

Cain will arrange offer(x) close to va(x) but lower for the bits he wants Abel to choose. and higher for the bits he wants to keep himself. Something like v a(x)-e*(va(x)-vc(x)) for instance where e is tiny. If e could be made zero he could assure himself of giving Abel only value vbid < vmax and so ensuring himself > vmax. It has to be greater than zero though so the difference so Abel will choose as desired. Setting offer like this assures Cain that the remaining bits will have the highest values of vc(x)/va(x).

Francis Su also noted that for 3 people, there is a result by Brams/Taylor's that it is impossible to satisfy equitability, envy-freeness, and efficiency in every situation. This is certainly true here - envy freeness is not satisfied. I wish I'd discovered that result for myself, it is very nice - I just never asked myself the obvious question.