Automated Mechanism Design without Money via Machine Learning

Abstract

We use statistical machine learning to develop methods for automatically designing mechanisms in domains without money. Our goal is to find a mechanism that best approximates a given target function subject to a design constraint such as strategy-proofness or stability. The proposed approach involves identifying a rich parametrized class of mechanisms that resemble discriminant-based multiclass classifiers, and relaxing the resulting search problem into an SVM-style surrogate optimization problem. We use this methodology to design strategy-proof mechanisms for social choice problems with single-peaked preferences, and stable mechanisms for two-sided matching problems. To the best of our knowledge, ours is the first automated approach for designing stable matching rules. Experiments on synthetic and real-world data confirm the usefulness of our methods.