Introduction
Mechanism design traditionally relies on manual axiomatic derivation or heuristic search to create rules for social choice and matching. This paper introduces a novel framework that bridges machine learning and mechanism design by using SVM-style optimization to automatically synthesize "money-free" mechanisms. By parametrizing classes of mechanisms that are guaranteed to be strategy-proof or stable, the authors demonstrate how to "learn" a mechanism that mimics a designer's desired outcomes while maintaining strict theoretical guarantees.
The Challenge of Money-Free Design
In settings like school matching or public facility location, agents cannot be compensated for truth-telling. Designing rules for these scenarios involves two primary hurdles:
- Complex Objectives: Designers often struggle to formalize mathematical objective functions, possessing only an intuitive sense of "correct" outcomes for specific historical examples.
- Computational Complexity: Finding rules that satisfy constraints such as strategy-proofness (incentivizing truth-telling) or stability (preventing justified envy) while optimizing a global goal is often computationally intractable.
Methodology: Mechanisms as Classifiers
The core insight of this work is that many strategy-proof or stable mechanisms can be viewed as discriminant-based multiclass classifiers. This allows the application of structural and multiclass Support Vector Machine (SVM) techniques to the mechanism design problem.
Parametrization
The authors identify rich, weight-parametrized classes of mechanisms:
- Social Choice: Weighted Generalized Median (WGM) rules extend standard median rules by weighting both agents and outcomes.
- Two-sided Matching: Weighted Polytope (WP) rules leverage the mathematical structure of the stable matching polytope.
Optimization
To handle the discontinuous nature of distance metrics between mechanism outputs and targets, the authors employ a continuous surrogate objective, analogous to the hinge loss in SVMs. The algorithm finds weights $w$ that minimize the loss between the mechanism’s output and a set of "target labels" provided by the designer.
Experimental Evaluation
The framework was tested on synthetic social choice problems (1D facility location), synthetic one-to-one matching, and real-world school choice data from Wake County, NC.
Social Choice Results
The learned WGM rules consistently outperformed baseline rules, including the best-fixed percentile and dictatorial rules, across various target functions. The approach demonstrated robustness as the number of agents scaled from 5 to 100, maintaining low average absolute distance to the target outcomes.
Matching Results
In synthetic hospital-doctor matching experiments, the Weighted Polytope (WP) rules achieved lower Hamming distance errors compared to standard Deferred Acceptance (DA) variants. This trend extended to real-world school choice data, where the WP rule significantly outperformed DA in matching complex administrative goals, such as diversity-inducing targets (achieving an error of 47.7 compared to 57.3 for DA).
Conclusion
This work represents the first automated approach specifically designed to create stable matching rules, moving beyond rigid classical algorithms like Deferred Acceptance. By treating mechanism design as a statistical learning problem, the authors provide a flexible tool for designers to implement complex administrative goals while preserving essential game-theoretic properties.
Summary updated