ARC Colloquium: Sebastian Lahaie, Yahoo! Research

Title: A Kernel-Based Combinatorial Auction

Abstract: In this  talk  I present an iterative combinatorial auction that  offers modularity in the  choice of  price  structure,  drawing on  ideas  from kernel  methods and  the primal-dual paradigm of  auction design.  The  auction is able  to  automatically detect,  as   the   rounds  progress,   whether  price    expressiveness   must    be increased to  clear  the  market, and  converges to  a  sparse  representation of nonlinear clearing prices.  I show  that  by  introducing regularization the auction is able to compute approximate truth-inducing payments in just a single  run, in contrast to VCG payments which require as many  runs as there  are bidders. An empirical evaluation demonstrates the performance gains  that  can be obtained in  allocative efficiency,  revenue,  and  rounds to  convergence through various configurations of  the  auction design against  established linear-   and  bundle- price  auctions.

Poster [PDF]

Event Details


  • Monday, April 16, 2012
    1:00 pm
Location: MiRC 102A

For More Information Contact