Capturing Corruption with Hybrid Auctions: Social Welfare Loss in Multi-Unit Auctions.

Corruption in auctions is a phenomenon that is theoretically still poorly understood, despite the fact that it occurs rather frequently in practice. In this paper, we initiate the study of the social welfare loss caused by a corrupt auctioneer, both in the single-item and the multi-unit auction setting. In our model, the auctioneer may collude with the winners of the auction by letting them lower their bids in exchange for a fixed fraction $\gamma$ of the surplus. As it turns out, this setting is equivalent to a $\gamma$-hybrid auction in which the payments are a convex combination (parameterized by $\gamma$) of the first-price and the second-price payments. Our goal is thus to obtain a precise understanding of the (robust) price of anarchy of $\gamma$-hybrid auctions. If no further restrictions are imposed on the bids, we prove a bound on the robust POA which is tight (over the entire range of $\gamma$) for the single-item and the multi-unit auction setting. On the other hand, if the bids satisfy the no-overbidding assumption a more fine-grained landscape of the price of anarchy emerges, depending on the auction setting and the equilibrium notion. We derive tight bounds for single-item auctions up to the correlated price of anarchy and for the pure price of anarchy in multi-unit auctions. These results are complemented by nearly tight bounds on the coarse correlated price of anarchy in both settings.