We use techniques from sample-complexity in machine learning to reduce problems of incentive-compatible mechanism design to standard algorithmic questions, for a broad class of revenue-maximizing pricing problems. Our reductions imply that for these problems, given an optimal (or Β-approximation) algorithm for the standard algorithmic problem, we can convert it into a (1 + ε)-approximation (or Β(1 + ε)-approximation) for the incentive compatible mechanism design problem, so long as the number of bidders is sufficiently large as a function of an appropriate measure of complexity of the comparison class of solutions. We apply these results to the problem of auctioning a digital good, to the attribute auction problem which includes a wide variety of discriminatory pricing problems, and to the problem of item-pricing in unlimited-supply combinatorial auctions. From a machine learning perspective, these settings present several challenges: in particular, the loss function is discontinuous and asymmetric, and the range of bidders' valuations may be large.

33 pages

*Microsoft Research, Mountain View, CA
**School of Computer Science, Tel-Aviv University

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu