Skip to main content

How to approximate optimal auctions

Publication ,  Journal Article
Haghpanah, N; Immorlica, N; Mirrokni, V; Munagala, K
Published in: ACM SIGecom Exchanges
June 2012

Bayesian auction design investigates how to sell scarce resources to agents with private values drawn according to known distributions. A natural objective in this setting is revenue maximization. The seminal work of Roger Myerson presents a recipe for designing revenue-maximizing auctions in single-parameter settings. Myerson defines a function that maps each agent's value to a new number called the . The optimal auction then chooses the solution with maximum virtual surplus subject to the feasibility constraints. Often this underlying optimization problem is NP-hard and is complicated by the fact that virtual values may be negative. Prior work approximates the optimal auction by approximating this optimization problem. Such a solution can be interpreted as approximating the optimal auction point-wise, i.e., for each realization of values the revenue of the derived auction is close to that of the Myerson auction. In this letter, we suggest a different approach: . Our approach has the advantage that sometimes the point-wise optimization problem is not approximable to within any reasonable factor. However, by leveraging the fact that any distribution of virtual values has non-negative expectation, it is sometimes possible to get good average-case approximations. Furthermore, the optimal auction is itself an average-case guarantee: it maximizes the revenue on average with respect to the distributions, but it may lose substantial revenue on certain value profiles. Thus our average-case guarantee is without loss of generality.We showcase our approach using the problem of selling goods with positive network externalities. For this problem, the underlying optimization problem is inapproximable, yet with our approach we are able to prove that a natural greedy auction is a constant-factor approximation.

Duke Scholars

Published In

ACM SIGecom Exchanges

DOI

EISSN

1551-9031

Publication Date

June 2012

Volume

11

Issue

1

Start / End Page

30 / 33

Publisher

Association for Computing Machinery (ACM)
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Haghpanah, N., Immorlica, N., Mirrokni, V., & Munagala, K. (2012). How to approximate optimal auctions. ACM SIGecom Exchanges, 11(1), 30–33. https://doi.org/10.1145/2325713.2325719
Haghpanah, Nima, Nicole Immorlica, Vahab Mirrokni, and Kamesh Munagala. “How to approximate optimal auctions.” ACM SIGecom Exchanges 11, no. 1 (June 2012): 30–33. https://doi.org/10.1145/2325713.2325719.
Haghpanah N, Immorlica N, Mirrokni V, Munagala K. How to approximate optimal auctions. ACM SIGecom Exchanges. 2012 Jun;11(1):30–3.
Haghpanah, Nima, et al. “How to approximate optimal auctions.” ACM SIGecom Exchanges, vol. 11, no. 1, Association for Computing Machinery (ACM), June 2012, pp. 30–33. Crossref, doi:10.1145/2325713.2325719.
Haghpanah N, Immorlica N, Mirrokni V, Munagala K. How to approximate optimal auctions. ACM SIGecom Exchanges. Association for Computing Machinery (ACM); 2012 Jun;11(1):30–33.

Published In

ACM SIGecom Exchanges

DOI

EISSN

1551-9031

Publication Date

June 2012

Volume

11

Issue

1

Start / End Page

30 / 33

Publisher

Association for Computing Machinery (ACM)