Research map / Large language models / Instruction and fine-tuning
Matching Markets Meet LLMs: Algorithmic Reasoning with Ranked Preferences
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Evaluates seven LLMs on matching-market tasks (stable matching generation, instability resolution/detection, ranked-preference queries) and shows LoRA fine-tuning helps small markets but not large ones.
Problem
Whether LLMs can reason over ranked preferences and execute structured algorithms such as deferred acceptance in two-sided matching markets, especially as market size grows.
Approach
Builds a graded benchmark of matching-market tasks (generation, instability detection and resolution, preference queries) over synthetic Impartial Culture and Master-list profiles at three sizes, and tests LoRA fine-tuning on synthetic reasoning traces to see whether it closes the gap on larger instances.
Key results
- Gemini-2.5-Pro achieves 68.33% stable solutions in generation and 61.33% in instability resolution on average, the highest among evaluated models.
- On Hard instances all models essentially fail to generate stable matchings, while Qwen-QwQ-32B fine-tuned with LoRA reaches 100% stable solutions on Easy and Medium instances.
- LoRA fine-tuning raises Qwen-QwQ-32B preference-reasoning accuracy on Hard instances to 99.00% from 91.67%, while Hard stable-solution generation stays at 0%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Fine-tune Qwen-QwQ-32B with LoRA on synthetic reasoning traces | Qwen-QwQ-32B · Stable matching generation, Easy | stable solutions (%): 83.0 -> 100.0 | Helped |
| Fine-tune Qwen-QwQ-32B with LoRA on synthetic reasoning traces | Qwen-QwQ-32B · Stable matching generation, Medium | stable solutions (%): 24.0 -> 100.0 | Helped |
| Fine-tune Qwen-QwQ-32B with LoRA on synthetic reasoning traces | Qwen-QwQ-32B · Stable matching generation, Hard | stable solutions (%): 0.0 -> 0.0 | No clear effect |
| Fine-tune DeepSeek-8B with LoRA on synthetic reasoning traces | DeepSeek-8B · Stable matching generation, Easy | stable solutions (%): 3.0 -> 64.0 | Helped |
| Fine-tune DeepSeek-8B with LoRA on synthetic reasoning traces | DeepSeek-8B · Stable matching generation, Medium | stable solutions (%): 0.0 -> 31.0 | Helped |
| Fine-tune DeepSeek-14B with LoRA on synthetic reasoning traces | DeepSeek-14B · Stable matching generation, Easy | stable solutions (%): 19.0 -> 51.0 | Helped |
| Fine-tune DeepSeek-14B with LoRA on synthetic reasoning traces | DeepSeek-14B · Stable matching generation, Medium | stable solutions (%): 0.0 -> 41.0 | Helped |
| Fine-tune DeepSeek-14B with LoRA on synthetic reasoning traces | DeepSeek-14B · Stable matching generation, Hard | stable solutions (%): 0.0 -> 0.0 | No clear effect |
| Provide the deferred-acceptance algorithm in the prompt (ablation) | LLMs generating stable matchings · Stable matching generation, Medium and Hard | stable solutions (%) | No clear effect |
| Use CoT or few-shot prompt enhancements (ablation) | LLMs generating stable matchings · Stable matching generation, Medium and Hard | stable solutions (%) | No clear effect |
| Frame matching as task scheduling instead of stable marriage (ablation) | Gemini-2.0-Flash and o3-mini · Stable matching generation | stable solutions (%) | No clear effect |
| Specify strong or super stability in the prompt for preferences with ties (ablation) | Gemini-2.5-Pro · Stable matching generation with ties | stable solutions (%) | Hurt |
Surprising findings
- Resolving instability performs no better, and often worse, than generating stable matchings from scratch, and advanced models often introduce additional blocking pairs when fixing a one-blocking-pair matching.
- Basic non-advanced models hallucinate blocking pairs, biasing them toward classifying matchings as unstable.
Limitations
- Relies on synthetic preference profiles rather than real-world preference data.
- Only complete strict preferences in the main evaluation; ties are explored only preliminarily in the appendix.
- LoRA fine-tuning does not improve Hard instances, and full-parameter tuning or RL were not tested.
Experimental setup
Datasets: synthetic Impartial Culture and Master-list preference profiles
Benchmarks: Matching Dataset (2850 questions)
Metrics: stable solutions (%) instability rate optimality rate accuracy (%)
Baselines: Llama-3.3-70B Gemini-2.0-Flash Qwen-QwQ-32B DeepSeek-70B o3-mini DeepSeek-R1 Gemini-2.5-Pro
Builds on: deferred acceptance algorithm LoRA
Closest papers by meaning
- The Shadow Price of Reasoning: Economic Perspective on Optimal Budget Allocation for LLMs (ICML 2026 · similarity 0.88)
- Aligning with Logic: Measuring, Evaluating and Improving Logical Preference Consistency in Large Language Models (ICML 2025 · similarity 0.87)
- Agentic Multi-Turn Reasoning: A Fairness Approach (NeurIPS 2026 · similarity 0.87)
- GTBench: Uncovering the Strategic Reasoning Capabilities of LLMs via Game-Theoretic Evaluations (NeurIPS 2024 · similarity 0.87)
- Investigating Non-Transitivity in LLM-as-a-Judge (ICML 2025 · similarity 0.87)
- Sample Smart, Not Hard: Correctness-First Decoding for Better Reasoning in LLMs (ICLR 2026 · similarity 0.87)
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.