Mechanism design via machine learning

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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

67 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 wide variety of revenue-maximizing 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, the attribute auction problem, and to the problem of item-pricing in unlimited-supply combinatorial auctions. From a 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.

Original languageEnglish (US)
Title of host publicationProceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005
Pages605-614
Number of pages10
DOIs
StatePublished - Dec 1 2005
Event46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005 - Pittsburgh, PA, United States
Duration: Oct 23 2005Oct 25 2005

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2005
ISSN (Print)0272-5428

Other

Other46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005
CountryUnited States
CityPittsburgh, PA
Period10/23/0510/25/05

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Mechanism design via machine learning'. Together they form a unique fingerprint.

Cite this