Optimal Design for Multi-Item Auctions: A Robust Optimization Approach

In this paper, we revisit the auction design problem for multi-item auctions with budget constrained buyers by introducing a robust optimization approach to model (a) concepts such as incentive compatibility and individual rationality that are naturally expressed in the language of robust optimization and (b) the auctioneer's beliefs on the buyers' valuations of the items. Rather than using probability distributions (the classical probabilistic approach) or an adversarial model to model valuations, we introduce an uncertainty set based model for these valuations. We construct these uncertainty sets to incorporate historical information available to the auctioneer in a way that is consistent with limit theorems of probability theory or knowledge of the probability distribution. In this setting, we formulate the auction design problem as a robust optimization problem and provide a characterization of the optimal solution as an auction with reservation prices, thus extending the work of Myerson [Myerson RB (1981) Optimal auction design. Math. Oper. Res. 6(1):58-73] from single item without budget constraints to multiple items with budgets, potentially correlated valuations, and uncertain budgets. Unlike the Myerson auction where the reservation prices do not depend on the item, the reservation prices in our approach are a function of both the bidder and the item. We propose an algorithm for calculating the reservation prices by solving a bilinear optimization problem that, although theoretically difficult in general, is numerically tractable for the polyhedral uncertainty sets we consider. Moreover, this bilinear optimization problem reduces to a linear optimization problem for auctions without budget constraints and the auction becomes the classical second price auction. We report computational evidence that suggests the proposed approach (a) is numerically tractable for large scale auction design problems with the polyhedral uncertainty sets we consider, (b) leads to improved revenue compared to the classical probabilistic approach when the true distributions are different from the assumed ones, and (c) leads to higher revenue when correlations in the buyers' valuations are explicitly modeled.