Reducing mechanism design to algorithm design via machine learning

Maria Florina Balcan*, Avrim Blum, Jason D. Hartline, Yishay Mansour

*Corresponding author for this work

Research output: Contribution to journalArticle

42 Scopus citations

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 languageEnglish (US)
Pages (from-to)1245-1270
Number of pages26
JournalJournal of Computer and System Sciences
Volume74
Issue number8
DOIs
StatePublished - 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