Revenue maximization and ex-post budget constraints

Constantinos Daskalakis, Nikhil R. Devanur, S. Matthew Weinberg

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations


We consider the problem of a revenue-maximizing seller with m items for sale to n additive bidders with hard budget constraints, assuming that the seller has some prior distribution over bidder values and budgets. The prior may be correlated across items and budgets of the same bidder, but is assumed independent across bidders. We target mechanisms that are Bayesian Incentive Compatible, but that are ex-post Individually Rational and ex-post budget respecting. Virtually no such mechanisms are known that satisfy all these conditions and guarantee any revenue approximation, even with just a single item. We provide a computationally efficient mechanism that is a 3-approximation with respect to all BIC, ex-post IR, and ex-post budget respecting mechanisms. Note that the problem is NP-hard to approximate better than a factor of 16=15, even in the case where the prior is a point mass [Chakrabarty and Goel 2010]. We further characterize the optimal mechanism in this setting, showing that it can be interpreted as a distribution over virtual welfare maximizers. We prove our results by making use of a black-box reduction from mechanism to algorithm design developed by [Cai et al. 2013]. Our main technical contribution is a computationally efficient 3-approximation algorithm for the algorithmic problem that results by an application of their framework to this problem. The algorithmic problem has a mixed-sign objective and is NP-hard to optimize exactly, so it is surprising that a computationally efficient approximation is possible at all. In the case of a single item (m = 1), the algorithmic problem can be solved exactly via exhaustive search, leading to a computationally efficient exact algorithm and a stronger characterization of the optimal mechanism as a distribution over virtual value maximizers.

Original languageAmerican English
Title of host publicationEC 2015 - Proceedings of the 2015 ACM Conference on Economics and Computation
PublisherAssociation for Computing Machinery, Inc
Number of pages16
ISBN (Electronic)9781450334105
StatePublished - Jun 15 2015
Event16th ACM Conference on Economics and Computation, EC 2015 - Portland, United States
Duration: Jun 15 2015Jun 19 2015

Publication series

NameEC 2015 - Proceedings of the 2015 ACM Conference on Economics and Computation


Conference16th ACM Conference on Economics and Computation, EC 2015
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Economics and Econometrics
  • Statistics and Probability
  • Computer Science (miscellaneous)
  • Computational Mathematics
  • Marketing


  • Budget constraints
  • Generalized assignment problem
  • Revenue optimization
  • Virtual welfare


Dive into the research topics of 'Revenue maximization and ex-post budget constraints'. Together they form a unique fingerprint.

Cite this