Problem $3(20$ points$).$

$($a$)$ Consider a single$-$item auction with player set $N=[n].$ Each player iinN has

a private valuation $v_i$ and specifies a bid $b_i.$ Show that in a Vickrey auction a

player i might be strictly worse of by bidding $b_i{v}_i$ than by bidding truth$-$

fully. That is$,$ show that for every player iinN and for every bid $b_i{v}_i$ there

is a bidding profile $b_{-i}$ of the other players such that $N{u}_i(b_{-i},b_i).$

$(b)$ Consider the combinatorial auction setting, where the set $of$ players $isN$ and

the set $of$ items $isM.$ Assume that the auctioneer runs the $VCG$ mechanism$($Algorithm $10$ in the Lecture Notes$).$ Show that the payments $(p_i{)}_{\text{i}\text{i}\text{n}\text{N}}$ com$-$

puted by the VCG mechanism satisfy that for every player iinN,$0p_i$

$b_i(a^{*}).$