Thursday, October 18, 2007
4:15 pm
B17 Upson Hall

Computer Science
Fall 2007

David C. Parkes
Harvard University

Tell the truth: Incentives for Dynamic Multi-Agent Environments

Many interesting multi-agent systems are inherently dynamic, with uncertainty about both supply and demand, and populated by self-interested participants; e.g., selling seats on an airplane, adverts on a search engine, resources on computational grids, or access to fractionated satellites. These dynamics challenge the existing methodologies of computational mechanism design (CMD), in which one seeks to design a static game to solve a static problem. In this talk, I first review some important results in CMD, providing a backdrop for the challenges in the design of dynamic incentive mechanisms. In the dynamic setting, we see that although the classic VCG mechanism can be generalized, the computational challenges endemic to the use of the VCG mechanism become even more severe. In responding to these challenges, I will describe the complementary direction of "computational ironing" as a procedure for scalable, dominant-strategy mechanisms. Computational ironing judiciously cancels decisions proposed by methods of stochastic combinatorial optimization, leaving a modified policy that is provably non-manipulable. Time permitting, I will try to touch on some directions for future work.