Mechanism Design for Public Projects via Neural Networks
- Dr. Mingyu Guo, The University of Adelaide
- Time: 2019-11-26 15:30
- Host: Prof. Xiaotie Deng
- Venue: Room 102, Courtyard No.5, Jingyuan
Abstract
We study mechanism design for nonexcludable and excludable binary public project problems. We aim to maximize the expected number of consumers and the expected social welfare. For the nonexcludable public project model, we identify a sufficient condition on the prior distribution for the conservative equal costs mechanism to be the optimal strategy-proof and individually rational mechanism. For general distributions, we propose a dynamic program that solves for the optimal mechanism. For the excludable public project model, we identify a similar sufficient condition for the serial cost sharing mechanism to be optimal for 2 and 3 agents. We derive a numerical upper bound. Experiments show that for several common distributions, the serial cost sharing mechanism is close to optimality.
The serial cost sharing mechanism is not optimal in general. We design better performing mechanisms via neural networks. Our approach involves several technical innovations that can be applied to mechanism design in general. We interpret the mechanisms as price-oriented rationing-free (PORF) mechanisms, which enables us to move the mechanism's complex (e.g., iterative) decision making off the network, to a separate program. We feed the prior distribution's analytical form into the cost function to provide quality gradients for training. We use supervision to manual mechanisms as a systematic way for initialization. Our approach of "supervision and then gradient descent" is effective for improving manual mechanisms' performances. It is also effective for fixing constraint violations for heuristic-based mechanisms that are infeasible.
Biography
Mingyu GUO received the B.S. degree in mathematics from Zhejiang University, in 2004, the M.S. degree in applied mathematics from the University of Florida, in 2006, and the Ph.D. degree in computer science from Duke University, in 2010. His Ph.D. dissertation, entitled Computationally Feasible Approaches to Automated Mechanism Design, was selected as one of the two runner-ups for the prestigious IFAAMAS-10 Victor Lessor Distinguished Dissertation Award (an annual award for the Best Ph.D. Dissertation in the field of multiagent systems). He held a position as a Lecturer with the University of Liverpool, until 2013, and has been a Lecturer with The University of Adelaide since then. His interests are in algorithmic game theory and multiagent systems. His work appeared in top computer science journals (e.g., the Artificial Intelligence and the Journal of Artificial Intelligence Research), top computer science conferences (e.g., AAAI, IJCAI, AAMAS, and EC), and top economics journal (Games and Economic Behavior). He has served as a Senior Program Committee Member for CORE A* conferences including IJCAI, AAAI, and AAMAS.