* Faculty       * Staff       * Students & Alumni       * Committees       * Contact       * Institute Directory
* Undergraduate Program       * Graduate Program       * Courses       * Institute Catalog      
* Undergraduate       * Graduate       * Institute Admissions: Undergraduate | Graduate      
* Colloquia       * Seminars       * News       * Events       * Institute Events      
* Overview       * Lab Manual       * Institute Computing      
No Menu Selected

* News


The Kernel Approach to Combinatorial Auction Design

Dr. Sébastien Lahaie
Yahoo! Research

November 18, 2010
JEC 3117 - 4:00 p.m. to 5:00 p.m.


An auction typically serves dual purposes: to find clearing prices that balance supply and demand, and (in so doing) to determine an efficient transfer of resources from sellers to buyers. In environments where buyers would like to acquire multiple different resources at once, combinatorial auctions have emerged as a method of choice for efficient allocation. However, pricing in such environments is complicated by the fact that linear (i.e., item) prices may not exist to clear the market---one may need to resort to nonlinear (i.e., bundle) prices instead. The problem of finding nonlinear clearing prices is challenging because such prices may be difficult to succinctly describe, let alone efficiently compute. In this work, I draw on techniques from kernel methods in machine learning to design a combinatorial auction that addresses both of these issues. I show that market-clearing directly generalizes the familiar machine learning problems of regression and classification, and that techniques such as the kernel trick can be applied to design a combinatorial auction with modular price structure. An empirical evaluation demonstrates that, with a proper choice of kernel function, the auction is able to find sparse nonlinear clearing prices with much less than full revelation of values and costs. I also show how the auction can be made approximately truthful by drawing on connections between incentive-compatibility and regularization.


Sébastien Lahaie joined Yahoo Research as a research scientist in October of 2007. At Yahoo his research focuses on marketplace design, including sponsored search and display advertising. He was recently a co-organizer of the Sixth Workshop on Ad Auctions and the Third New York Computer Science and Economics day. He received his Ph.D. in Computer Science from Harvard University in 2007, and B.A. in Computer Science and Mathematics from Dartmouth College in 2002.

Hosted by: Dr. Sanmay Das (x2782)

Last updated: October 26, 2010