# Matching Markets Meet LLMs: Algorithmic Reasoning with Ranked Preferences

arXiv: https://arxiv.org/abs/2506.04478 · HTML: https://mlsanity.com/paper/2506.04478/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 42 of its 70 references that are in the map.
- First posted on arXiv 4 Jun 2025.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 30 of 42)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Measuring Massive Multitask Language Understanding](https://mlsanity.com/paper/2009.03300/) (2020)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Constitutional AI: Harmlessness from AI Feedback](https://mlsanity.com/paper/2212.08073/) (2022)
- [Scaling Instruction-Finetuned Language Models](https://mlsanity.com/paper/2210.11416/) (2022)
- [Solving Quantitative Reasoning Problems with Language Models](https://mlsanity.com/paper/2206.14858/) (2022)
- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [WizardCoder: Empowering Code Large Language Models with Evol-Instruct](https://mlsanity.com/paper/2306.08568/) (2023)
- [GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Models](https://mlsanity.com/paper/2410.05229/) (2024)
- [Improve Mathematical Reasoning in Language Models by Automated Process Supervision](https://mlsanity.com/paper/2406.06592/) (2024)
- [Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Models](https://mlsanity.com/paper/2503.09567/) (2025)
- [From System 1 to System 2: A Survey of Reasoning Large Language Models](https://mlsanity.com/paper/2502.17419/) (2025)
- [Toward Self-Improvement of LLMs via Imagination, Searching, and Criticizing](https://mlsanity.com/paper/2404.12253/) (2024)
- [Self-Discover: Large Language Models Self-Compose Reasoning Structures](https://mlsanity.com/paper/2402.03620/) (2024)
- [Social Choice Should Guide AI Alignment in Dealing with Diverse Human Feedback](https://mlsanity.com/paper/2404.10271/) (2024)
- [Chain of Preference Optimization: Improving Chain-of-Thought Reasoning in LLMs](https://mlsanity.com/paper/2406.09136/) (2024)
- [LLM Voting: Human Choices and AI Collective Decision Making](https://mlsanity.com/paper/2402.01766/) (2024)
- [MuggleMath: Assessing the Impact of Query and Response Augmentation on Math Reasoning](https://mlsanity.com/paper/2310.05506/) (2023)
- [Generative Social Choice](https://mlsanity.com/paper/2309.01291/) (2023)
- [Investigating Non-Transitivity in LLM-as-a-Judge](https://mlsanity.com/paper/2502.14074/) (2025)
- [ReSo: A Reward-driven Self-organizing LLM-based Multi-Agent System for Reasoning Tasks](https://mlsanity.com/paper/2503.02390/) (2025)
- [Enhancing Reasoning Capabilities of LLMs via Principled Synthetic Logic Corpus](https://mlsanity.com/paper/2411.12498/) (2024)
- [The CLRS-Text Algorithmic Reasoning Language Benchmark](https://mlsanity.com/paper/2406.04229/) (2024)
- [DSGBench: A Diverse Strategic Game Benchmark for Evaluating LLM-based Agents in Complex Decision-Making Environments](https://mlsanity.com/paper/2503.06047/) (2025)
- [LogicGame: Benchmarking Rule-Based Reasoning Abilities of Large Language Models](https://mlsanity.com/paper/2408.15778/) (2024)
- [Accelerated Preference Elicitation with LLM-Based Proxies](https://mlsanity.com/paper/2501.14625/) (2025)
- [Distributive Fairness in Large Language Models: Evaluating Alignment with Human Values](https://mlsanity.com/paper/2502.00313/) (2025)

## Built on by (most cited first, 2 of 2)

- [Virtual Agent Economies](https://mlsanity.com/paper/2509.10147/) (2025)
- [From Preference to Reciprocity: Decentralized Matching with Empirically Grounded LLM-agent Based Modeling](https://mlsanity.com/paper/2609.34679/) (2026)

## Abstract (arXiv)

The rise of Large Language Models (LLMs) has driven progress in reasoning tasks -- from program synthesis to scientific hypothesis generation -- yet their ability to handle ranked preferences and structured algorithms in combinatorial domains remains underexplored. We study matching markets, a core framework behind applications like resource allocation and ride-sharing, which require reconciling individual ranked preferences to ensure stable outcomes. We evaluate several state-of-the-art models on a hierarchy of preference-based reasoning tasks -- ranging from stable-matching generation to instability detection, instability resolution, and fine-grained preference queries -- to systematically expose their logical and algorithmic limitations in handling ranked inputs. Surprisingly, even top-performing models with advanced reasoning struggle to resolve instability in large markets, often failing to identify blocking pairs or execute algorithms iteratively. We further show that parameter-efficient fine-tuning (LoRA) significantly improves performance in small markets, but fails to bring about a similar improvement on large instances, suggesting the need for more sophisticated strategies to improve LLMs' reasoning with larger-context inputs.