Chapter 3, Problem 71E

Suppose that N players bid on M items using the method of sealed bids. Let T denote the table with M rows (one for each item) and N columns (one for each player) containing all the players' bids (i.e., the entry in column j, row k represents player j's bid for item k). Let $c_1,c_2,\dots ,c_N$ denote, respectively, the sum of the entries in column 1, column 2,…, column N of T, and let $r_1,r_2,\dots ,r_M$ denote, respectively, the sum of the entries in row 1, row 2,…, row M of T. Let $w_1,w_2,\dots ,w_M$ denote the winning bids for items $1,2,\dots ,M$, respectively (i.e., $w_1$ is the largest entry in row 1 of T, $w_2$ is the largest entry in row 2, etc.). Let S denote the surplus money left after the first settlement.

a. Show that

$S=\left(w_1+w_2+\cdots +w_M\right)-\left(c_1+c_2+\cdots +c_N\right)/N$.

b. Using (a), show that

$S=\left(w_1-\frac{r_1}{N}\right)+\left(w_2-\frac{r_2}{N}\right)+\cdots +\left(w_M-\frac{r_M}{N}\right)$.

c. Using (b), show that $S\ge 0$.

d. Describe the conditions under which $S=0$