Matching Markets Meet LLMs: Algorithmic Reasoning with Ranked Preferences
Hadi Hosseini, Samarth Khanna, Ronak Singh
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 seven 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 \textit{parameter-efficient fine-tuning} (LoRA) improves performance on large instances but degrades accuracy in small markets, suggesting a scale-dependent trade-off between generalization and overfitting.