Multi-parameter Mechanisms for Consumer Surplus Maximization

We consider the problem of designing auctions that maximize consumer surplus (i.e., the social welfare minus the payments charged to the buyers). In the consumer surplus maximization problem, a seller with a set of goods faces a set of strategic buyers with private values, each of whom aims to maximize their own individual utility. The seller, in contrast, aims to allocate the goods in a way that maximizes the total buyer utility. The seller must then elicit the values of the buyers in order to decide what goods to award each buyer. The canonical approach in mechanism design to ensure truthful reporting of the private information is to find appropriate prices to charge each buyer in order to align their objective with the objective of the seller. Indeed, there are many celebrated results to this end when the seller's objective is welfare maximization [36, 9, 16] or revenue maximization [25] . However, in the case of consumer surplus maximization the picture is less clear -using high payments to ensure the highest value bidders are served necessarily decreases their surplus utility, but using low payments may lead the seller into serving lower value bidders. Our main result in this paper is a framework for designing mechanisms that maximize consumer surplus. We instantiate our framework in a variety of canonical multi-parameter auction settings (i.e., unit-demand bidders with heterogeneous items, multi-unit auctions, and auctions with divisible goods) and use it to design auctions achieving consumer surplus with tight approximation guarantees against the total social welfare. Along the way, we resolve an open question posed by Hartline and Roughgarden [20] for the two bidder single item setting.