Lecture: Adaptive Online Allocation Mechanisms for Single-Valued Domains
Professor David Parkes from the Division of Engineering and Applied Science at Harvard University will deliver this lecture as part of the Spring 2007 Operations Research / Management Science Seminar series. All are invited to attend.
Title: Adaptive Online Allocation Mechanisms for Single-Valued Domains
Abstract: Mechanism design studies the problem of designing protocols that will implement desirable outcomes in multi-agent systems with self-interest and private information. Many interesting domains are inherently dynamic with uncertainty about both supply and demand; e.g., selling seats on an airplane, adverts on a search engine, computational resources. The classic Vickrey-Clarke-Groves mechanism extends to dynamic environments but is non-adaptive and much less robust than when used offline. Our interest in this talk is in the design of adaptive, online allocation mechanisms, that are able to leverage a probabilistic (perhaps incorrect) model of the environment. We focus on single-valued domains in which agents are indifferent across one of a set of equivalent allocations. A truthful, online stochastic optimization algorithm coupled with historical sampling and an ironing procedure is presented, along with theoretical analysis to demonstrate that the optimal policy is generally not truthfully implementable. Experimental analysis illustrates the cost of truthfulness in application to selling a computational resource.
This series is organized by the UMass Amherst INFORMS Student Chapter. Support for this series is provided by the Isenberg School of Management, the Department of Finance and Operations Management, and the John F. Smith Memorial Fund.
Check here for more details about this speaker series.
