Abstract: Systems wherein strategic agents compete for limited resources are ubiquitous: the economy, computer networks, social networks, congestion networks, etc.  Auction theory governs the design and analysis of these systems.  I will describe a method for using approximation in auction theory to identify simple, practical, and robust auction mechanisms that perform nearly as well as the complex optimal ones.  A main goal of this approach is to understand the extent to which important intuition from optimal auctions for ideal models extends to approximately optimal auctions for more realistic models.

Auction theory is well understood only in ideal models where agents have single-dimensional, linear preferences.  I.e., each agent has a value for receiving a service and her utility is the difference between her value and her payment.  For these models optimal auctions can be interpreted as "marginal revenue" maximizers (Myerson, 1981; Bulow and Roberts 1989).  In more realistic models, i.e., where bidders have multi-dimensional preferences for different outcomes or non-linear utility, similar intuitive characterizations are unknown.  Understanding good auctions for these environments is considered to be the main challenge in auction theory.  In these more realistic environments maximizing marginal revenue may not be optimal, and furthermore, there is sometimes no direct way to implementing the marginal revenue maximization mechanism. I will present two results:  I will give procedures for implementing marginal revenue maximization in general, and I will show that marginal revenue maximization is approximately optimal.  The approximation factor smoothly degrades in a term that quantifies how far the environment is from an ideal one (i.e., where marginal revenue maximization is optimal).

Joint work with Saeed Alaei, Hu Fu, Nima Haghpanah, and Azarakhsh Malekian.