None
Explain how to implement a welfare-maximizing DSIC mecha-
nism by invoking this subroutine n + 1 times, where n is the
number of participants.
Conclude that mechanisms that are ideal in the sense of Theo-
rem 2.4 exist for precisely the families of single-parameter envi-
ronments in which the welfare-maximization problem (given b
as input, compute (4.2)) can be solved in polynomial time.
Prove that the greedy algorithm in the proof of Theo-
rem 4.2 always computes an optimal fractional knapsack solution.
Exercise 4.5 Prove that the three-step greedy knapsack auction al-
location rule in Section 4.2.2 is monotone. Does it remain monotone
with the two optimizations discussed in the footnotes?
Consider a variant of a knapsack auction in which we
have two knapsacks, with known capacities W1 and W2. Feasible
sets of this single-parameter environment now correspond to subsets
S of bidders that can be partitioned into sets S1 and S2 satisfying∑
i∈Sj wi ≤ Wj for j = 1, 2.
Consider the allocation rule that first uses the single-knapsack
greedy allocation rule of Section 4.2.2 to pack the first knapsack,
and then uses it again on the remaining bidders to pack the second
knapsack. Does this algorithm define a monotone allocation rule?
Give either a proof of this fact or an explicit counterexample.
(H) The revelation principle (Theorem 4.3) states that
(direct-revelation) DSIC mechanisms can simulate all other mecha-
nisms with dominant-strategy equilibria. Critique the revelation prin-
ciple from a practical perspective. Name a specific situation where
you might prefer a non-direct-revelation mechanism with a dominant-
strategy equilibrium to the corresponding DSIC mechanism, and ex-
plain your reasoning.
Core terms of use, available at https://www.cambridge.org/core/terms. https://doi.org/10.1017/CBO9781316779309.005
Downloaded from https://www.cambridge.org/core. Access
