Research map / Learning theory and algorithms / Submodular and game algorithms
Analysis of One-to-One Matching Mechanisms via SAT Solving: Impossibilities for Universal Axioms
Ulle Endriss
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use preservation theorem to reduce impossibility proof to n=3 base case checked by SAT solver | matching mechanism axioms · Theorem 5 and 6 | proof resources: 64s MUS for Theorem 5, 19s for Theorem 6 | Improved |
| lower bound from n>=3 to n>=2 for Theorem 5 and 6 (ablation) | impossibility theorems · matching mechanisms | impossibility holds | Hurt |
| weaken two-way strategyproofness to one-way strategyproofness (ablation) | Theorem 5 · matching mechanisms | impossibility holds | Hurt |
| weaken stability to top-stability (ablation) | Theorem 6 · matching mechanisms | impossibility holds | Hurt |
Closest papers by meaning
- Strategyproof Matching of Roommates and Rooms (AAAI 2025 · similarity 0.88)
- Reachability of Fair Allocations via Sequential Exchanges (AAAI 2024 · similarity 0.88)
- Welfare-Optimal Serial Dictatorships Have Polynomial Query Complexity (AAAI 2025 · similarity 0.87)
- On Hierarchies of Fairness Notions in Cake Cutting: From Proportionality to Super Envy-Freeness (NeurIPS 2025 · similarity 0.86)
- The Complexity of Extending Fair Allocations of Indivisible Goods (AAAI 2025 · similarity 0.86)
- On the Power of Randomization for Obviously Strategy-Proof Mechanisms (AAAI 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
