You can earn extra credit by typing up your solutions in LaTeX. I suggest you use Overleaf as a LaTeX editor.

• Exercise adapted from Problem 4.3:

Consider a set M of distinct items.  There are n bidders, and each bidder i has a publicly known subset Ti  ⊆ M of items that it wants, and a private valuation vi  for getting them. If bidder i is awarded a set Si of items at a total price of p, then her utility is vi xi − p, where xi is 1 if Si  ⊇ Ti and 0 otherwise. Since each item can only be awarded to one bidder, a subset W of bidders can all receive their desired subsets simultaneously if and only if Ti ∩ Tj  = ∅ for each distinct i,j ∈ W.

(a) Is this a single-parameter environment? Explain fully.

(b) The allocation rule that maximizes social welfare is well known to be NP hard (as the

Knapsack auction was) and so we make a greedy allocation rule.  Given a reported truthful bid bi from each player i, here is a greedy allocation rule:

Is this allocation rule monotone (bidder smaller leads to a smaller cost)? If so, find a DSIC auction based on this allocation rule. Otherwise, provide an explicit counterex- ample.

(c) Does the greedy allocation rule maximize social welfare? Prove the claim or construct an explicit counterexample.

• Exercise 6.4

• Exercise 7.4

• Exercise 9.5