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.

(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 http://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 a_ip stand for the bid of the p^th for the i^th item. The p^th player assessment of his or her fair share is given by the expression

where N is the number of players and the sum is taken over the entire p^th column. Let B_p be the sum of player p^th valuations of the goods for which he (she) was the highest bidder. The amount D_p = B_p - A_p may be positive or not. If it is, the p^th 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

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 h_i is the highest bid for the i^th item then

so that we may continue

because in the parentheses the difference is between the maximum and the average values in the i^th row of the table, the bids for the i^th item.

Copyright © 1996-2009 Alexander Bogomolny