Skip to main content

Revenue Maximization and Ex-Post Budget Constraints

Author(s): Daskalakis, Constantinos; Devanur, Nikhil R; Weinberg, S Matthew

To refer to this page use:
Abstract: 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. 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. Our main technical contribution is a computationally efficient 3-approximation algorithm for the algorithmic problem that results from 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.
Publication Date: Oct-2018
Citation: Daskalakis, Constantinos, Nikhil R. Devanur, and S. Matthew Weinberg. "Revenue Maximization and Ex-Post Budget Constraints." ACM Transactions on Economics and Computation 6, no. 3-4 (2018): 20:1-20:19.
DOI: 10.1145/3274647
ISSN: 2167-8375
EISSN: 2167-8383
Pages: 20:1 - 20:19
Type of Material: Journal Article
Journal/Proceeding Title: ACM Transactions on Economics and Computation
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.