Computationally Feasible Automated Mechanism Design: General Approach and Case Study on VCG Redistribution Mechanisms

Title: Computationally Feasible Automated Mechanism Design: General Approach and Case Study on VCG Redistribution Mechanisms
Speaker: Dr. Mingyu Guo, the University of Liverpool
Inviter: Dr. Sun Xiaoming, Center for Advanced Computing Research, ICT
Time: 14:00pm—15:00pm, January 6th, 2012 (Monday)
Place: Room 446, Institute of Computing Technology, Chinese Academy of Sciences
Abstract:
In many multiagent settings, a decision must be made based on the preferences of multiple agents, and agents may lie about their preferences if this is to their benefit. In mechanism design, the goal is to design procedures (mechanisms) for making the decision that work in spite of such strategic behavior, usually by making untruthful behavior suboptimal. In automated mechanism design, the idea is to computationally search through the space of feasible mechanisms, rather than to design them analytically by hand. Unfortunately, the most straightforward approach to automated mechanism design does not scale to large instances, because it requires searching over a very large space of possible functions. In this paper, we describe an approach to automated mechanism design that is computationally feasible. Instead of optimizing over all feasible mechanisms, we carefully choose a parameterized subfamily of mechanisms. Then we optimize over mechanisms within this family, and analyze whether and to what extent the resulting mechanism is suboptimal outside the subfamily. We demonstrate the usefulness of our approach with one case study on VCG redistribution mechanisms.

Bio:
Dr. Mingyu Guo is a Lecturer (US equivalent of Assistant Professor) in the Department of Computer Science at the University of Liverpool. Guo's research interests include algorithmic game theory, multiagent systems, mechanism design, and prediction markets. Prior to joining the University of Liverpool, Guo received his Ph.D. in Computer Science from Duke University in 2010. His Ph.D. dissertation was recognized as a runner-up for the prestigious Victor Lessor Dissertation Award. Guo has been invited to serve on the program committee of many academic conferences, including AAAI, AAMAS, AMEC, EC, IJCAI, and WWW.