CMU talk: Adaptive Online Allocation Mechanisms for Single-Valued Domains

Adaptive Online Allocation Mechanisms for Single-Valued Domains

David C. Parkes, Harvard University

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 examples to show that the optimal policy is generally not truthfully implementable. Simulation analysis illustrates the cost of truthfulness in application to selling a computational resource.

Bio: David C. Parkes is the John L. Loeb Associate Professor of the Natural Sciences and Associate Professor of Computer Science at Harvard University. He received his Ph.D. degree in Computer and Information Science from the University of Pennsylvania in 2001, and an M.Eng. (First class) in Engineering and Computing Science from Oxford University in 1995. He was awarded the prestigious NSF CAREER Award in 2002, an IBM Faculty Partnership Award in 2002 and 2003, and the Alfred P. Sloan Fellowship in 2005. Parkes has published extensively on topics related to electronic markets, computational mechanism design, auction theory, and multi-agent systems. He serves on the editorial board of the Journal of Artificial Intelligence Research and the Electronic Commerce Research Journal, and has served on the Program Committee of a number of leading conferences in artificial intelligence, multiagent systems and electronic commerce, including ACM-EC, AAAI, IJCAI, UAI and AAMAS. Parkes is the co program-chair of the ACM Conference on Electronic commerce, 2007 and the Int. Conf. on Autonomous Agents and Multiagent systems, 2008.

http://www.eecs.harvard.edu/~parkes