### Abstract

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 an algorithmic pricing problem, we can convert it into a (1 + ε{lunate})-approximation (or β (1 + ε{lunate})-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.

Original language | English (US) |
---|---|

Pages (from-to) | 1245-1270 |

Number of pages | 26 |

Journal | Journal of Computer and System Sciences |

Volume | 74 |

Issue number | 8 |

DOIs | |

State | Published - Dec 1 2008 |

### Keywords

- Attribute auctions
- Combinatorial auctions
- Covering numbers
- Digital good auction
- Machine learning
- Mechanism design
- Profit maximization
- Sample complexity
- Structural risk minimization
- Unlimited supply

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Networks and Communications
- Computational Theory and Mathematics
- Applied Mathematics

## Fingerprint Dive into the research topics of 'Reducing mechanism design to algorithm design via machine learning'. Together they form a unique fingerprint.

## Cite this

*Journal of Computer and System Sciences*,

*74*(8), 1245-1270. https://doi.org/10.1016/j.jcss.2007.08.002