Deep Learning for Multi Facility Location Mechanism Design
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 strategyproof 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 multifacility 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.
IJCAI