TY - GEN

T1 - Mechanism design via machine learning

AU - Balcan, Maria Florina

AU - Blum, Avrim

AU - Hartline, Jason D.

AU - Mansour, Yishay

PY - 2005/12/1

Y1 - 2005/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=33748593645&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33748593645&partnerID=8YFLogxK

U2 - 10.1109/SFCS.2005.50

DO - 10.1109/SFCS.2005.50

M3 - Conference contribution

AN - SCOPUS:33748593645

SN - 0769524680

SN - 9780769524689

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 605

EP - 614

BT - Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005

T2 - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005

Y2 - 23 October 2005 through 25 October 2005

ER -