Speaker: Nina Balcan

Time: Wednesday 12-1pm

Place: NSH 1507

Title: Mechanism Design via Machine Learning

Abstract:
In this work, we make an explicit connection between machine learning and
mechanism design. In doing so, we obtain a unified approach for
considering a variety of profit maximizing mechanism design problems,
including many that have been previously considered in the literature.
In particular, we use techniques from sample-complexity in machine
learning theory to reduce problems of incentive-compatible mechanism
design to standard algorithmic questions. We apply these results to a wide
variety of revenue-maximizing pricing problems, including the problem of
auctioning a digital good, the attribute auction problem, and the problem
of item-pricing in unlimited-supply combinatorial auctions.

It is worth noting that from a learning perspective, these settings
present several unique challenges: the loss function is discontinuous and
asymmetric, and the range of bidders' valuations may be large.

This is joint work with Avrim Blum, Jason Hartline, and Yishay Mansour, to
appear in FOCS'05.