Stochastic Analysis via Robust Optimization: Robust Optimal Auctions

Abstract: 
Modern probability theory, whose foundation is based on the axioms set forth by Kolmogorov, is currently the major tool for performance analysis in stochastic systems. While it offers insights in understanding such systems, probability theory is really not a computationally tractable theory in high dimensions. Correspondingly, some of its major areas of application remain unsolved when the underlying systems become multidimensional (which is often the case in practice): Queueing networks, network information theory, pricing multi-dimensional financial contracts, auction design in multi-item, multi-bidder auctions among others.

We propose a new approach to analyze stochastic systems based on robust optimisation, which we have applied to solve some of the key problems in these application domains.The key idea is to replace the Kolmogorov axioms as primitives of probability theory, with some of the asymptotic implications of probability theory: the central limit theorem and law of large numbers and to define appropriate robust optimisation problems to perform performance analysis. In this way, the performance analysis questions become highly structured optimisation problems (linear, conic, mixed integer) for which there exist efficient, practical algorithms that are capable of solving truly large scale systems. 

In this talk, we revisit the auction design problem for multi-item auctions with budget constrained buyers by introducing a robust optimisation approach to model (a) concepts such as incentive compatibility and individual rationality that are naturally expressed in the language of robust optimisation 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 optimisation problem and provide a characterization of the optimal solution as an auction with reservation prices, thus extending the work of Myerson [1981] from single item without budget constraints, to multiple items with budgets, potentially correlated valuations and uncertain budgets. We propose an algorithm for calculating the reservation prices by solving a bilinear optimisation problem which, although theoretically difficult in general, is numerically tractable. Moreover, this bilinear optimisation problem reduces to a linear optimisation 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, (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.

Joint work with Professor Dimitris Bertsimas, MIT.