Matching Markets Meet LLMs: Algorithmic Reasoning with Ranked Preferences
combinatorial domainsfine-grained preference queriesinstability detectioninstability resolutionlarger-context inputsmatching marketsparameter-efficient fine-tuningpreference-based reasoningprogram synthesisranked preferencesreasoning tasksresource allocationscientific hypothesis generationstable outcomesstructured algorithms
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