Fair Division: Method of Sealed Bids II
The applet below helps practice and gain insight into one of the fair division methods, the Method of Sealed Bids. The instructions for using the applet are available on a separate page and can also be read under the first tab directly in the applet.
|What if applet does not run?|
(This applet was created to accompany Excursions in Modern Mathematics, Seventh Edition, by Peter Tannenbaum © Pearson Education. Reproduced with permission.)
An earlier version of the applet and the Description of the method are available at https://www.cut-the-knot.org/Curriculum/SocialScience/SealedBids.shtml. Here I would like to clarify the reason why the method of sealed bids works. An important question is this: after the announcement of the high bids and the winners of individual items, the winnings of each player are compared to his or her estimate of the fair share of the goods. Some of the players - who received more than their fair share - are found to owe the estate, others - who received less than the fair share or nothing at all - to be owed by the estate. It is always the fact that the difference of the total amount owed to the estate and the total of players' debts is not negative. It is 0 if and only if all players bids are equal for any individual item.
This fact follows from the observation that also underlies the pigeonhole principle, viz., the maximum of a set of numbers is never less than their average.
Let aip stand for the bid of the pth for the Ith item. The pth player assessment of his or her fair share is given by the expression
|Ap = Σiaip / N,|
where N is the number of players and the sum is taken over the entire pth column. Let Bp be the sum of player pth valuations of the goods for which he (she) was the highest bidder. The amount Dp = Bp - Ap may be positive or not. If it is, the pth receives more than the expected fair share estimate and must pay this amount to the estate. If it's negative, the player receives less than the fair share and ought to be compensated by the estate for the value of the deficit. What we are looking into is the sum
|ΣpDp||=Σp(Bp - Ap)|
|=ΣpBp - ΣpAp.|
Observe that the first sum is the sum of the highest bids for every item (which is somehow has been distributed among the players). If hi is the highest bid for the Ith item then
|ΣpBp = Σihi,|
so that we may continue
|ΣpDp||=ΣpBp - ΣpAp|
|=Σihi - ΣpΣiaip / N|
|=Σi (hi - Σpaip / N)|
because in the parentheses the difference is between the maximum and the average values in the Ith row of the table, the bids for the Ith item.
Copyright © 1996-2018 Alexander Bogomolny