## 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 [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 language | English (US) |
---|---|

Title of host publication | EC 2015 - Proceedings of the 2015 ACM Conference on Economics and Computation |

Publisher | Association for Computing Machinery, Inc |

Pages | 433-448 |

Number of pages | 16 |

ISBN (Electronic) | 9781450334105 |

DOIs | |

State | Published - Jun 15 2015 |

Event | 16th ACM Conference on Economics and Computation, EC 2015 - Portland, United States Duration: Jun 15 2015 → Jun 19 2015 |

### Publication series

Name | EC 2015 - Proceedings of the 2015 ACM Conference on Economics and Computation |
---|

### Other

Other | 16th ACM Conference on Economics and Computation, EC 2015 |
---|---|

Country/Territory | United States |

City | Portland |

Period | 6/15/15 → 6/19/15 |

## All Science Journal Classification (ASJC) codes

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

## Keywords

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