TOYOTA AI SEMINAR SERIES
      Department of Electrical Engineering and Computer Science
              Stained-Glass Conference Room (3725 CSE)
              4:00 - 5:30 PM Tuesday, October 24, 2006


    Using Mathematical Programming to Make VCG Auctions Tractable

                                  by
				   
                               Amy Cohn
      Assistant Professor, Industrial and Operations Engineering


Abstract:

Combinatorial auctions are very useful in theory but their
applicability in practice is limited by the need for bidders to bid on
an exponential number of bundles and the auctioneer to solve an
exponentially large winner-determination problem. We seek to eliminate
these challenges for a broad class of VCG combinatorial auctions by
exploiting the fact that true-cost bidding is a dominant strategy in
these auctions. Our proposed mechanism eliminates the need for
explicit bidding on each bundle, instead using mathematical
programming to implicitly capture all bids via the bidder's true-cost
function. Likewise, the auctioneer's winner-determination problem can
be simplified significantly. We use the problem of
truckload-procurement auctions as a means to demonstrate our approach.

This is joint work with Professors Amitabh Sinha and Damian Beil of
the Ross School of Business, and Richard Chen and Shervin AhmadBeygi
of the Department of Industrial and Operations Engineering.


Bio:

Amy Cohn is an Assistant Professor in the Department of Industrial and
Operations Engineering. She obtained her Ph.D. in Operations Research
from the Massachusetts Institute of Technology. Her research emphasis
is on solving applied problems in large-scale combinatorial
optimization, primarily in the domains of transportation and
logistics. She is currently a Sloan Industry Studies Fellow, studying
the impact of delay propagation on passenger airline plans.