An Ironing-Based Approach to Adaptive Online Mechanism Design in Single-Valued Domains

David C. Parkes, Quang Duong

Online mechanism design considers the problem of sequential decision making in a multi-agent system with self-interested agents. The agent population is dynamic and each agent has private information about its value for a sequence of decisions. We introduce a method (``ironing") to transform an algorithm for online stochastic optimization into one that is incentive-compatible. Ironing achieves this by canceling decisions that violate a form of monotonicity. The approach is applied to the Consensus algorithm and experimental results in a resource allocation domain show that not many decisions need to be canceled and that the overhead of ironing is manageable.

Subjects: 7. Distributed AI; 9.3 Mathematical Foundations

Submitted: Apr 24, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.