AI Seminar

A Kernel-Based Combinatorial Auction

Sébastien Lahaie

Microsoft Research
Tuesday, January 28, 2014
4:00pm - 5:30pm
3725 BBB

Add to Google Calendar

About the Event

In a combinatorial auction, buyers place bids on packages of items to account for complementarities. I present a combinatorial auction that offers modularity in the choice of price structure, drawing on ideas from kernel methods, typically used for machine learning tasks. As implemented, the auction is able to detect whether price complexity must be increased to clear the market, and converges to a sparse representation of nonlinear clearing prices. An empirical evaluation against a state of the art ascending-price auction demonstrates the performance gains that can be obtained in efficiency, revenue, and rounds to convergence through various configurations of the design. Throughout the talk, I will highlight the similarities and differences between the problem of market clearing and classic learning problems like classification and regression, and also touch upon connections between the concepts of generalization and incentive-compatibility. No background on combinatorial auctions or kernel methods is assumed.


Sébastien Lahaie is a researcher at Microsoft Research, New York City. He received his PhD in Computer Science from Harvard University in 2007 and was previously a research scientist at Yahoo. His research focuses on computational aspects of marketplace design, including sponsored search and display advertising. He is interested in designing market algorithms that scale well and properly anticipate user behavior. Other interests include preference modeling and elicitation, combinatorial auctions, and prediction markets. He serves as a co-editor for Economic Inquiry and was previously a program chair for AMMA.

Additional Information

Sponsor(s): Toyota

Open to: Public