16 Nonidential Objects
Problem 16.1 (Low revenue) Consider the problem of allocating a set of two objects
in K=fa; bgto three buyers with values as follows:
a b ab
x10 0 10 + “
x210 10 10
x210 10 10
where 0” < 1:
a. Find an e¢ cient allocation and the corresponding payments in the VCG mech-
anism.
b. What is the total revenue accruing to the seller?
Solution. Part a. It would be e¢ cient to give ato buyer 2 and bto buyer 3. With
buyer 2, the other two buyers have total welfare of W2(x) = 10. Without buyer 2
Part b. The seller collects 2“in revenue.
Problem 16.2 (Complements) Consider the problem of allocating a set of four ob-
jects in K=fa1; a2; b1; b2gto …ve buyers. Buyer 1has use only for objects a1and b1;
buyers 2and 3have use only for objects a2and b2; buyer 4has use only for b1and
b2; and buyer 5 has use only for objects a1and a2. Speci…cally, the values attached
by the buyers to these bundles are
x1(a1b1) = 10
x2(a2b2) = 20
x3(a2b2) = 25
x4(b1b2) = 10
x5(a1a2) = 10
All other combinations (or packages) are valued at zero.
a. Find an e¢ cient allocation and the corresponding payments in the VCG mech-
anism.
Solution. It is e¢ cient to give a1b1to buyer 1 and a2b2to buyer 3. With buyer 1,
the total welfare of the other buyers is W1(x) = 25. If buyer 1 reported a value
vector of zeros, it would be e¢ cient to give a2b2to buyer 3 and a1and b1to no one,
60
Problem 16.3 Show that the conditions (16.6) and (16.7) are equivalent.
Solution. (16:6))(16:7).Suppose (16.6) holds and take two sets S; T K.
Because Kis …nite, we can list TnS=a1; :::; an. De…ne T0T; S0T\Sand
Tm=Tm1[ famgand Sm=Sm1[ famgfor m= 1; :::; n. Applying (16.6) n
times to SmTm63 am+1 gives the following sequence of inequalities:
Adding these inequalities up gives
And substituting Sn= (T\S)[(TnS) = S,S0=T\S,Tn=T[(TnS) = T[S
and T0=Tgives
which can be rearranged to make (16.7).
(16:7))(16:6).Suppose (16.7) holds and take a2K; a =2T; and ST. De…ne
S0=S[ fAg. Applying (16.7) to the sets S0; T gives
which can be rearranged as (16.6).
61