
CMUCS05143
Computer Science Department
School of Computer Science, Carnegie Mellon University
CMUCS05143
Mechanism Design via Machine Learning
MariaFlorina Balcan, Avrim Blum, Jason D. Hartline*, Yishay Mansour**
May 2005
CMUCS05143.ps
CMUCS05143.pdf
Keywords: Mechanism Design, Machine Learning, Sample Complexity,
Profit Maximization, Unlimited Supply, Digital Good Auction, Attribute
Auctions, Combinatorial Auctions
We use techniques from samplecomplexity in machine learning to reduce
problems of incentivecompatible mechanism design to standard algorithmic
questions, for a broad class of revenuemaximizing 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 itempricing in
unlimitedsupply 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, TelAviv University
