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

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 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 = ∅ 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 and so we make a greedy allocation rule. Given a reported truthful bid bi from each player i, here is a greedy allocation rule:
(i) Initialize the set of winners W = ∅, and the set of remaining items X = M.
(ii) Sort and re-index the bidders so that b1 ≥ b2 ≥ · · · ≥ bn.
(iii) For i = 1, 2, 3, . . . , n :
If Ti ⊆ X, then:
– Delete Ti from X.
– Add i to W .
(iv) Return W.
Is this allocation rule monotone? If so, find a DSIC auction based on this allocation rule. Otherwise, provide an explicit counter example.
(c) Does the greedy allocation rule maximize social welfare? Prove the claim or construct
an explicit counter example.