file.pdf (372.92 kB)
Download fileReducing Mechanism Design to Algorithm Design via Machine Learning
journal contribution
posted on 1973-01-01, 00:00 authored by Maria-Florina Belcan, Avrim Blum, Jason D. Hartline, Yishay MansourWe 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 an algorithmic pricing 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 class of allowable pricings. 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, is asymmetric, and has a large range. We address these issues in part by
introducing a new form of covering-number bound that is especially well-suited to
these problems and may be of independent interest.