Reducing mechanism design to algorithm design via machine learning
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 beta-approximation) algorithm for an algorithmic pricing problem, we can convert it into a (1 + epsilon)-approximation (or beta(l + epsilon)-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. (C) 2007 Elsevier Inc. All tights reserved.
mechanism design machine learning attribute auctions combinatorial auctions sample complexity profit maximization unlimited supply digital good auction structural risk minimization covering numbers