Deep Learning for Multi-Facility Location Mechanism Design

Deep Learning for Multi-Facility Location Mechanism Design

Noah Golowich, Harikrishna Narasimhan, David C. Parkes

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 261-267. https://doi.org/10.24963/ijcai.2018/36

Moulin [1980] characterizes the single-facility, deterministic strategy-proof mechanisms for social choice with single-peaked preferences as the set of generalized median rules. In contrast, we have only a limited understanding of multi-facility strategy-proof mechanisms, and recent work has shown negative worst case results for social cost. Our goal is to design strategy-proof, multi-facility mechanisms that minimize expected social cost. We first give a PAC learnability result for the class of multi-facility generalized median rules, and utilize neural networks to learn mechanisms from this class. Even in the absence of characterization results, we develop a computational procedure for learning almost strategy-proof mechanisms that are as good as or better than benchmarks from the literature, such as the best percentile and dictatorial rules.
Keywords:
Machine Learning: Neural Networks
Agent-based and Multi-agent Systems: Algorithmic Game Theory
Agent-based and Multi-agent Systems: Computational Social Choice