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 vixi − 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 = ∅
Is this a single-parameter environment? Explain fully.
(iv) Return W (and give the bidders in W their desired items).
Is this allocation rule monotone (bidder smaller leads to a smaller cost)? If so, find a
Does the greedy allocation rule maximize social welfare? Prove the claim or construct an explicit counterexample.