Introduction
Matching theory is a fundamental pillar of economics and computer science, governing systems ranging from school choice and residency programs to organ donation networks. At its heart, the field seeks to design mechanisms—algorithms—that satisfy desirable properties known as axioms. Common examples include stability (ensuring no two agents prefer each other over their assigned partners) and strategyproofness (ensuring agents cannot gain an advantage by misrepresenting their preferences).
However, designers often encounter "impossibility theorems": mathematical proofs showing that certain sets of axioms are mutually exclusive. Traditionally, discovering and proving these results required significant manual effort. This paper presents a framework that automates this process using SAT solvers, leading to the discovery of new impossibility results in one-to-one matching.
The Preservation Theorem: Bridging the Gap
The primary theoretical contribution of this work is the Preservation Theorem. In computer-aided social choice, a recurring challenge is the "inductive step"—generalizing a result found for a small number of agents (e.g., $n=3$) to all larger populations.
The author proves that for a specific class of "universal axioms," if a matching mechanism exists for $n$ agents, a corresponding mechanism must also exist for $n-1$ agents. By contrapositive, if a SAT solver proves that no mechanism can satisfy a set of axioms for 3 agents, it is mathematically guaranteed to be impossible for any number of agents greater than 3. This theorem allows researchers to use automated tools to provide rigorous, general proofs.
Methodology: From Logic to SAT
To leverage the power of modern SAT solvers, matching axioms must be translated into a machine-readable format. The author defines a fragment of first-order logic to express these requirements using universal quantifiers.
The process involves several steps:
- Axiom Encoding: Axioms like stability and gender-indifference are written using universal quantifiers ($\forall$).
- CNF Translation: A Python script converts these logical formulas into Conjunctive Normal Form (CNF), the standard input for SAT solvers.
- SAT Solving: The PicoSAT solver checks the satisfiability of the resulting formula for a base case (typically $n=3$).
- Proof Extraction: If the formula is unsatisfiable, the PicoMUS tool identifies a "Minimal Unsatisfiable Subset" (MUS). This subset provides the core logical contradiction, which can be translated back into a human-readable proof.
Key Results and Performance
The automated framework successfully identified and provided human-readable proofs for two new impossibility theorems:
- Theorem 5: No mechanism can simultaneously satisfy top-stability and two-way strategyproofness for $n \geq 3$. This result strengthens a classic finding by Roth (1982) by showing the impossibility persists even when the stability requirement is significantly weakened.
- Theorem 6: It is impossible to achieve both stability and gender-indifference for $n \geq 3$. Gender-indifference is a fairness axiom requiring that the mechanism treats both sides of the market (e.g., men and women) symmetrically.
The computational efficiency of this approach is noteworthy. Despite the massive search space—over 46,000 preference profiles for $n=3$—the solver reached conclusions in under a minute.
Limitations and Future Directions
While powerful, the method faces a "state-space explosion." The number of variables required for $n=4$ exceeds $1.7 \times 10^{12}$, which is currently beyond the reach of SAT technology. Consequently, if an impossibility only emerges at $n=4$ or higher, this tool cannot yet detect it.
Furthermore, the Preservation Theorem only applies to "universal" axioms. Properties that cannot be expressed solely with "for all" quantifiers remain outside the scope of this automated generalization. Future work may focus on extending the logic fragment or applying these techniques to "one-to-many" matching markets.
Summary updated