Sunday, December 02, 2012

Learning Mechanism Designs

David Parkes recently visited CMU and gave a very interesting talk on applying machine learning for mechanism design. The talk is based on an award-winning paper titled Payment Rules through Discriminant-Based Classifiers.

For those who are unfamiliar with the term, mechanism design is an area of study that concerns developing pricing and payout systems (or mechanisms) that satisfy various desirable properties (such as incentive compatibility). A canonical example are combinatorial auctions, such as bundled auctions. But this is typically an extremely hard problem from both modeling and computational perspectives.

The two biggest components in mechanism design are matching items or packages to bidders and charging payment. The basic idea of the paper is that, instead of developing a payment rule formulaically, just learn a good payment rule from the distribution of bids that people typically make for the items in question. If such a payment rule could be learned well using machine learning approaches (such as a Structural SVM), then the resulting mechanism is close to incentive compatible and maximizes a wide range of social utility criteria.

I think this is an exciting research direction, because it is often difficult to craft rules for mechanism design (especially when many such rules are not implementable). By taking a data-driven approach, we can learn rules that work reasonably well in a distributional sense, rather than some unrealistic worst-case scenario.

One interesting limitation of the paper is that it assumes training data that comes from agents (or bidders) that are being truthful in their bids. Of course, this is unrealistic. In fact, one of the most prominent applications of this approach is in online ad auctions (such as in commercial search). In such cases, the data being collected is from a previous version of the auction, which is by assumption imperfect and thus does not incentivize truthful bidding.

1 comment:

Rodrigo Martynes said...

Hi! Check out this website. I've been looking for somebody custom writings reviews
proficient to help me and I found it only at this service. They're so great!