Mechanism Design under Interdependent Valuations

Abstract: We study buyers with interdependent valuations: where one buyer's private information about an item impacts how much another buyer is willing to pay for it. In this setting, if a buyer misreports his own private information, he can impact not only what the auctioneer believes his own value is, but also what the auctioneer believes regarding other buyers' values as well, allowing him to essentially corrupt their values. As a result, the usual mechanism design tricks fall short, and welfare maximization is notoriously difficult. Almost all prior work in this setting requires a very strong "single-crossing" condition on the valuation functions in order to obtain any positive results.

We introduce two more natural notions -- first, a relaxed, parameterized notion of single-crossing, and second, a completely unrelated notion, one of submodularity over the private information of buyers -- that each separately enable good approximation guarantees to optimal welfare. These conditions, combined with the lens of approximation, allow us to go beyond not only the restrictive single-crossing notion, but to go far beyond the single-item setting and to give positive results for even the very general setting of combinatorial auctions.

Joint work with Alon Eden, Michal Feldman, Amos Fiat, and Anna Karlin.