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 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
A_{p} = Σ_{i}a_{ip} / N, |
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
Σ_{p}D_{p} | =Σ_{p}(B_{p} - A_{p}) | |
=Σ_{p}B_{p} - Σ_{p}A_{p}. |
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
Σ_{p}B_{p} = Σ_{i}h_{i}, |
so that we may continue
Σ_{p}D_{p} | =Σ_{p}B_{p} - Σ_{p}A_{p} | |
=Σ_{i}h_{i} - Σ_{p}Σ_{i}a_{ip} / N | ||
=Σ_{i} (h_{i} - Σ_{p}a_{ip} / N) | ||
≥ 0, |
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.
|Contact| |Front page| |Contents| |Up|
Copyright © 1996-2018 Alexander Bogomolny
63587491 |