Matching Markets Meet LLMs: Algorithmic Reasoning with Ranked Preferences
Authors: Hadi Hosseini
Samarth Khanna
Ronak Singh
Venue: NeurIPS 2025 poster ()
Keywords: Preference reasoning
matching markets
stability
comprehension
Primary area: deep_learning

Abstract: 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 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.

Matching Markets Meet LLMs: Algorithmic Reasoning with Ranked Preferences
Hadi Hosseini Penn State University, USA hadi@psu. edu
Samarth Khanna Penn State University, USA samarth. khanna@psu. edu
Ronak Singh Penn State University, USA ronak. monakssinghpsu. edu
Abstract
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- a-tthe-art models on hierarchy of preference-based reasoning tasks tasks- from stable-matching generation to instability detection, instability resolution, and fine- grained preference queries- 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-effiiien fine-tuning (LoRA) significantly improves performance small markets, but fails to bring about similar improvement in large instances, suggesting the need for more sophisticated strategies to improve LLMs' reasoning with larger-context inputs.
Data and Code:
Introduction
The emergence of Large Language Models (LLMs) has positioned them as integral components in wide range of reasoning-intensive tasks such as program synthesis, logical inference, mathematical problem solving, and scientific hypothesis generation, highlighting the importance of structured problem-solvine capabilities. Despite their recent success in symbolic and logical reasoning, their capacity to reason over ranked preferences and to execute structured algorithms within combinatorial domains remains largely unexplored. Preference reasoning constitutes a foundational component in numerous domains, including economic contexts e.g.. auctions, voting systems, and market design-and and the architecture of pre-trained generative models using Reinforcement Learning from Human Feedback (RLHF) capture and internalize human value judgments. These methods often have to execute algorithms on a large number of preference lists (either pairwise, partial, or complete rankings) aggregate the rankings through constitutional Al or social choice theory 15
Despite substantial progress, reasoning over preferences remains a non non-trivial endeavor: ensuring transitivity [64] [75]. accurately augmenting ordinal rankings [23). and achieving coherent value alignment pose significant challenges. Without robust mechanisms for preference elicitation and the capacity execute the requisite combinatorial procedures, even state-of-the-art LLMs may produce outputs that diverge from true human preferences 33 or fail to satisfy desirable properties (24..
We consider matching markets, domain that constitutes fundamental class of problems underlying diverse applications-frov healthcare resource allocation to ride-sharing platforms and recommender
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Proforence Profies
Syntheecaly
O
Gorneeting Bistr Rabdines
Iestonoo Dificclly in corker 201e)
PAlkn Survenis of Defiered Accoptance
mwctee.....
Pistie
eipcrsene le pigueess und
LoRA Fice. Funiin
Ploties Sine hwned
Dot 300--0
Oetacting Intraili
deopsock
QwQ
Protiee
Fronpe de didertiee
Wedoo
Duark QweEcAR Qvves 320
Preference
Colire Rondee
Prefeissio Comprrahastinn
Sumping 50 0585 20G
Mescettllacces ieprovamunt
Sopperpes
Mackerorr Ad on SNT Mechco
(ipin))
Ogant wil Age Lono
Figure I: The framework for reasoning with ranked preferences through matching markets.
systems-and demand accurate comprehension of individual preferences and reconciliation of conflicting choices to guarantee system-wide stability. Matching markets are an ideal testbed for studying reasoning in AI models for two key reasons: First, they provide a structured platform for evaluating reasoning over ranked preferences and algorithmic thinking. They provide a framework that is axiomatically rich yet computationally tractable where solution quality (e.g.. stability and efficiency) can be rigorously evaluated. Second. LLMs are increasingly utilized as black-box systems in variety of economic, social, or medical settings to inform automated screening in recruitment pipelines 28), investigating market behavior [39], market clearing in ride-hailing platforms [42), and in general simulating economic interactions 32) This makes it imperative to evaluate their ability in terms of computing "desirable" solutions from stakeholders' preferences. Additionally, their potential to serve as interfaces between stakeholders and established black-box systems (e.g., the National Residents Matching Program (61]) requires benchmarking their ability to reason about provided solutions and address aspects that users might find undesirable.
1.1 Our Results
We focus on four preference-based tasks: (i) generating stable solutions, requiring LLMs to produce stable matchings directly from ranked inputs, (ii) instability resolution, demanding preference reasoning to transform unstable matchings to stable ones, (iii) instability detection, in which models detect blocking pairs within a proposed solution, and (iv) preference reasoning, assessing nuanced query answering over ranked lists. We evaluate seven large language models with varying reasoning capabilities, including basie models, those with some limited reasoning, and advanced reasoning models. Our methodology and results are summarized in Figure
Benchmark. We introduce a benchmark with instances and questions aimed at evaluating the above tasks involving reasoning over ranked preferences. These tasks are categorized into three levels of difficulty- Easy, Medium, and Hard based on problem size. Each task utilizes ranked preferences sampled from two statistical distribution models: Impartial Culture (IC) and Master- list (ML).
Generating Stable Solutions. Although models with advanced-reasoning capabilities generally outperform other LLMs on Easy and Medium instances, all models struggle to generate stable solutions on Hard instances-indicating that the combinatorial reasoning capability of L.LMs does not necessarily extend to larger-context inputs. Interestingly, the fraction of invalid and failed solutions significantly lower for models with higher reasoning abilities, indicating their understanding of constraints, despite their inability to perform precise and step-by-step reasoning with preferences.
Instability Detection and Resolution. We find that LLMs frequently make mistakes in determining whether solutions are stable, with hallucinations about blocking pairs being the most common among basic models. Additionally, LLMs' ability to correct unstable solutions is (at best) good their ability to generate them from scratch, in some cases making the provided incorrect solutions worse.
Preference Reasoning, We consider tasks based on three levels of inference over ranked preferences. Large language models with advanced reasoning capabilities generally demonstrate strong com- prehension of preferences across levels of inference. However, even small errors compound in tasks

---

requiring multi-step sequences of reasoning (e.g., generating stable solutions or resolving instability), or in other words, small errors multiply!
Supervised Parameter-Efficien Fine- Taning.nngg We demonstrate that fine-tuning an open-source reasoning model using synthetically generated reasoning traces substantially improves performance, significantly outperforming advanced-reasomie models on Easy and Medium instances. However, we find that this approach does not address the challenges LLMs face with large inputs (Hard).
1.2 Related Work
Reasoning Capabilities of LLMs. Mathematical problem solving has been key area of focus in evaluating the reasoning ability of LLMs, through a variety of benchmarks such as [14] 30 31 57] LLMs have also demonstrated remarkable capabilities on coding benchmarks such as SWE- Benchhh
41 and CodeForces. As SOTA benchmark scores improve, recent work studies whether these improvements reflect genuine logical reasoning through benchmarks assessing logical consistency [29). Furthermore, the recent rise of LLM agents has increased interest in benchmarking LLMs' causal reasoning [[2] and strategic planning abilities
50 and rule
20 40 [66] Additionally, the emergence of reasoning models has led to benchmarks evaluating
these models' improved reasoning and planning abilities
10 49
Enhancing Reasoning Capabilities of LLMs. Specialized prompting strategies like Chain-of- Thought (CoT)) (72), Tree-of-Thought (ToT) (77). and Graph-of-Thought (GoT) (3] have performance
abilities on a variety of reasoning benchmarks. Fine-tuning has also been demonstrated to improve CoT in model outputs (78), as well as economic rationality [T]] and abstract reasoning 774] Addi- tionally, instruction-tunin tuningg has been shown to enhance reasoning in several works [8]
48 51 7T].
More advanced techniques build upon CoT 668 80), or utilize multi-agent architectures that leverage cooperative LLMs [69| [7].. More recently, reinforcement-leamee model reasoning, the most popular example being the Deepseek-R. R1 reasoning model [T7].
(GRPO) has been used to improve
LLMs in Social and Economic Decision Making. While still an emerging area of research, multiple works have focused on the collective decision- maaiing capabilities of LLMs. One particular area of interest is the use of LLMs in preference elicitation [35] 655. Fish et al. [24] benchmark the ability of models learn and strategize in unknown economic environments using deliberate exploration. Another notable avenue of work is the study of how well LLMs can represent humans in collective decision-making, an understudied component of LLM alignment 33 76
2 Methodology
2.1 Problem Formulation
A two-sided matching market consists of two disjoint sets of agents (e.g., riders and drivers, freelancers and job requesters, and content creators and ads) denoted by M and W, where |M] = |W] = n. The preference list of an agent i, denoted by >;, is ranked order list over the agents on the other side. A preference profile, >, denotes the collection of preferences of all agents. We write w1 >m W2 and mi > w m2 denote that m prefers Wi to W2 and w prefers my to m2 respectively. In this paper, we primarily consider the standard model, which assumes a complete and strict preference list (no ties) and aims at finding a one-to-one matching between the agents in two sets
Matching and Stability. A matching is a function μ M U W + M U. such that f((m) E W for all m M, p(w) E M for all w W, and µ(m) w if and only if μ(w)) m. Given matching j,, a blocking pair with respect to the preference profile > is pair (m, w) who prefer each other over their assigned partners in μr, i.e., w 7m (um) and m >> ((w).. A matching is said to be stable if it does not have any blocking pairs. Given an instance of the problem. the set of all possible stable solutions forms a distributive lattice and can be exponential in size 45
In their seminal work, Gale and Shapley 27 proposed an iterative procedure the deferred accep- tance algorithm (DA) that always guarantees to find stable solution. It proceeds by series of proposals and rejections. In the initial proposal phase, each of the unmatched agents on one side (aka proposers) proposes to their favorite agent from the other side (aka receivers) according to their
'Thi is the standard model considered by the seminal works of Gale and Shapley 27 and Knuth 445
3

---

preference list. In the subsequent rejection phase, each agent on the receiving side tentatively accepts its preferred proposal, rejecting the others. The algorithm terminates when no further proposals can be made. The details of this algorithm can be found in Appendix [ The underlined solution in Example T is simultaneously optimal for the proposing side and pessimal for the receiving side [56]. We refer to the former as the Optimal matching and the latter as the Pessimal matching.
Example 1 (An instance with multiple stable solutions.). A preference profile for a sample instance of size 4; underlined agents indicate the Optimal matching, the Pessimal matching is indicated with a , and the i indicates a stable matching that is different from the forst two.
1T u14
W1 W2
wt 1/
m11
1764
m2 M%
w
w2
201
W2 : m
mg
m
1701
mg W1
w
W2
Ws : mi
my
7711
1722
m4 W1
w
W4
w4: m4
mg
mg
m1
2.2 Dataset, Models, and Setup
Preference Instances. We synthetically sample set of 300 preference profiles, partitioned into three sets of 100 instances for each difficulty level, namely Easy (n = 10 agents on each side of the market), Medium (n 20), and Hard (n 50). The preference profiles
sampled from two types of distributions Impartial Culture (IC) and Master-list (ML), each constituting 50 questions at each difficulty level. An impartial culture (IC) is a well-studied probabilistic model for generating preference profiles in which every agent's ' strict preference ranking is drawn independently and 22 It has been extensively studied in the context of economics, matching, 9 [70]. A profile with a master-list (ML) is a highly structured preference profile in which all agents on one side of the market share exactly the same striet ranking over the agents on the other side. They represent the homogeneity in settings ranging from the labor market to organ allocation in healthcare 6 38 While an arbitrary instance generated by IC may admit
uniformly random 4
and voting theory 5
exponentially many stable solutions 45 with a Master- list, only a single unique stable solution exists. indicating a difficulty level proportional to the size of the space of stable outcomes. In Appendix C we discuss a simpler version of the DA algorithm for computing stable solutions with ML instances.
Matching Dataset. We curate dataset comprising 2850 questions derived from the instances described above. These questions cover four task categories, each applied to the same pool of profiles to ensure consistency: (i) generating stable solutions, given a preference profile (300 questions); (ii) instability resolution, given a profile and an unstable matching; (iii) instability detection, given a profile and solution (1050 questions); and (iv) preference reasoning, given single preference list or a profile (900 questions).
Models. We select representative suite of both open-source and closed-source models for evaluation. Since our benchmark is based on a reasoning task, we categorize models by their reasoning ability. We evaluate two basic models (those not specifically trained for reason- ing), namely Llama-3.3-708B (21] and Gemini-2.0-Fllash [60] and five reasoning models, namely
Owen-QwQ-322 (77. DeepSeek-700 (Llama-distilled) [17. OpenAl 03-mini [59) DeepSeek-RI
17]. and 2emini-2.5-Pro [16]. Among reasoning models, we classify the last three as advanced reasoning models, based on their SOTA performance on reasoning benchmarks [49].
The prompt for each task consists of the preference profile for a given instance, followed by task-specific instructions (e.g., computing the "proposer-optimal"" matching, or resolving given unstable matching). While we adopt the stable-marriage setting, considered by Gale and Shapley [27), where men propose women, show (in Appendix [ that the results do not change if different setting- where workers are assigned tasks is used. scale up the verification of solution correctness, we instruct LLMSs to adhere to a predefined answer format. Additionally, we allow LLMMs two re-tries to correct solutions that are either invalid, partial, or do not adhere to the specified format. See Appendix for details about the inference setup, and Appendix [ for sample prompts.
Prompting.
2.3 Evaluation Criteria
We consider several metrics for evaluating the quality of returned responses depending on the task. To account for cases in which LLM outputs violate task requirements, categorize responses into

---

Stable (Corecc)
Unstable
Partial
Invalid
Fall
100
Purcentage of Responsess
40
20
mrea commii top
cuet ae
moce you
combint
Ma-aasy
Easy
ML Medium
Mcdiedi
ML Hard
IC Hard
Figure 2: The generated responses by LLMs with Master-list (ML) and Impartial Culture (IC) preferences at different difficulty levels. Stable indicates one-to-one matchings with no blocking pairs; otherwise is unstable. Invalid do not adhere to one-to-one constraint, partial are one-to-one but leave some unmatched, and Fail indicates models' failure to return any matching.
the following types: A solution is invalid if some agent from one side is matched to more than one agent from the other side. It is partial if it is invalid, but some agents remain unmatched. A matching is stable if it is perfect one-to-one matching that admits no blocking pair. Otherwise, it is unstable if it matches all the agents but admits blocking pair. The following metrics apply primarily to valid responses. Informally, these metrics measure the distance from reference stable outcome.
Instability Rate (IR): The instability rate measures the proportion of agents involved in blocking pairs, and thus the degree to which a matching violates the stability criterion. Given a complete matching, instability rate measures the percentage of unstable agents, i.e., those involved in at least [[i MUW >()()) > ((())) for some jE MUW)|
one blocking pair. Formally, IR(H, [))
2n
This rate assesses the overlap between the model's matching and reference stable matching, thereby capturing how closely the model's s output mirrors the stepwise proposals and acceptances of canonical algorithm. Formally, given two perfect matchings, P and n², in one-to-one market where each matching is viewed as a set of unordered pairs between agents, the Jaccard similarity is defined as [S, ft') stable matching as its similarity to the proposer-optimal stable solution, which is unique.
Aptimality/Pessimalii Rate:
|aПμ'l |aUn"] Then, we define optimality rate (OR) of
3 Generating Stable Solutions
The first task involves evaluating LLMs' abilities to generate valid, stable matchings in markets with various difficulty levels. This task ideally requires models to reason over ranked preferences while iteratively executing a structured algorithm.
We consider two sub-categories for generating matchings depending on declarative knowledge about algorithms: i) prompt without specifying any algorithm, and ii) prompt with exact step-by-step instructions on how to execute the DA algorithm 27 (see Section 2.T for details). Our ablation studies showed that the above prompting strategies did not result in qualitatively different outcomes, as all models were able to correctly identify the requirement for considering preferences, the DA algorithm, and its execution steps The detailed results are presented in Appendix D
Difficulty, Model Size, and Reasoning. Figure demonstrates the performance the models in generating stable outcomes. Baseline models without explicit reasoning mechanisms unable to solve even Easy instances, whereas eooooiingennaledd models achieve high accuracy on Easy instances but suffer dramatic performance drops on Hard instances. Furthermore, for Hard problems, even reasoning models frequently produce invalid outputs or fail to return any solution. Interestingly,
Furthermore, converting the mableemarriage setting to a task-scheduling setting (24. where "men" and "women" are replaced by "workers" and "tasks" (respectively), does not have significant impact performance.
5

---

100
10
80
Oyemelty Sate
0.
Span Seaeaia del
Figure 3: Instability Rate (lower is better) within unstable outcomes returned by each model as compared to randomly selected valid (but not nec- essarily stable) solutions (Random).
Optimality Rate within unstable out- comes returned by each model compared to randomly selected valid (but not necessarily sta- ble) solutions (Random).
Figure 4:
Qwen-QwQ-32B significantly outperforms much larger model, DeepSeek-70B, indicating that LLMs' combinatorial reasoning capability does not necessarily scale with model size
IC vs. ML Profiles. Under Impartial Culture (IC) profiles, the number of stable solutions can grow exponentially as the problem scales (increase of n) [45). This combinatorial explosion poses a significant challenge for LLMs attempting to identify stable solutions, especially when solely using implicit reasoning over preference lists (without executing concrete matching algorithm). In contrast, mister-list profiles iirespreeeeettve of the underlying sampling method used to generate preferences admit exactly one stable solution. Moreover, this unique stable matching can be constructed in (n) steps by (i) extracting the common Master-list and then (ii) pairing agents in order of their shared priority 38 See the details of the algorithm in Appendix
We observe that there is significant performance gap between ML and IC instances this disparity especially marked for DeepSeek-R1. With IC profiles and Hard instances, all models are unable to compute stable solution They perform slightly better under ML profiles, and while this performance drops for Hard instances, these models almost never return invalid or partial matchings.
Prompting Techniques. Prompt-engineering techniques have been empirically demonstrated to enhance the performance of LLMs mathematical reasoning and formal logic inference tasks 72 We evaluated a range of prompt-engineerin techniques- scchiquess-includnng few-shot prompting and Chain-of-Thoughh (CoT) prompting, which supply exemplar "thought processes" and intermediate reasoning steps-in in an attempt to bolster LLM performance. However, none of these strategies qualitatively improved medium- or hard-difficllyy instances. See Appendix D for further details.
3.1 Measuring Instability
natural question is how far LLMM-pooduee responses deviate from stable outcomes. To quantify this, two complementary metrics: instability rate and optimality rates (see Section (2.2). The instability rate directly reflects the distance from any stable solution, whereas the optimality rate implicitly evaluates the model's success in executing the underlying matching procedure. Figure and Figure 4 illustrate comparisons of LLMs with a baseline randomly generated outcomes
Broadly, the advanced-reasoning models generate significantly closer approximations to stability and optimality than their non-reasoning counterparts. Moreover, all evaluated LLMs (regardless of reasoning sophistication) substantially outperform random baselines on both metrics, indicating that they inherently leverage preference structures and exhibit nontrivial reasoning about ranked inputs.
Interestingly, the performance distinction between basic and reasoning models becomes less clear. While the intermediate reasoning models return lower instability rate Easy and Medium problems, their performance significantly drops in larger-scale scale problems (Hard). In fact, the performance of DeepSeek-7001 becomes worse than even basic non-reasoning models. We attribute this behavior to
'Trroughout the paper, all statistical comparisons between the percentages of stable solutions returned (across LLMs or across treatments) are done using Fisher's 's Exact test (25). Similarly, any two distributions of Instability or Optimality Rate are statistically compared using Welch's T-test 7
4 'Gemini-2.5-Ppi P-r the only model with a positive success rate (= 8%) with IC preferences Hard instances. 'Note that the plots only illustrate unstable but valid one-to-one outputs.

---

Table 1: The percentage of stable matchings returned when tasked with resolving instability starting from One-BI or Random matchings. The numbers in bold represent the highest accuracy (across all LLMs) of resolving the corresponding type of unstable matching.
Baic LLMs
Reaseiing LLMs
Advaseed Bensesinn LLMs
Desplrde-U8
DeplinskRi
Geminni----he
Diliiolly
Preferasce
OueBP
Rusdoe
Oue-PP
Randknn
Oze-IP
Ransaan
Oxe-IP
Rasden
CheaBP
Randien
One
Ransher
Ose-BP
Rasalens
Bayr
I0
ML.
60
88
76
36
66
d6
62
54
Iee
96
199
10
56.
96.
Medium
10
M1.
33
17
21
10
64
64
26
88
82
74
60
Hladd
MT.
130
66
033
000
3081
3516
310
300
1900
57.0
5667
5067
01.3
the model's diminished capacity for handling larger input lengths, hypothesis supported by their lower proportion of valid outcomes (as seen in Figure
4 Resolving Instability
Generating stable solutions requires both exact reasoning over agents' preference lists and the execu- tion of stability-guaranteeing procedure (e.g., the DA algorithm). As demonstrated in Section 3 all evaluated models cadblls-iresspettiv of their reasoning capabilities-ertt exhibit severe performance degra- dation as the problem size grows. This leads to the natural question of whether these models can resolve instability given matching a task that entails detecting blocking pairs through preference reasoning and applying an appropriate sequence of adjustments to restore stability.
We provide LLMs with unstable (but valid) matchings along with preference profiles, and instruct them to convert these initialized solutions to stable matchings. To assess how the instability rate may influence solution quality, we distinguish two classes of initial matchings: (i) One-BP, matchings containing exactly one blocking pair (i.e., "almost stable") such that their stability may be resolved through simpler proposal-rejection iterations, and (ii) Random, matchings sampled uniformly random from the set of all valid one-to-one pairings. which typically contain a large number of blocking pairs and thus exhibit high degrees of instability. See Appendix F for detailed steps and pscudo-code for generating one-BP and random initialization. Note that starting from an arbitrary matching, sequentially resolving blocking pairs may result in a cycle as shown by Knuth [44]
However, random sequence converges to stability with probability one [ 62].
Table I displays the fraction of responses in which LLMs return stable matchings when asked to resolve the above types of unstable matching. Surprisingly, our experiments illustrate that in the task of resolving instability, the performance of all evaluated models does not exceed-and even degrades- their performance in generating stable solutions. This behavior persists regardless of initial matchings (One-BP or Random) and LLMs' reasoning capability. In fact, on Hard instances, the output returned by advanced reasoning models on One-BP matchings (i.e., containing single blocking pair) contains substantially more than one blocking pair. In other words, even for the most basic instances, LLMs often introduce additional instabilities beyond the original single violation. We elaborate on this in Appendix demonstrating how all models, including those with advanced reasoning, often return solutions with higher instability rate, highlighting their inability to systematically eliminate blocking pairs in accordance with preference lists.
5 Detecting Instability
The findings in previous sections raise the question of whether LLMs can reliably detect instability in a given matching simpler task that involves iterating over each unmatched pair to determine whether both agents prefer one another over their assigned partners. This procedure entails only straightforward comparison of preferences and requires Onn?) steps.
For this task, we evaluate the performance of valid one-to-one matchings initialized under two instability conditions: (i) One-BP, representing nearly stable matchings containing a single blocking pair, and (ii) Random, representing highly unstable matchings with numerous blocking pairs. To detect malse-positives we additionally include two extreme cases of stable matchings: the proposer-optimal (Optimal) and the pooposer-psssinge (Pessimal) stable solutions.
7

---

Impartial Culure
Gemini22.u O-flash
Llama-3.-7788
DeepSieek-70B
Twen-QwQ:332
04-63-mini
DeepSeek-R1
Gemini-2.5-PP
20
24
64
20
20
20
75
92
96
92
25
100
92
90
92
100
-100 100
100
200
100 100 100
100
-100 100
94
100
300
Size
70
22
80
94
100
100
MB
100
82
100
93
-00
Master-list
10
100
100
100
100
100
100
S2c
20
90
96
80
80
100
54
54
86
100
96
96
100
98
98
80
100
50
90
100
50
80
95
94
54
54
36
86
23
28
32
102
82
82
50
36
68
50
100
86
58
Optinal
Passemal
Randtm
Optemal
Pestions
Randon
Optimal
Prxtimal
Ramdom
Optional
Postenal
Rannfo
Optinal
Passenal
are-g
Randmm
Oatenal
Postinal
dre-g
Rardii
Optonal
Pertonal
Figure 5: The fraction of responses where each model correctly detects stability or instability of given matching.
Reasoning Models: Preferences and Blocking Pairs. Figure 5 reveals an interesting observation about reasoning models: their performance is influenced by the number of blocking pairs in the matching being wvaluated-simiae to the observations in Section 4 They achieve a high accuracy on identifying random matchings (which have a larger number of blocking pairs) as unstable and a significantly lower accuracy with matchings that have at most one blocking pair.
Basic Models and Hallucination. Interestingly, the non-reasoning models achieve a high accuracy (80%) with both types of unstable matchings, and extremely low (20%) accuracy with stable match- ings. Note that the performance across all models is qualitatively similar in ML and IC profiles, even though each ML profile admits a unique stable solution (thus, identical reports for Optimal and Pessimal). See Appendix for further analysis. A manual analysis of non-reasoning models uncov- ers frequent hallucinations about blocking pairs, resulting in systematic bias toward classifying matchings as unstable. This can be largely attributed to misinterpretations of the input preferences.
Reasoning about Ranked Preferences
Many advanced reasoning paradigms, ranging from causal inference [12 and counterfactual analysis to game-theoretic decision making, depend fundamentally on the ability to compare and evaluate alternative choices. As demonstrated thus far, even advanced reasoning models often fail to execute the step-by-step procedures of combinatorial algorithms when those procedures operate over ranked preference lists. This shortcoming motivates the question of whether current LLMs can truly reason about preferences, as opposed to merely applying preferences in generating responses hcuristically.
To investigate preference comprehension, we introduce a suite of tasks spanning three levels of inference over ranked preferences: (i) basic retrieval (L1), in which models must extract individual preference relations; (ii) comparison queries (L.2), requiring pairwise preference judgments; and (iii) paapossl-acceptane simulations (L3), which combine comparison of alternatives with binary accept/reject decisions mirroring the dynamics of deferred-acceeptacce algorithms.
Hierarchical, level-wise reasoning evaluations have been proposed recently in domains such causal inference of LLMs [12). For example, an L1 question is "Who is agent W5's, 4th-most preferred agent?", and an L2 question "Would agent W5, prefer M8 over M7?"
aama- 700
Gemini-2 oFFass
Dee3Ceek:200
Qeen-Gw0--3 -22
D4-03-mir
DeepSeri-R1
Gemiri 2.5.
100
Easyy
68
67
99
56
65
100
100 100
59
100 98
100
38
97
100
100 90
100
100
Diffculty
Medium
39
71
85
50
51
96
99
100
100
100
100
100
96 100 100
87
-100 100
100
Harr
60
23
74
98 100
99 99
12
Figure 6: Accuracy on questions about provided preferences, with both IC and ML instances.
Basic models have low accuracy in levels of difficulty even on small instances, which probably the reason behind their inability to compute or detect stable solutions (as discussed in Section
8

---

and Section 5). In basic models (e.g., Llama-3.3-70B) and (non-advanced) reasoning models (e.g.. DeepSeek-70Bi) the size of the problem has a greater impact on accuracy as compared to the level of the question, indicating their difficulty of handling larger inputs. Although advanced-reasoning models have significantly higher aceuracy rates compared to other models, they still make minor errors, especially in larger profiles (Hard). Generating stable solutions for these instances often requires a larger number of reasoning steps over many preference lists, causing minor errors to compound (small errors multiply!).
7 Performance Improvement through LoRA Fine-Tuning
Supervised fine-tuning has proven to be effective in enhancing the reasoning capabilities of LLMs in a variety of tasks, including mathematical problem solving [3 logical reasoning [58], and code generation [52]. Markeeva et al. [55] demonstrate how fine-tuning a small LLM (2B parameters) can significantly improve LLMs' ability to execute textbook algorithms (e.g.. sorting an array, finding the shortest path between two nodes a graph, etc.). Hence, we evaluate whether fine-tuning can be used to enhance L.LMs ability to compute stable matchings- task requiring reasoning over ranked preferences in addition to algorithmic understanding. To this end, we perform LoRA fine-tuning and two smaller models, DeepSeek-88 and DeepSeek-14p for Generating Stable Solutions task. Additionally, we also evaluate whether fine-tuning can mitigate errors made by LLMs in the Preference Reasoning task (Section 6).
(34] on three reasoning models, including Dowen-QwQ-e
Training. Let D
y100) be the fine-tuning dataset for a given task. Each pair consists of x()) and the desired model completion y()) The input instance x(() is made up of four components: (i) a generic system-
an imput instance
s, (ii) a high-level instruction u, (iii) the preference profile p and (iv) the task- bask-prompt t(), The desired completion y(() consists of two components, (i) a chain-of-thought reasoning trace ((), and (ii) the answer ( in the desired format. Each model is fine-tuned with standard next-token cross-entropy on the concatenated sequence (8) = x( (ly(), We separately finetune each model for the Generating Stable solutions task (N = 10, 000) and the Preference Reasoning task (N 9, 000). See Appendix [H] details of the fine-tuning setup and results from experiments with different hyperparameter values.
Improvement. Fine-tuning LLMs with data containing synthetically generated reasoning performance on both tasks, as evidenced in Table
traces substantially improves their In fact, this approach enhances the performance of Owen-QwQ-32BB a (non-advanced) reasoning model, to a success rate of 100% in computing stable matchings with both Easy and Medium instances, significantly out- performing advanced-reat reaasoning mod- els. Fine-tuning also clearly improves smaller models, i.e. DeepSeek-8B and DeepSeek-1411 14B, both in terms of achieving stability and Instability Rate [ Similar results are obtained for the Preference Reasoning tasks, with the error-rate reducing to 0 at the Easy and Medium levels.
Table 2: Improvement in performance in the Generating Stable Solutions and Preference Reasoning tasks after fine- tuning on respective datasets.
Gencrating
Prefecence Reasoiing
Midal
Stage
Stuble Salatians
Stuble Sobations (%)
Instabiity Rate (i)
Accurasy (5)
Blay
Basy
Med.
Eas
Med.
Hard
DospSiekk
Fiieettree
Vanilla
64.0
$1.0
41,02
6.00
66.19
12.13
98.91
74,33
75.00
47.67
DeepSeck-148
Fine-funed
Vanilla
51.0
19.0
43.0
0.0
0.0
0.0
20.66
16.35
55.31
24.02
94.00
$4000
07.67
1010
91.33
100.
91.03
72.33
Qwen-QuQ-3t
Fine funed
100.0
100.0
99,00
In spite of these improvements, however, there remains a distinct gap in performance at the Easy and Medium levels as compared to the Hard level. LLMs remain altogether unable to compute stable matchings for Hard instances, even after fine-tuning. similar trend is reflected in the accuracy on the Preference Reasoning task. Hence, while fine-tuning clearly improves the reasoning capabilities of L.LMs, further enhancements are required to improve their ability to handle larger inputs.
'Interestingly, this improvement is clearer ML instances, where both models achieve a 100% success rate at the Easy level and > 80% success rate at the Medium level. The only exception being DeepSeek-88 8B the Medium level.

---

Table 3: The performance of LLMs with different reasoning capability across all tasks requiring reasoning over ranked preferences and executing structured algorithms.
Generating
Resolving Iustability
Detecting Instabiliit
Prefereuce Reasoning
Solutions
Category
Model
Stable Sotutions (56)
Instability
Rate
Uptimality Rate (1>
Stable Solutions (%S)
Instability Rate (1)
Optimaality Rate
Accuracy (%)
Accuracy (%)
Basic
Gemini-2.0-Pun
L.320-333-7008
0.33
2.36
0.21
0.21
0.17
0.83
56.04
$3.94
58.38
52.67
89
Ressoning
DeepSeck-708
Qwen-QuQ-13R
26.20
35.67
0.59
0.61
22,49
28.00
26.37
0.62
77,05
75.05
96. 89
$9.67
Reasoming
Advanced
DropSeck-R1
Gemini-22.-PPru
63-mini
68.33
58.00
19:98
7.16
12:35
0.80
0.84
0.73
61.35
57,50
18.52
14.31
8,50
0.75
0.79
0.79
92.38
19
99.67
78
8 Concluding Remarks
We summarize the performance of LLMs across all four tasks in Table reflecting the clear hierarchy between advanced-reasoning models, (non-advanced) reasoning models, and basic models. The limitations in reliably reasoning about ranked preferences raise concerns about the viability of LLMs settings,
as agents acting on behalf of users in market-oriented or preference-sensinee sensitive decision- limit their capacity to negotiate complex user preferences. and hinder efforts in developing pluralistic techniques (c.g.. constitutional AI (2) and social choice-theoretic (15)) for value alignment that are inherently based on aggregating rankings.
Open-Source vs. Closed models. Among the models that we evaluate, Gemini-2.5-Pro (a closed-source model) emerges the most capable across all tasks. While DeepSeek-R1 (open-source) broadly outperforms OpenAT's 03-mini (closed-source), it performs much worse with IC instances than with ML instances. While both basic models struggle on all tasks, Gemini-2.0-Flash (closed- source) marginally outperforms Llama-3.3-70BB (open-source) on various metrics. Given the promis- ing improvement yielded by fine-tuning open-source reasoning model, i.e. Qwen-QwQ-32B, it is worth exploring strategies that also enable it to handle large inputs.
Beyond Linear Preferences. Our current evaluation paradigm considers complete and strict linear preferences. In real-world scenarios, however, preferences involve complexities such as incomplete- ness, indifference between alternatives, and capacity constraints 18
As result, algorithms to compute stable solutions in such settings are far more complex and solutions are often intractable [53]. While, in Appendix E we provide some preliminary insights on preferences with ties, under- standing such cases requires deeper theoretical and empirical investigation. A meaningful next step would be examine how Al models respond to these more intricate preference structures.
46 54
Acknowledgments
This research was supported by the National Science Foundation (NSF) through CAREER Award IIS-214444 and Award IIS-2107173, We thank the anonymous reviewers for their fruitful comments. We would also like to thank Shraddha Pathak for several useful discussions.
References
[1] Hernan Abeledo and Uriel G Rothblum. Paths to marriage stability. Discrete Applied Mathe- matics, 63(1):1-12, 1995.
[2] Yuntao Bai, Saurav Kadavath, Sandipan Kundu, Amanda Askell, Jackson Kernion, Andy Jones, Anna Chen, Anna Goldie, Azalia Mirhoseini, Cameron McKinnon, et al. Constitutional AI: Harmlessness from AI feedback. arXiv preprint arXiv:2212.08073 2022.
[3] Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Michat Podstawski, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Hubert Niewiadomski, Piotr Nyczyk, and Torsten Hoefler. Graph of thoughts: solving elaborate problems with large language models. In Proceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty- Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence, AA//2/AAAAAAA/AAAAA 24. AAAI Press,
10

---

2024. ISBN 978 1577735-88-99 doi: 10. 10.1609/ aaad0 1...11...991111
URL https://dooi org/
[4] Duncan Black et al. The theory of committees and elections. Springer, 1958.
[5] Niclas Boehmer, Piotr Faliszewski, Lukasz.Janeczke Andrzej Kaczmarczyk, Grzegorz Lisowski, Grzegorz Pierczyáski, Simon Rey, Dariusz. Stolicki, Stanistaw Szufa, and Tomasz Was. Guide to numerical experiments on elections computational social choice. arXiv preprint arXiv:2402.11765, 2024.
[6] Robert Bredereck, Klaus Heeger, Dušan Knop, and Rolf Niedermeier. Multidimensional stable roommates with master list, 2021.
wttpaawwwwi...raa/////////// 14191
[7] Angelina Brilliantova and Hadi Hosseini. Fair stable matching meets correlated preferences. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, pages 190-198, 2022.
[8] Huanqia Cai, Yijun Yang, and Zhifeng Li. System-2 mathematical reasoning via enriched instruction tuning. CoRR, abs/2412.11664, 2024, doi: 10.48550/ARXI.2411... URL https://doi.. htttp:://do.oor/100 48550//550/0 www...211.................. 16964
[9] Ioannis Caragiannis and Karl Fehrs. Beyond the worst case: Distortion in impartial culture electorates, 2024. httpss///aarrii wwgg/bg//////////// 230.//030000000 .7730
[10] Qiguang Chen, Libo Qin, Jinhao Liu, Dengyun Peng, Jiannan Guan, Peng Wang, Mengkang Hu, Yuhang Zhou, Te Gao, and Wanxiang Che. Towards reasoning A survey of long ofainn-of-though for reasoning large language models. CoRR, abs/2503.095677, 2025. doi: 10448550/ARXXI.2550..0005
https:::::////// //dpss://doi... org/10.../.o..oo................ 48550/ 23550/arXivv arxiv 2503 09567
[11] Yiting Chen, Tracy Xiao Liu, You Shan, and Songfa Zhong. The emergence of economic rationality of gpt. Proceedings of the National Academy of Sciences, )e0 120, 2023.
[12] Haoang Chi, Li, Wenjing Yang, Feng Liu, Long Lan, Xiaoguang Ren, Tongliang Liu, and Bo Han. Unveiling causal reasoning in large language models: Reality mirage? In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, Tomczak, and C. Zhang, editors, Advances in Neural Information Processing Systems, volume 37, pages 96640-96770, Curran Associates, Inc., 2024. URL UtL/tttps://prrceedinng neurips cwtpaper_aaaiiieeeeeee files/paper> Cete-rooooeeeeeeeee pdf
[13]
Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Yunxuan Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, Albert Webson, Shixiang Shane Gu, Zhuyun Dai, Mirac Suzgun, Xinyun Chen, Aakanksha Chowdhery, Alex Castro-Ros, Marie Pellat, Kevin Robinson, Dasha Valter, Sharan Narang, Gaurav Mishra, Adams Yu, Vincent Y. Zhao, Yanping Huang, Andrew M. Dai, Hongkun Yu, Slav Petrov, Ed H. Chi, Jeff Dean, Jacob Devlin, Adam Roberts, Denny Zhou, Quoe Le, and Jason Wei. Scaling instruction-finetueed language models. J. Mach. Learn. Res., 25:70:1-70:53, 2024. URL https://jmlr. http::///ji...orr///pesss////// wttp:/apppr/////2303553/5
html.
[14] Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jemry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems. CoRR, abs/21 10.14168, 2021. URL
https://arxiv: org/ abs 2210. 14168
[15] Vincent Conitzer, Rachel Freedman, Jobst Heitzig, Wesley Holliday, Bob M Jacobs, Nathan Lambert, Milan Mossé, Eric Pacuit, Stuart Russell, Hailey Schoelkopf, et al. So- cial choice should guide Al aligmment in dealing with diverse human feedback. arXiv preprint arXiv:2404.10277 2024.
[16] Google Deepmind. Gemini pro, Mar 2025.
URL fttps://deeppiin google/
technologies// haaanoologgeesgemii/prroo/o gewini/pro////mmg

---

[17] AI, Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin
Xu, Qihao Zhu, Shirong Ma. Peiyi Wang, Xiao Bi, Xiaokang Zhang, Xingkai Yu, Yu Wu,
7. F. Wu, Zhibin Gou, Zhihong Shao, Zhuoshu Li, Ziyi Gao, Aixin Liu, Bing Xue, Bingxuan Wang, Bochao Wu, Bei Feng, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, Damai Dai, Deli Chen, Dongjie Ji, Erhang Li, Fangyun Lin, Fucong Dai, Fuli Luo, Guangbo Hao, Guanting Chen, Guowei Li, H. Zhang, Han Bao, Hanwei Xu, Haocheng Wang. Honghui Ding, Huajian Xin, Huazuo Gao, Hui Qu, Hui Li, Jianzhong Guo, Jiashi Li, Jiawei Wang, Jingchang Chen, Jingyang Yuan, Junjie Qiu, Junlong Li, J. L. Cai, Jiaqi Ni, Jian Liang, Jin Chen, Kai Dong, Kai Hu, Kaige Gao, Kang Guan, Kexin Huang, Kuai Yu, Lean Wang, Lecong Zhang, Liang Zhao, Litong Wang. Liyue Zhang, Lei Xu, Leyi Xia, Mingchuan Zhang, Minghua Zhang, Minghui Tang, Meng Li, Miaojun Wang, Mingming Li, Ning Tian, Panpan Huang, Peng Zhang, Qiancheng Wang. Qinyu Chen, Qiushi Du Ruiqi Ge, Ruisong Zhang, Ruizhe Pan, Runji Wang. R. J. Chen, R. I.. Jin, Ruyi Chen, Shanghao Lu, Shangyan Zhou, Shanhuang Chen, Shengfeng Ye, Shiyu Wang. Shuiping Yu, Shunfeng Zhou, Shuting Pan, and S. S. Li. Deepseek-rl: Incentivizing reasoning capability in Ilms via doi: 10445500ARXIV.2501.2220 12948
reinforcement learning. CoRR, abs/2501 12948, 2025.
URL https://doi...... org/ 10. 0088550/aXii1
[18] Maxence Delorme, Sergio Garefa, Jacek Gondzio, Jörg Kalesies, David Manlove, and William Pettersson. Mathematical models for stable matching problems with ties and incomplete lists. Eur. J. Oper Res., 27712):426-411, 2019. doi: 10.0016/.EJ0R.201..000177 URL
https://doi. org/ 111.10016.je... ejjor 2019. 03.
[19] Qingxiu Dong, Lei Li, Damai Dai, Ce Zheng, Jingyuan Ma, Rui Li, Heming Xia, Jingjing Xu, Zhiyong Wu, Tianyu Liu, et al. A survey on in-context learning. arXiv preprint arXiv:2301.00234. 2022.
[20] Jinhao Duan, Renming Zhang, James Diffenderfer, Bhavya Kailkhura, Lichao Sun, Elias Stengel-Eskin, Mohit Bansal, Tianlong Chen, and Kaidi Xu. Gtbench: Uncovering the strategic reasoning capabilities of lims via game-theoretic evaluations. In A. Globerson,
L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang, editors, Advances in Neural Information Processing Systems, volume 37, pages 28219-28253, Curran Associates, www.ips....... cc/ cwtpsecccppppppppeeeee pappprppprr___p files/ wwt..isss/pppp////////./ /appr//024//flle/ pdf
Inc., 2024. URL httRlittts::/proeeeeeiiiii
[21] Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, Anirudh Goyal, Anthony Hartshom, Aobo Yang, Archi Mitra, Archie Sravankumar, Artem Korenev, Arthur Hinsvark, Arun Rao, Aston Zhang, Aurélien Rodriguez, Austen Gregerson, Ava Spataru, Baptiste Rozière, Bethany Biron, Binh Tang, Bobbie Chern, Charlotte Caucheteux, Chaya Nayak, Chloe Bi, Chris Marra, Chris McConnell, Christian Keller, Christophe Touret, Chunyang Wu, Corinne Wong. Cristian Canton Ferrer, Cyrus Nikolaidis, Damien Allonsius. Daniel Song, Danielle Pintz, Danny Livshits, David Esiobu, Dhruv Choudhary, Dhruv Mahajan, Diego Garcia-Olano, Diego Perino, Dieuwke Hupkes, Egor Lakomkin, Ehab AlBadawy, Elina Lobanova, Emily Dinan, Eric Michael Smith, Filip Radenovic, Frank Zhang, Gabriel Synnaeve, Gabrielle Lee, Georgia Lewis Anderson, Graeme Nail, Grégoire Mialon, Guan Pang, Guillem Cucurell, Hailey Nguyen, Hannah Korevaar, Hu Xu, Hugo Touvron, Iliyan Zarov, Imanol Arrieta Ibarra, Isabel M. Kloumann, Ishan Misra, Ivan Evtimov, Jade Copet, Jaewon Lee, Jan Geffert, Jana Vranes, Jason Park, Jay Mahadeokar, Jeet Shah, Jelmer van der Linde, Jennifer Billock, Jenny Hong, Jenya Lee, Jeremy Fu, Jianfeng Chi, Jianyu Huang, Jiawen Liu, Jie Wang. Jiecao Yu, Joanna Bitton, Joe Spisak, Jongsoo Park, Joseph Rocca, Joshua Johnstun, Joshua Saxe, Junteng Jia, Kalyan Vasuden Alwala. Kartikeya Upasani, Kate Plawiak, Ke Li. Kenneth Hcafield, Kevin Stone, and et al. The lama 3 herd of models. CoRR, abw////0..22a/a 0774407..77,,,. 2024. doi: 10.4850/ARXIV.447..1185 URL httph::tt:/oooot org/ htt.:///00r..1..../////0/////// arvvv 2407 .2783
[22] Öner Eğecioğlu and Ayça Giritligil. The impartial, anonymous, and neutral culture model: a probability model for sampling public preference structures. The Journal of Mathematical Sociology, 37(4)203--22, 2013.
[23] Sara Fish, Paul Gölz, David C. Parkes, Ariel D. Procaccia, Gili Rusak, Itai Shapira, and Manuel Wüthrich. Generative social choice. In Dirk Bergemann, Robert Kleinberg, and Danicla Sabán,
12

---

editors, Proceedings of the 25th ACM Conference on Economics and Computation, EC 2024, New Haven, CT. USA, July 8-11, 2024, page 985. ACM. 2024. doi: 10. 10.11453670865536735477 URL wtt.https:////// https::/doi...... www.oogg///oo 00t..11///676653377777777 3673547
[24] Sara Fish, Julia Shephard, Minkai Li, Ran I. Shorrer, and Yannai A. Gonczarowski. Econevals: Benchmarks and litmus tests for LLM agents in unknown environments. CoRR, abs/2503.1882, 2025, doi:
18825. URLhttps::/dda org/ 400.048850/aaa. arriv 2503
18825
[25] R. A. Fisher. On the interpretation of x2 from contingency tables, and the calculation of Journal of the Royal Statistical Sociery, 85(1):87-94, 1922. ISSN 09528385. URL http 7/www wwww.jstor org/ htgg/stabbe/2340552
[26] David Gale and Lloyd S Shapley, College Admissions and the Stability of Marriage. The American Mathematical Monthly, 69(1):9-11) 15, 1962.
[27] David Gale and Lloyd S Shapley, College admissions and the stability of marriage. The American Mathematical Monthly, 69(1))9-15, 1962.
[28] Chengguang Gan, Qinghao Zhang, and Tatsunori Mori. Application of LLM agents in recruit- ment: A novel framework for automated resume screening. Journal of Information Processing, 32:881-892 2024.
[29] Jiayi Gui, Yiming Liu, Jiale Cheng, Xiaotao Gu, Xiao Liu, Hongning Wang, Yuxiao Dong, Jie Tang, and Minlie Huang. Logicgame: Benchmarking rule- muse-based reasoning abilities of large language models. CoRR, abs/2408. 15778, 2024. doi: 10448550/ARXV..4088.. 15778. URL
https://doi. org/10. 48550/ 135500/arXiv arXiv. 2408. 15778
[30] Dan Hendrycks. Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. Measuring massive multitask language understanding. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. BtL.htttss://oponreeee
[31] Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the MATH dataset. In Joaquin Vanschoren and Sai-Kit Yeung, editors, Pro- ceedings of the Neural Information Processing Systems Track on Datasets and Bench- marks 1, NeurlPS Datasets and Benchmarks 2021, December 2021, virtual, 2021. URL ae535becdbbt/aaaadcc.b////3333.3
neurips.. httpseaeee.e..eeeeeee/////// cc//paper//022/haah httll
[32] John J Horton. Large language models as simulated economic agents: What can we learn from homo silicus? Technical report, National Bureau of Economic Research, 2023.
[33] Hadi Hosseini and Samarth Khanna. Distributive fairness in large language models: Evaluating alignment with human values. arXiv preprint arXiv:2502.003/ 2025.
[34] Edward J. Hu, Yelong Shen, Phillip Wallis. Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. Lora: Low-rank adaptation of large language models. In The Tenth International Conference on Learning Representattinns ICLR 2022, Virtual Event, April 25-29,
2022. OpenReview.net, 2022. URL.https::/opeereviiss
[35] David Huang, Francisco J. Marmolejo Cossío, Edwin Lock, and David C. Parkes. Accelerated preference elicitation with Ilm-based proxies. CoRR, ab5/2501.144255, 2025. doi: 10.48550/ RRX1V.2501.14625. URL htthhhtt/////t :/doi. ieeiidi..oggggg/
org/ /00 48550/ar5iii. 2501, 14625
[36] Robert W. Irving. Stable marriage and indiffereenee. Discrete Applied Mathematics, 48(3): 261-272, 1994. ISSN 0166-218X. doi: http:://bb.ooo///...000666622210
URL
[37] Robert W. Irving, Paul Leather, and Dan Gusfield. An efficient algorithm for the "optimal" stable marriage. Journal of the ACM, 34())533-543, jul 1987. ISSN 0004-5411, doi:
10.1145/28869.22 18871. htLps: org/ 10. 114.//14522999 28877
13

---

[38] Robert W Irving, David F Manlove, and Sandy Scott. The stable marriage problem with master preference lists. Discrete Applied Mathematics, 156(15):2959 2977, 2008
[39] Jingru Jia and Zehua Yuan. An experimental study of competitive market behavior through Ilms. arXiv preprint arXiv:2409.08357, 2024.
[40] Jingru Jia, Zehua Yuan, Junhao Pan, Paul McNamara, and Deming Chen. Large language model strategic reasoning evaluation through behavioral game theory. CoRR, abs/2502.20432, 2025, doi: 1044550/ARXII25002224333
org/ 10. (38500/axiiv 2502
20432
[41] Carlos E. Jimenez, John Yang, Alexander Wettig, Shunyu Yao, Kexin Pei, Ofir Press, and Karthik R. Narasimhan. Swe-bench: Can language models resolve real-world github issues? In The Twelfth International Conference Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024. URL htt.tttt/////eeeeiiiiiee www.eewwwee/fooroeee net/forum? 1d=VIF8yNQM66
[42] Enric Junqué De Fortuny. Simulating market equilibrium with large language models. In Proceedings of the 58th Hawaii International Conference on System Sciences, 2025.
[43] Naoyuki Kamiyama. Stable matchings with ties, master preference lists, and matroid constraints. In Martin Hoefer, editor, Algorithmic Game Theory, pages 3-14, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg. ISBN 978-3-662-48433-3.
[44] Donald Ervin Knuth. Marriages stables. Technicul report, 1976.
[45] Donald Ervin Knuth. Stable marriage and its relation to other combinatorial problems: An introduction to the mathematical analysis of algorithms, volume 10. American Mathematical Soc., 1997.
[46] Augustine Kwanashic and David F. Manlove. An integer programming approach to the hospi- tals/residents problem with ties. In Dennis Huisman, Ilse Louwerse, and Albert P. M. Wagelmans, editors, Operations Research Proceedings 2013, Selected Papers of the International Confer- ence on Operations Research, OR2013, organized by the German Operations Research Society (GOR), the Dutch Society of Operations Research (NGB) and Erasmus University Rotterdam, September 3-6, 2013, pages 263-269, Springer, 2013. doi: 10. 10.1007/978.3-119-00000--- URL https:: org/ 10. 1007/900-77222 3-0---1100000111111 0tt
[47] Aitor Lewkowyez, Anders Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski. Vinay V. Ramasesh, Ambrose Slone, Cem Anil, Imanol Schlag, Theo Gutman-Solo, Yuhuai Wu, Behnam Neyshabur, Guy Gur-Ari, and Vedant Misra. Solving quantitative reasoning problems with language models. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, Novem- ber 28- December 9, 2022, 2022. URL http::tt:p::ppeee nips wwtppppppppppppeeeeeeeeeeeee...p farersfffeee/eee /lpp/ppprr///// Conference html
[48] Chengpeng Li, Zheng Yuan, Hongyi Yuan, Guanting Dong, Keming Lu, Jiancan Wu, Chuanqi Tan, Xiang Wang, and Chang Zhou. Mugglemath: Assessing the impact of query and response augmentation on math reasoning. In Lui-Wei Ku, Andre Martins, and Vivek Srikumar, editors, Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), ACL. 2024, Bangkok, Thailand, August 11-16, 2024, pages 10230- 10258. Association for Computational Linguistics, 2024. doi: 10. 18653V66/ 12.4655VN22224ACCLL 1/002.ACLLLL 551. URL URLhttts:://dat fttttp:://aoi..rg/o....1.. 11t.:11..1661vv11/1 acl- 551
[49] Zhong- Zhi Li, Duzhen Zhang, Ming-Liang Zhang, Jiaxin Zhang, Zengyan Liu, Yuxuan Yao, Haotian Xu, Junhao Zheng, Pei-Jie Wang. Xiuyi Chen, Yingying Zhang, Fei Yin, Jiahua Dong, Zhijiang Guo, Le Song, and Cheng-Lin Liu. From system to system 2: A survey of reasoning large language models. CoRR, abx/2502. 17419, 2025. doi: 20-4 URI. https: : /doi. org/10 10//1..0. 48550 arxiv 2502. 17419
14

---

[50] Yinhong Liu, Zhijiang Guo, Tianya Liang, Ehsan Shareghi, Ivan Vulic, and Nigel Collier. Aligning with logic: Measuring, evaluating and improving logical consistency in large language models. CoRR, abs/2410.02205,, 2024. doi: 1044550/ARXX URL https
//doi.org/10 4000./8550//rr0 arriv. 2410. 02205
[51] Liangchen Luo, Yinxiao Liu, Rosanne Liu, Samrat Phatale, Harsh Lara, Yunxuan Li, Lei Shu, Yun Zhu, Lei Meng, Jiao Sun, and Abhinav Rastogi. Improve mathematical reasoning in language models by automated process supervision. CoRR, abs/2406.06592, 2024. doi: 2406 06592
(0448550/ARXXV.22460666667
URL (RLhhtt:://d// orttpp:://oi..or//000.. 48000.4855/aaz/
[52] Ziyang Luo, Can Xu, Pu Zhao, Qingfeng Sun, Xiubo Geng, Wenxiang Hu, Chongyang Tao, Jing Ma. Qingwei Lin, and Daxin Jiang. Wizardcoder: Empowering code large language models with evol-instruct. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024. URL https://opeerreeiie
met//foruun/oo-nnUsSSggSSS
[53] David F. Manlove. Algorithmics of matching under preferences. Bull. EATCS, 112, 2014. URL www.aatcss..rgbbaacaa/eeeeeeeeee pptpbaattes/rriiica////////////
[54] David F. Manlove, Duncan Milne, and Sofiat Olaosebikan. Student-project allocation with preferences over projects: Algorithmic and experimental results. Discret, Appl. Math., 308: 220-234, 2022. doi: 10. 00100161.DAM.22200..01515 URL https://doi. httpg//..1116///
dam 2020. 08220.8.000 015
[55] Larisa Markeeva, Sean McLeish, Borja Ibarz, Wilfried Bounsi, Olga Kozlova, Alex Vitvitskyi, Charles Blundell, Tom Goldstein, Avi Schwarzschild, and Petar Velickovic. The clrs-text algorithmic reasoning language benchmark. CoRR, abs/2406.00422, 2024. doi: 10.48550/
BRXIV.2406.04229. https:////// org/ 48550/arXiv......// www...240............. 2406 04229
[56] David G Vititie and Leslie B Wilson. The stable marriage problem. Communications of the ACM, 14(7):486-49)) 1971.
[57] Seyed-Iman Mirzadeh, Keivan Alizadeh, Hooman Shahrokhi, Oncel Tuzel, Samy Bengio, and Mehrdad Farajtabar. Gsm-symbolic: Understanding the limitations of mathematical reasoning in large language models. CoRR, abs/2410.055229 2024. doi: 1048500/AXXIV2410052299 2410 05229
URL https:
[58] Terufumi Morishita, Gaku Morio, Atsuki Yamaguchi, and Yasuhiro Sogawa. Enhancing reasoning capabilities of lims via principled synthetic logic corpus. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomezak, and Cheng Zhang, editors, Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 15, 2024, 2024. URL http:://pppppr// nips. cc/ wacc/appr_ffiii caatssffleeppppee http:/pppe/222/aaaaeeee 8677ds90128555882222 2tt.:02220522022222222222222 Abstract Confer Abstract-Conferoncee html
[59]
OpenAL. Openai 03-mini system card, 2025.
URL https://openall com com/index, index/
03 mini - wystsmssttmssse cardd/
[60] Sundar Pichai, Demis Hassabis, and Kouray Kavukcuoglu. Introducing gemini 2.0: our new ai model for the agentic era, Dec 2024. URL //blos http::///bboggggggleeeeeeeoo/// google//ecchoooggy// google-deepmind/goonn
-egiini--- ai- goo.aeeennigoooolegeeinnnnnnnnni
2024/
[61] National Resident Matching Program. Results and data: 2024 main resi-
dency match, 2024.
URL https://www wwwpp www.:nwww.........oom
results-and and lorddddat-2aae 2024 main resi rewi-rrereeenncmmmccc/h
[62] Alvin E Roth and John H Vande Vate. Random paths to stability in two-sided matching. Econometrica: Journal of the Econometric Society, pages 1475-1480. 1990.
[63] Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, Y. K. Li, Y. Wu, and Daya Guo. Deepseekmath: Pushing the limits of mathematical reasoning in open language models, 2024. URL https:::tt: //tpx//axvvv////////// org/ abs/
2402.03300
15

---

[64] Kiwon Song, James M Jennings III, and Clintin P Davis-Stober. Benchmarking the rationality of Al decision making using the transitivity axiom. arXiv preprint arXiv:2502.10554 2025.
[65] Ermis Soumalias, Yanchen Jiang, Kehang Zhu, Michael J. Curry, Sven Seuken, and David C. Parkes. Lim-pur L.mm-oweere preference elicitation in combinatorial assignment. CoRR. abs/2502.10035 2025. doi: 4445550ARXXI22552000005 URL https://doi.
18550/arXiv 2002. 10308
[66] Wenjie Tang, Yuan Zhou, Erqiang Xu, Keyan Cheng, Minne Li, and Liquan Xiao. Dsghench: diverse strategic game benchmark for evaluating llm-based agents in complex decision- making environments. CoRR, abs/2503.06 06047, 2025. doi: 10.48500AARXIV255000000 URL
https://doi. httpp:://doooor//1...o 48550/8550aaa0
2503. 06047
[67] Qwen Team. Qwq: Reflect deeply on the boundaries of the unknown, Nov 2024. URL attps://quent www.ingiihhhu........ 1o. htt.b/////oo///oooooooooggoooolt wwwpo///wwqg-000 qwq-32b preview/
[68] Ye Tian, Baolin Peng, Linfeng Song, Lifeng Jin, Dian Yu, Lei Han, Haitao Mi, and Dong Yu. Toward self-improvement of Ilms via imagination, searching, and criticizing. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, Tomczak, and C. Zhang, editors, Advances in Neural Information Processing Systems, volume 37, pages 52723-52743 Curran Associates, Inc., 2024. URL htttps:: wwctinnggnnnuuurpr neurips paperapp__... paapr_ffllesseeeeepaaaaaaaaaeeee files/ files/paper// Paper Conference .dd
[69] Vince Trencsenyi, Agnieszka Mensfelt, and Kostas Stathis. Approximating human strategic reasoning with llm-enhanced recursive reasoners leveraging multi-agent hypergames. CoRR, abs/2502.07443, 2025. doi: 10:48500/ARXXV22500077444 URL https://aoi.org:: 48550 1a150//arxi.. 250.xiv..200.... 07443
[70] Ilia Tsetlin, Michel Regenwetter, and Bernard Grofman. The impartial culture maximizes the probability of majority cycles. Social Choice and Welfare, 21(3):387-398, 2003. ISSN 01761714, 1432217X. htt:htt://wee http:::/wwwwjssor.orrg.
[71] Emily Vaillancourt and Christopher Thompson. Instruction tuning on large language models to improve reasoning performance. Authorea Preprints, 2024.
[72] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-24837, 2022.
[73] B. L. Welch. The generalization of 'student's' problem when several different population variances are involved. Biometrika, 34(1/2):28 35, 1947. ISSN 00063444. URL http www..jstor org/ stt.s//eaaee22/1//////
[74] Kai Xiong, Xiao Ding, Ting Liu, Bing Qin, Dongliang Xu, Qing Yang, Hongtao Liu, and Yixin Cao. Meaningful learning: Enhancing abstract reasoning in large language models via generic fact guidance. In Amir Globersons. Lester Mackey, Danielle Bel- grave, Angela Fan, Uirich Paquet, Jakub M. Tomczak, and Cheng Zhang, editors, Ad- vances in Neural Information Processing Systems 38: Annual Conference
Neural In- formation Processing Systems 2024, NeurlPS 2024, Vancouver, BC, Canada, December 10 15, 2024, 2024. URL http::/papers..atte////// nips cc cctpcc/pppp.oo wwcppaper_fttt files/ files/paper/ httppppppp/////// 2ee///2222/hh/h// hash// Abstract Conference. hhten
[75] Yi Xu, Laura Ruis, Tim Rocktäschel, and Robert Kirk. Investigating non-transitivity in LLM- as-a-judge. arXiv preprint arXiv:2502. 14074, 2025.
[76] Joshua C. Yang, Damian Dailisan, Marein Korecki, Carina I. Hausladen, and Dirk Helbing. LLM voting: Human choices and AI collective decision-making In Sanmay Das, Brian Patrick Green, Kush Varshney, Marianna Ganapini, and Andrea Renda, editors, Proceedings of the Seventh AAAI/ACM Conference on AI, Ethics, and Society (AIES-24) Full Archival Pupers, October 21-23, 2024, San Jose, California, USA- Volume 1, pages 1696-1708. AAAI Press, 2024. doi: 10.1609/AIES 110.0//AEE....1.1555... URL https: http///oi.aaa org 10. 1 aies. v711 31758
16

---

[77] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: deliberate problem solving with large language models. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2023. Curran Associates Inc.
[78] Xuan Zhang, Chao Du, Tianyu Pang, Qian Liu, Wei Gao, and Min Lin. Chain of pref- erence optimization: Improving chain-of-thought reasoning in llms. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet. Tomczak, and C. Zhang, editors, Advances in Neural Information Processing Systems, volume 37, pages 333-356. Curran Associates, Inc., 2024. URL /ttp neurips cc/ wappap www.fflllaapppee pttp//pppppp///eeeeeee. pdf
[79] Heng Zhou, Hejia Geng, Xiangyuan Xue, Zhenfei Yin, and Lei Bai. Reso: A reward-driven self- organizing llm-based multi-agent system for reasoning tasks. CoRR, abs/2503.02390, 2025. doi: 10448550/ARXIV.2500..2222 02..0999. URL URL httpps///0....rrg///
48550/8500/ee0 arviv 2w0....50000223330 02390
[80] Pei Zhou, Jay Pujara, Xiang Ren, Xinyun Chen, Heng-Tze Cheng, Quoc V. Le, Ed H., Denny Zhou, Swaroop Mishra, and Huaixiu Steven Zheng. Self-discover: Large lan- guage models self-compose reasoning structures.
A. Globerson, L.. Mackey, D. Bel- grave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang. editors, Advances in Newral Information Processing Systems, volume 37, pages 126032-126058. Curran Associates, Inc., 2024. URL
nww.ses...ees.peppeeeeeeeeeeeeee https///esseapp////////// eel.ebbeeeaa22200000ccc77eeeeeep Poneccreeee pdf
17

---

A Limitations and Future Work
While we present comprehensive evaluation of the practical algorithmic and economic reasoning capabilities of series of state-of-the-ar LLMs, our dataset primarily relies on synthetic data due to the challenges in obtaining real-world ordinal preference data. This calls for the collection and curation of datasets in the two-sided matching setting, and generating preference profile datasets that better aligned with human preferences.
Additionally, while our work provides insights into the reasons behind the failure of LLMs to consistently generate stable solutions (see Section 6 there is scope for further clarity where exactly LLMs make mistakes during algorithmic execution. A potential method to explore this is to break the algorithmic execution task into smaller steps (e.g., single proposal-ace acceptance/rrejection cycle) and identify which components of the state-transition are challenging for LLMs to understand.
Furthermore, while fine-tuning substantially enhances L.Ms' performance on instances with rela- tively smaller input sizes, improving their performance with larger inputs requires further exploration. This can include the investigation of methods such as fine-tuning the entire set of parameters (unlike with LoRA) or cettorrementlcarnninn methods such as group- policy optimization (GRPO) that are known increase the reasoning capabilities of LLMs (63
B Broader Impacts
This paper is intended to advance Machine Learning and AI research, with special emphasis on the reasoning ability of LLMs-an essential component of autonomous Al systems. We identify key shortcomings in the reasoning capabilities of LLMs, especially in terms of aggregating individuals preferences over alternatives and algorithmic execution. We believe that the findings presented in this work can inform further research into AI systems to enhance their ability to act independently in complex decision-making environments.
C Preference-Based Algorithms in Matching Markets
C.1 Algorithm for Generating Stable Matching
As shown in Algorithm [ the standard deferred-acceptaane algorithm runs by having the proposing side of the market make a series of proposals, and each agent that receives at least one proposal decides which proposal to accept (the proposal becomes engagement), and which proposals to reject (or engagements to break). This continues until all agents are matched, which requires O(n²) proposal steps. The resulting solution is stable (27). To describe the algorithm, adopt the traditionally used setting of stable-marriage where the proposing side consists of men and the receiving side consist of women.
Algorithm 1 The Deferred Acceptance Algorithm
assign each agent E A and E W to be free
while there exists a free man m who has not proposed to every woman do highest-ranked woman m preference list to whom he has not yet proposed m proposes to w if is free then
w tentatively accepts m else if prefers to her current partner m then rejects m' and tentatively accepts m m' becomes free
else
rejects m end if
end while
return the set of engaged pairs, these form stable matching
18

---

Another commonly used version of the DA algorithm involves the receiver agent (in given proposal) removing all agents (on the proposer-side) from their preference list who are ranked below the current proposer agent (who also remove the receiver from their respective preference lists). Due to the shortening of the preference lists as the algorithm progresses (see Algorithm 2), this referred as the version of the DA algorithm with Shortlists [77. While this version terminates with at most as many (and often less) proposal steps as compared to Algorithm | original preference lists.
it requires repeated updates to the
Algorithm 2
The Deferred-Acceppin
Algorithm with Shortlists
assign each agent m E M and w E W to be free while some man m free do
== first woman on m's preference list m proposes and becomes engaged to w
if' some man p is engaged to then break the engagement (p, w). assign to be free end if
for each m' in w's preference list s.t. m > m' do remove m' and w from each other's preferences end for
end while
return the set of engaged pairs, these form stable matching
C.2 Algorithm for Generating Stable Matching w/ Master-Lists
Similar to Algorithm I Algorithm runs in rounds of proposals. Since there is a Master-list over proposing agents in the preference Tists of receiving agents, and proposing agents are selected to make proposals in the order in which they appear in the Master-list, there are no rejections (since any receiver receives the best possible proposal at any step) (38). Hence, this algorithm terminates in proposal steps (and is therefore casier to execute).
Algorithm 3 The Referred-Acceptanne Algorithm for Preferences w/ Master-lists on One Side
assign each agent m E M and w E W to be free L Master-list over men. for next free man m in L do first woman on m's preference list
m proposes and becomes engaged to w end for
return the set of engaged pairs, these form stable matching
C,3 Algorithm for Resolving Instability
While we don't explicitly describe the algorithm here, the mechanism presented by Abeledo and Rothblum [I] can be applied to an unstable matching μ by resolving blocking pairs, resulting in stable solution. Intuitively, an LLM does not have to follow specific mechanism, rather the model can resolve instability by iteratively resolving blocking pairs as they arise (eventually, assuming all steps correct, the model should arrive a stable solution).
C.4 Algorithm for Detecting Instability
Intuitively, Algorithm 4 works by iteratively visiting each pair of agents (m, w) s.t. m E M and E W, and finding pair such that either prefers w to their current partner, or w prefers to their current partner (when such pair is found, output as a blocking pair). If no pair (m, w) found to be blocking pair, then the solution is stable.
19

---

Algorithm 4 Stability Detecting Algorithm
for each (m, w) E 14, where É M and w E W for man m E M do for man to E W do m > (u(w) and w >m (((m) then
output the identified blocking pair (m,w)
end if end for end for
output that there exist no blocking pairs
Table Percentage of stable solutions returned by LLMs when provided with the DA algorithm in the prompt (With) as compared to the case when not provided (Without).
Reaenning LLMs
Atvaneed Bazesming LLMss
L.-71--33-00
TwC3--QQQ33BB
DeepSeck-Top
o3-mini
DecpSeck-R1
Gemini
Difiicatty
Preference
Without
Win
Wittont
With
Without
Win
Withort
Was
Without
Wira
Without
With
Without
With
Easy
72
1611
98
Medium
ML
IC
0
34
14
40
14
0
12
0
90
86
82
58
201
94
35,67
26,00
36,00
70
D Prompt Engineering
Providing Algorithmic Description. In Table examine LLMs' performance when provided with prompt containing pseudocode for the DA algorithm, and compare it the case when algorithm is provided in the prompt. While providing the DA algorithm as part of the prompt leads to an improvement some cases, the only case in which there improvement statistically significan is with DeepSeek-70B at the Easy level with ML instances.
Reasonnnggenhaancemenn Prompts. For models that fail generating stable matchings even with small instances, we evaluate whether prompt-basen enhancements such as Chain-of- Chain-of-Thought (CoT) 72 and Few-shot prompting [19] can improve their performance. In particular, introduce the following three types of modifications to the original prompt (used in Section 3):
CoT-Vanilla (CoT-V): The steps of execution of the DA algorithm (see Algorithm T are provided for an example instance. Each step consists of single (free) proposing agent making his next proposal, and the receiving agent either accepting or rejecting the proposal based on their current status.
CoT-Shortlist (CoT-SL):
This version of CoTT uses the Shortlist version of the DA algorithm (see Algorithm 2 which reduces the overall number of proposal steps, but requires repeated updates to the original preference lists.
Few-shot Examples: As opposed to the previous two cases, we provide LLMs with three examples of stable matching instances accompanied by their solutions.
To limit the context size of the prompt, consider examples with = 5 for each of these prompt modifications.
As depicted in Table these prompting enhancements fail to improve the ability of L.LMs to generate stable matchings. While there is a slight improvement for models like Owen-QQQ-322) and DeepSeek-700 instances with Master-list preferences and size n 10, this improvement is not statistically significant.
At p < 0.05, using Fisher's exact test
Alll models considered here are never able to generate stable matchings at the Hard difficulty level, with any prompting method.
20

---

Table 5: Percentage of stable solutions returned when prompt-enhancement strategies are used, as compared to the case without, for the Easy and Medium difficulty levels.
Sine
Culere
Newe
CuTy
Caldi.
Fre-sket
New
Cursi.
Freesker
New
CaTAI
Fou-dlt
Newo
CarV
GaF-Si
Fou-dur
ML
16
IC
0
Table 6: Percentage of stable solutions from two LLMs when the task is framed as the stable marriage and the scheduuug problem.
Madel
Grmini-21x
Difliuaity
Preference
Marriiqe
Stable
Schedtlling
Tock
Statle Marrisge
Tock Schodaling
IC
100
US
ML
ML
50
MT.
IC
0
0
Modified Problem Setting. We consider the traditionally used setting of stable-marriage, where the set M consists of men who propose to women in the set W [26]. To measure whether LLMs are sensitive to the nomenclature used to described the two-sided matching market, we also consider a different setting, i.c, that where set of workers (W) are to be assigned a set of tasks (T") (and members on both sides have preferences over members of the other). We test the difference in the performance of two LLMs Gemini-2.0-E F.0-Flshh and o3-mini-betteen beetween the task-scheduling and stable-marriage settings. The results are provided in Table [ While there is slight decrease in performance for 03-mini, the change is not significant (at < 0.05). This provides further evidence that LLMs understand requirements of computing stable solutions for matching markets, general.
E Generating Stable Solutions for Preferences with Ties
As demonstrated in Section Bl crasoning-enabled models achieve significantly higher accuracy on Easy instances when compared to non-reasoning baseline models, but suffer dramatic drops in performance with Hard instances. A natural extension of this is examine how introducing ties to preferences impacts an LLM's ability to generate stable solutions.
New notions of stability. When ties are introduced to preference profiles, additional (stronger) notions of stability exist. Namely, in addition to the standard notion of weak stability (where matching does not admit any weak blocking pairs: agents who strictly prefer each other to their current partners), we have the added notions of strong and super stability, where a matching does not admit any strong or super blocking pairs, respectively. A strong blocking pair is a pair of agents in which one agent strictly prefers the other agent over their current partner, and the other agent remains indifferent or prefers the first agent and their current partner. A super blocking pair is a pair of agents in which either agent is either indifferent the other agent and their current partner, or prefers the other agent to their current partner. Super stability, the strongest notion of stability, implies strong stability, which in turn implies weak stability. Additionally, it is important to note that strongly and super stable solutions do not exist for all preference profiles.
Irving 36 provides three algorithms (one for each) to compute weakly, strongly, and super stable matchings for preference profiles with ties. The algorithm for weak stability takes O(n²) steps (the algorithm is equivalent to running standard the DA algorithm with arbitrary tie-breaking), the algorithm for strong stability takes O (n²)) steps, and the algorithm for super stability takes ((n)) steps (these two algorithms require more demanding steps with complex operations).
Generating matchings for each stability notion. To evaluate how LLMs handle preferences with ties, we perform the same experiment as in Section 3 with Easy preference profiles and Gemini-2.5-Pro. except we introduce multiple ties of random sizes, at randomly selected start- ing positions, in each preference list in the profile. Additionally, we modify the prompt listed in Appendix D.T to get total of three different prompts. The first prompt (referred to as the Baseline Prompt) is identical to the prompt in Appendix J.] The other two prompts (referred to as the Strong
21

---

Stable
Stronaly Stable
Wealdy Stable
Unstable
Percentage Responses
80
IC-Fasy ML-Fasy
IC-Easy ML-Easy Strong Prompt
IC-Fasy Mi-Fasy
Baseline Prompt
Super Prompt
Figure 7: The generated responses by Gemini-2.5-PP for Master-list (ML) and Impartial Culture (IC) Easy preferences with different prompts. All generated matchings were valid and complete. Again, unstable indicates one-to-one matchings with weak blocking pairs present.
Prompi and Super Prompt) replace the instruction to "...find the proposer-optimal stable matching..." with f...find the proposer-optimal STRONG stable matching..." and "...find the proposer-optimal
SUPER stable matching..." respectively. For each prompt, we run the experiment and count the proportion of generated matchings that are super, strong, and weakly stable, well as unstable matchings.
Figure 7 demonstrates the performance of Gemini-2.5-1 in generating stable outcomes with respect to each of the three new notions stability for preference profiles with ties. Gemini-2.5-PP once again demonstrates high accuracy (96%) in generating stable solutions (considering weak, strong, and super stability) with the Baseline Prompt, with 50% and 54% of stable solutions being weakly stable with the IC-Easy and ML-Easy preference profiles, respectively. However, only around 40% of generated solutions were super (and strongly) stable for both preference cultures. Gemini-2.5-Pro" reasoning traces for each instance indicate that the model essentially attempts execute the DA algorithm when generating stable solutions even when ties are present (rather than utilizing the more complex algorithms for strong and super stability, even when explicitly prompted). Additionally, any generated super stable solutions are a result of an instance's ' super stable solution intersecting with its weakly stable solution. Interestingly, specifying the notion of stability appears to significantly hurt the model's s ability to generate any stable solutions. While one potential explanation is that specifying the desired stability notion in the prompt introduces unnecessary noise, this is interesting avenue for future study.
Resolving Instability: Additional Material
F1 Generating Unstable Matchings
Here we describe the procedures use generate the two types of unstable matchings we consider.
One-BP.
We generate a matching that contains a single blocking pair, by swapping the partners of two randomly selected proposer agents in the Optimal matching. Since such a swap may lead more than one blocking pair no blocking pairs), we perform this process (for every instance) until we obtain matching with exactly one blocking-paii This procedure is formally described in Algorithm
Random. Random matching simply generated by generating random permutation of agents one side and assigning agents such list to the agents the other side, one-by-one.
22

---

Algorithm 5 GENDRRTIONGBPMATCHING
Require:
II
(>my) m
Preference profile for all men M and women E W > Men-optimal stable matching returned by Deferred Acceptance
14"
Ensure:
A matching containing exactly one blocking pair
function CENERRTEEEEEPPPPCCCNNNCCLL
2: repeat
Keep trying until the condition is met Start from the stable matching
3: 1 - copy(μ²)
4: (Ma; mo) f arbitrary pair Ma, E M s.t. Ma F m&
5: Wa + ((ma)
6:
Wp p(mss)
Swap partners of the two men
7:
p(maa) +- Why (u(w)) 6- Ma
8:
p((m)) was ((waa <-
9:
until BLOOCKINGAIRRS(, (I)
Stop when exactly one blocking pair exists
10: return
11: end function
12: function BLOCKINGPAIRS(AL II) B 4-0
14:
for all m M do
15:
for all w E do
16:
if mm μ(m) and m ~ p(w) then + {(m,u) w)}
17:
18:
end if end for end for
19:
20:
21:
return B
22:
end function
Table 7: Instability Rate (averaged across instances) in the (valid) matchings returned by LLMs when
asked to resolve given unstable matching of types One- BP and Random. The column "Baseline" contains the (average) Instability Rate for the provided matching of the indicated type. Numbers in bold indicate that the Instability Rate of the corrected solution is significantly worse than the provided matching. * on the number the One-BP column indicates a that Instability Rate is significantly lower than the case when Random matching provided (at p 0.05)
Reassiig H1Mc
Amtrrcel Revening
edestal
Depbedk
Geeeni 2.5--
"De-fi
Exe
X.44
(09)
0:20
Madian
50,00
50.1
57.48"
6L12
14.50
(9.3)
33.00
43.84
3.92
3.85
18.65
12.58
237
3.5
5.90
$7.00
Tiard
17.41
35.00
41.79
47.1
F.2 Further Results
Measuring Instability after Repair. The extent which given matching is incorrect does influence quality of the solutions returned by LLMs after being asked to correct it. Table shows that the number of blocking pairs often significantly lower when the unstable matching (that LLMs are asked to correct) has single blocking pair, as compared to the case with random matchings [ Similarly, as shown in Figure matchings returned after resolving an almost stable matching have greater overlap with the Optimal solution (especially at Medium and Hard difficulty levels).
statistical comparisons in this table are made using Welch's I-test 73
In fact, asking LLMs to resolve a random matching leads to significantly higher number of blocking pairs in the returned solution, compared to the case when they asked generate solutions from scratch.
23

---

Optimality Nate
6.6
0.0
Gynial
prepreat
Demam
Uaman 2010
Gemiin
Deprreet oage
Dosplesk
dke Kaay
GremnuZ..
Medium
Hard
Figure 8: Optimality Rate when LLMs are asked to resolve a matching with a single blocking pair introduced into the Optimal solution (One-Bi BP), or randomly generated matching (Random). These are is compared to the case when they are asked to generate a stable matching from scratch (Empty).
G Additional Material about Detecting Instability
G.1 Comparing Impartial Culture and Master-Liss Instances
Generally, the classification of a preference profile as an impartial culture or Master-list instance has relatively small impact the ability of LLM to detect instability in the instance. However, observe some differences between the ability of certain LLMs to detect stable/unstable matchings with ML instances compared IC instances. Models such as DeepSeek- 14B, 03-mini, and DeepScek-70BB are able correctly detect stable solutions significantly more frequently with ML instances than with IC instances. A potential explanation for this is that Master-list preferences contain fewer unique preference lists, decreasing the chances that the model hallucinates blocking pairs. On the other hand, models such as Gemini-2.00 2.0- and 3la-m--333-7BB correctly identify unstable solutions significantly more often with IC preferences compared to the case with ML preferences. The intuition for this observation the opposite: with impartial culture preferences, there higher probability of having blocking pairs, therefore models that tend to predict that solutions are unstable will perform better with impartial culture instances.
H
Fine-tuning Details
Models. We fine-tune four reasoning models:
DeepSeek-88 (eeppeaksa//pegsseee-lllllllll-e
DeepSeek- 14B ddeppeek-al/Pappsatttt----- Qwen-1Q0nnnn
Qwen-QwQ-32B (Qwen/ (wVem/QuQ-32B), and
Qwen3-32B (Qwen/Quen3-32B)
using the Unsloth 12
framework with parameter-efficient tuning (LoRA) B
Dataset. The dataset for the Generation task contains N 10000 samples for which the reasoning trace is generated using Python implementation of the DA algorithm. For the Preference Reasoning task, the dataset consists of N = 9000 samples (3000 for each question level), where the reasoning trace involves explicitly identifying the positions of agents in the concerned preferences. In both datasets, we include an equal number of IC and ML instances, with sizes ranging from n = to 50. Detailed examples of training examples for both tasks (Generation and Preference Reasoning) are provided in Appendix K
Model Setup. We used the FastLanguageModel. from load the base model with maximum sequence length of 10,000 tokens. The model was loaded in full
www.:frrooooaaaa_- pretrained interface from Unsloth to
12 Phttpss//unslthhaai ai/ Since results for Qwen-QwQ-ette QwQB32B and Qwen3-32B similar, show only those for the former in Table

---

precision (no quantization) and fine-tuned using Low-Rank Adaptation (LoRA) with the following settings:
Rank (r): 32
Target Modules: q.proj, k_proj, v_proj, o_proj, gate_proj. up_proj, down_proj
LoRA 32
LoRA Dropout:
Bias: none
Gradient Checkpointing: Enabled via www.gr/dwwa...eeeeeppiiiinnaaaaa
Training Configuration. Fine-tuning conducted using the SFTTrainer from the TRL library with the following training arguments:
Epochs:
Batch size per device: 2 (1, for Qwen-QwQ-32B)
Gradient accumulation steps: (2, for Qwen- QwBnn))
Learning rate: 2 x 10-1 with linear scheduler and warmup steps
Optimizer: Adamil-8bit
Weight decay: 0.01
Precision: Mixed precision (FP16 or BF16, based on hardware support)
Seed: 3407
Each model was fine-tuned using single NVIDIA H100 GPU (80GB RAM) with CUDA support; model and inputs were explicitly transferred GPU for inference and training.
Hardware.
Model Saving and Sharing. The resulting models were uploaded to the Hugging Face Hub and will be released upon acceptance.
Inference Setup. After fine-tuning, the model was evaluated using in-context inference. Inputs were formatted similarly to training prompts, and the model's output was parsed to extract the JSON-formatted matching solution.
Ablation tests. Table g illlstrates how performance is sensitive to variations in data-related pa- rameters such as the types instances included the data, range of instance sizes, and number of training examples, well as training-related parameters such the LoRA rank and the base model used. The primary observation from these tests is that easier training instances are more crucial that harder ones. For example, performance significantly better when the training data consists of only Easy (and smaller) instances, i.e. with n = 10, as compared to the case with only Hard instances (n = 50). Similarly, performance much better when the data consists of only ML instances, as opposed to the case where it consists of only IC instances, which are more difficult than the former.
I Inference Details
Fine-tuned Models. The models we fine-tune have been pushed to HuggingFace Hub and will be released upon acceptance.
Inference Configuration. For the task of generating stable solutions, inference performed on each of the open-source models such as DeepSeek-8B, DeepSeek-14B, Qwen-QwQ-32B, DeepSeek-70B, and Llama-3.3-70B,, with the following sampling parameters:
Temperature: 0.5
Maximum tokens: 30,000
25

---

Table 8: Performance (percentage of stable solutions generated) after fine-tuning, for DeepSeek-8B and Qwen3-32B, with different configurations of data- and training-related byper-parameters. Con- figuration 1 is the default configuration. The variation in each other configuration (as compared to config. 1) is in bold.
MI.
IC
Config.
Instance
Instamce sizes (range)
Training set size
LoRA
model
Easy
Mediom
Hard
Easy
Medium
types
rank
ML.,
[5.50]
10000
32
DeepSeek-8B
94
60
D
34
31,67
Qwen3-321B
ML
[5,50]
10000
32
DeepSeek-8B 8B
100
94
0
2
32.67
Qwen3-32B
100
34.33
IC
[5,50]
10000
32
DeepSeck-88
0
0
Qwen3-321
0.33
ML. IC
[5,50]
10000
64
D8
82
0
Qwen3-32B
100
100
100
100
66.67
MI.,
[5,50]
5000
32
DeepSeek-8B
46
0
Qwen3-3211
100
94
0
98
92
64
DeepSeek-88
ML.,
[5.10]
5000
32
Qwen3-32B
100
52
0
100
26
46.33
DeepSeek-8B
MI,,
[50,50]
Qwen3-32B
12
0
0
2.35
Default values were utilized for other sampling parameters. We used online APIs for the following models:
Gemini-2.0-Flast ('sssh"ggnn ("gemini-2.0-flash
03-mini ('o3-mini')
DeepSeek-RI ('deepseck-ressoner")
Gemini-2.5-Pro
Hardware. All inference experiments with open-source models were run on NVIDIA H100 GPUs (80GB RAM) with CUDA support; model and inputs were explicitly transferred to GPU for inference and training. We used single GPU for inference involving DeepSeek-8B and DeepSeck-14B, two GPUs for inference involving Qwen-QwQ-32BB and four GPUs for inference involving Llama-3.3-70B and DeepSeck-70B.
26

---

Prompts
J.1
Example prompt for Generating Stable Solutions
Vanilla prompt. The prompt used for generating stable solutions with LLMs follows standard prompting procedures, by first outlining the task, providing appropriate context, specifying constraints, and detailing the desired output format (a JSON object). We intentionally provide preferences in structured, tabular format. enables to isolate and rigorously evaluate the LLMs' reasoning. alignment, and solution quality relative to normative axioms (e.g.. stability). Natural language formulations introduce significant noise in both input and output, making difficult attribute performance failures to reasoning versus parsing. By grounding our analysis in tabular settings first, we can obtain clean and interpretable measurements, forming a benchmark for future extensions that incorporate naturalistic input.
Notice that despite the deferred-acceptanee algorithm never being mentioned the prompt, all models mentioned the
-acceptance algorithm in their responses. As mentioned in Appendix [ we use the traditional setting of stable-mariiage (where men propose women) considered by Gale and Shapley [27 while describing the problem in the prompt.
You are an intelligent assistant who is an expert in algorithms. Consider the following instance of the two-sided matching problem, where 10 men are to be matched with 10 women. Here the preference lists for all individuals: <preferences>
M: {
M1: W1 W3, W6. W4, W9, W8, W7, W5],
M2: W3, W2, W1, W9].
M10:
}.
W:
W1: [M2.M8.M9. 210.MB.M..M10.M5.. M10.M5.M7.M1 M4,M6,M3)
W2: [M2,M7,M3, M1,
W10:
))
</preferences>>
Your task is to find the proposer-optimal stable matching. You can use XML tags like <scratchpad>> to explain your thought process while computing the solution.
Once you have found stable matching, please return your matching in the JSON format given below:
<answer>
"M1": "<ooman matched with M1>",,
"M2": "<woman matched with M2>".
"M10": "<woman matched with M10>"
< //nswer>>>
Make sure that each man/woman matched with exactly ONE partner. is mandatory that you provide matching as a JSON object enclosed <answer>> </answer>> tags as described above.
27

---

Providing Algorithmic Description. The following is the prompt is modification of the vanilla prompt where the steps of the DA algorithm have been described to assist the model with implement- ing the same.
You are intelligent assistant who expert in algorithms.
</peferences>>>
Your task is to find the proposer-optimal stable matching. For this, you can use the Deferred Acceptance algorithm. The steps of this algorithm are described below: Initialize all men and women unmatched.
Create a list to keep track each man's next proposal (initially set for men).
3. While there are unmatched men:
a. Select an unmatched man (M).
Find the next woman (W) M's preference list that he hasn't proposed to yet.
unmatched, match and W.
d. If W is matched but prefers M to her current partner:
Unmatch W from her current partner.
Match M and W.
Set the unmatched man as W's previous partner. rejects M, move to the next woman on preference list.
Repeat step 3 until all men are matched.
You can use XML tags like <scratchpad>> to explain your thought process
mandatory that you provide matching as JSON object enclosed in <answer> </answer>> tags as described above.
Modified Problem Setting. The following a modification to the vanilla prompt, where the setting of task-allocation (assigning tasks to workers) is considered instead of the stable-marriag setting. We replace men with workers and women with tasks.
You are intelligent assistant who is an expert in algorithms. Consider the following instance of the two-sided matching problem, where workers to be assigned with 5 tasks, and each worker is assigned exactly one task.
Here are the preference lists for all workers (W) over tasks (T) and the preferences of tasks over workers:
<preferences>>
W: W1: [T5, T3, T4, T2, T1]
T:(
T1: (W3, W5, W4, W1, W2]
))
</preferences>>
Your task is find stable matching of workers and tasks. You can use XML tags like <scratchpad> to explain your thought process while computing the solution. Once you have found stable matching, please return your matching in the JSON format given below:
<answer>
W1": " "<aakk assigned to W1>",
"W5":
"<task assigned W5>"
</answer>>
Make sure that each worker is assigned exactly ONE task. It is mandatory that you provide matching JSON object enclosed in <answer><</answer> tags as described above.
28

---

J.2 Example Prompts for Prompt Engineering
J.2.1 CoT-Vanilla
Chain-of-Thought methods were applied the prompt Appendix 0.] by additionally including an example trace of steps performed when running the deferred-acceptante algorithm on randomly generated instance. The algorithm trace includes all proposals, all respective acceptances/rejeetionns and the resultant stable solution. The entire Chain-of Thought Chaig-of-Thought example is enclosed within <example>>
XML tags.
You are an intelligent assistant who is an expert in algorithms. Your task is find the proposer-optimal stable matching, for the two-sided matching problem. Here an example to demonstrate how you should proceed: <example>
<preferences>
M: {
M1: [W5, W1, W2, W4, W3],
M2: WW1,W2. W5, W3,
M3: [W4, W2.W33 W1, W5..
M4: [W5, W1, W2, W4, W3],
M5: [W3,W5, W5, W4, W1],
}.
W:
W1: [M2,33,MM N.R.M.,...44.. N15M4,M, M4.M1], ),
W2: [M5,M M1.5M2,,4,M4.
M3,M3,43,.... MM]
W3: [M2.M1. .M3M., N3,M5,M4
1M,,
W4: IM1,44,M MM4M5,. 144.M..M3. M2].
W5: MMM B}
</prefferecess>
M1 is free. M1 proposes to W5
Since W5 is free, W5 accepts the proposal. Now M1 and W5 are matched. M2 free. M2 proposes W1
Since W1 is free, W1 accepts the proposal. Now M2 and W1 are matched.
M3 is free. M3 proposes to W4
Since W4 is free, W4 accepts the proposal. Now M3 and W4 are matched.
M4 free. M4 proposes W5
Since W5 prefers M4 their current partner M1, W5 accepts the proposal. Now M4 and W5 are matched, and M1 is free.
M1 is free. M1 proposes to W1
Since W1 prefers their current partner M2 to M1, W1 rejects the proposal. M2 and W1 still matched, and M1 still free.
M1 is free. M1 proposes to W2
Since W2 is free, W2 accepts the proposal. Now M1 and W2 are matched.
M5 is free. M5 proposes to W3
Since W3 is free, W3 accepts the proposal. Now M5 and W3 matched.
<answer>
"M1": "W2".
"M2": "W1".
"M3": "W4".
"M4": "W5",
"M5": "W3"
</answer> </example>
Consider the following instance of the two-sided matching problem, where 10 men are to be matched with 10 women...
29

---

J.2.2 CoT-Shortlist
The main distinction between the prompt described here and the one in Appendix [12.1 lies in how the algorithm's 's execution is detailed. In the CoT-Shortlist prompt, the provided algorithm trace includes an additional step: agents remove each other from their respective shortlists if they become matched with a partner they find more desirable than the other agents on their list. All other aspects of prompt are identical to the Van-llnilla prompt.
You are an intelligent assistant who is an expert in algorithms. Your task is to find the proposer-optimal stable matching, for the two-sided matching problem. Here an example to demonstrate how you should proceed: <example>
<preferences>
M: {
M1: [W4, W3, W5, W2, W1],
M2: [W5, W4, W3, W1, W2],
M3: [W5, W4, W1, W2, W3],
M4: W4, W2, W1, W3],
M5: [W2,W4, W3, W1].
).
W: {
W1: NH5.M2,M3. M12.MM...11 M4.M1),
W2: [M3.M4.M5. M1. M22.
W3: [M4,M1. MMM4M,,M2,MM. MM, M3)3
W4: [M5,M1 M4,M3,M6 M2]
W5: [M1,44,M5, MM,3, )
</preferences>
M1 free. M1 proposes W4. W4 accepts the proposal. M1 and W4 are matched.
W1 deletes M4, M3, M2 from her list. M4, M3, M2 delete W4 from their list.
M2 is free. M2 proposes to W5. W5 accepts the proposal. Now M2 and W5 are matched.
M3 is free. M3 proposes to W5. W5 accepts the proposal. Now M3 and W5 are matched.
W5 prefers M3, so W5 breaks
engagement with M2.
W3 deletes M2 from her list. M2 delete W5 from their list.
M4 is free. M4 proposes to W5. W5 accepts the proposal. Now M4 and W5 are matched.
W5 prefers M4, so W5 breaks her engagement with M3.
W4 deletes M5, M3 from her list. M5, M3 delete W5 from their list.
free. M5 proposes W2. W2 accepts the proposal. Now M5 and W2 are matched.
W5 deletes M1, M2 from her list. M1, M2 delete W2 from their list.
<answer>
"M1": "W4".
"M2": "W3".
"M3": "W1".
"M4": "W5".
"M5": "W2"
</answer> </example>>
Consider the following instance of the two-sided matching problem, where 10 men are to be matched with 10 women...
30

---

J.2.3 Few-shot Examples
Few-shot prompting was applied the prompt Appendix J.T by additionally including series of randomly generated preference/stable solution pairs. As with other few-shot prompting strategies, the model is then asked to generate stable solution (as shown in Appendix 0.1 As with the CoT methods, each sample preference/stable solution pairs is enclosed in <example XMI tags.
You are an intelligent assistant who is an expert in algorithms. Your task is to find the proposer-optimal stable matching, for the two-sided matching problem. Here is an example to demonstrate how you should proceed: <example>>
<preferences>
M: {
M1: [W5, W3, W4, W2, W1].
M2: [W3, W4 W1, W2, W5].
M3: [W5, W1. W4, W2, W3],
M4: [W3,W2, W5, W1]
M5: [W3,W4 W1, W55. ).
W: [
W1: [M1,44,M, M.,MM.43.MMMM... M2),
W2: [M2.M4,M5.M
M3],
W3: MM1,M2,M4.M.. M3,
W4: MM3,55.M M1,M4,MM M2),
W5: M4, )}
</preferences>>
<answer>
"M1": "W3".
"M2": "W1".
"M3": "W5".
"M4": "W2",
"M5": "W4"
</answer> <example>>
<xample>>
/example>>>
<eample>>
</example>
Consider the following instance of the two-sided matching problem, where 10 men are to be matched with 10 women...
J.3 Example Prompt for Evaluating Stability
The following prompt requires LLMs to determine if given solution to provided preference profile is stable. Unlike the prompt in Appendix [ the only element that the LLM must include in their response is binary response (yes/no).
31

---

Consider the following instance of the two-sided matching problem, where men are to be matched with 5 women. Here are the preference lists all individuals: <preferences>
M: {
M1: W3, W2..111
}
W:
W1: [M3,M5,,M4,11,M22
</ppreference>>
Your task is to determine whether the following matching is stable or not. <matching>>
[[M1, W4],[M2, W5],[M3, W3],[M4, W1],[M5, W2].]
</matching>
Please return 'Yes' if you think the provided matching is stable and 'No' if you think it is unstable, and enclose your answer in <answer><<annswer> tags.
J.4 Example Prompts for Preference Comprehension
In each of the following preference comprehension prompts, models are asked to provide the name
of an agent (in level-1) or to provide binary answer (yes/no for levels and 3) in response to provided question. In addition changing the preference profiles for each instance a preference comprehension task, the agents and positions mentioned in the question are also changed with each instance. For details about each level of preference comprehension, view Section 6
J.4.1 Level-1
Your goal to correctly interpret the given preference lists and answer a specific question about agent preferences. First, here are the preference lists for all individuals: <preferences>>
M: { M1: ).
W: {
W1: [M3,M5,M4, MMM 14,,1,,M2 M2],
W2: MMM,MM).4,
})
</preferences>>>
Now, you will be asked a specific question about agent preferences: <question>>
Who is agent W2's, 1-most preferred agent?
</question>>
Once you have determined the answer, provide your output in the following format: 1. The solution as a single agent name. For example, "W1"
Present your final answer within <answer>> tags.
IMPORTANT: ONLY RETURN THE NAME OF THE SINGLE AGENT THAT IS THE ANSWER THE QUESTION. Do not include any explanations additional information your final answer.
32

---

J.4.2 Level-2
You an Al assistant tasked with analyzing preference profiles in a two-sided matching problem with one-to-one solutions. Your goal is to correctly interpret the given preference lists and answer a specific question about agent preferences. First, here are the preference lists for all individuals: <preferences>
M: {
M1: [35,W3, W3,.W33...2W111.
).
W: W1: MM3, MM2).
))
</peeerences>>> Now, you will be asked a specific question about agent preferences: <question>
Would agent W1, prefer M3 or M2 over M4?
</question>>
Once you have determined the answer, provide your output in the following format: 1. The solution as a YES or NO. For example, "NO"
Present your final answer within <answer>> tags.
IMPORTANT: ONLY RETURN YES OR NO THAT IS THE ANSWER TO THE QUESTION. Do include any explanations or additional information your final answer.
J.4.3 Level-3
You Al assistant tasked with analyzing preference profiles in two-sided matching problem with one-to-one solutions. Your goal correctly interpret the given preference lists and answer a specific question about agent preferences. First, here are the preference lists for all individuals: <preferences>>
M:
M1: WW5.W3,W4.W2,W1.
W: {
W1: M43
}}
</preferences>>
Now, you will asked a specific question about agent preferences:
<question;>
agent W1 is currently engaged to M4, would she accept proposals from M3 or M2? < /question
Once you have determined the answer, provide your output in the following format: The solution as a YES NO. For example, "NO"
Present your final answer within <answer>> tags.
IMPORTANT: ONLY RETURN YES OR NO THAT IS THE ANSWER TO THE QUESTION. Do not include any explanations or additional information in your final answer.
33

---

J.5 Example Prompt for Resolving Instability
For the task of resolving instability in given unstable solution, the prompt begins by providing models with the instance's 's preference profile (as with the prompts for the other tasks). In addition, the prompt includes an unstable matching, and asks the model resolve the instability by outputting stable solution (in an identical format to the prompt in Appendix I.1..
You are an intelligent assistant who is an expert in algorithms. Consider the following instance of the two-sided matching problem and respective unstable matching, where 5 men are to be matched with 5 women. Here are the preference lists for all individuals: <preferences>
M: {
M1: [W5, W3, W4, W1].
M2: [W2, W3, W5, W1, W4],
M3: [W5, W3, W1, W4, W2),
M4: W3, W2, W4],
M5: [W2,W3, W4, W1,W5].
)
W: {
W1: [M3.M5,M4 M1, M1,MM,M2]
W2: [M1M33, 11.
M4,
W3: M1..M2.M4,M1 M1.M5
W4: MM4,2,,M3 AM...3.M5. N1..M..11
W5: [M2,M4,MG M1,M5,M11...1 11,M1,,6 .M3]. }}
</preferences>>
Here an unstable matching.
<answer>
"M1": "W4".
"M2": "W5".
"M3": "W3",
"M4" "W2".
"M5": "W1"
</answer>
Your task modify the given unstable matching to make equivalent the proposer-optimal stable matching. You can use XML tags like <scratchpad>> to explain your thought process while computing the solution.
Once you have found stable matching, please return your matching in the JSON format given below:
<answer>
"M1": "<woman matched with M1>"
"M2": "<woman matched with M2>
"M3": "<woman matched with M3
"M4": "cwoman matched with M4>"
"M5": "<woman matched with M5>"
</answer>>
Make sure that each man/woman matched with exactly ONE partner. It is mandatory that you provide matching as JSON object enclosed in <answer>> </answer>> tags as described above.
34

---

J.6 Example Prompt for Repeated Queries Due to Missing JSON Object
For tasks where the desired output JSON object (when outputting stable solution), models given an additional opportunity to rectify issues in their response the original response is incorrectly formatted. The prompt below is passed the model help rectify issues related missing JSON objects. Note that the <initiallly passed prompt>> and <last 3,000 characters of LLM's s first response> XML tags are replaced by the initial prompt and the tail of the models initial response, respectively,
Previously, gave you the following task:
<initially passed prompt>
In your response, you either failed provide with matching did not adhere to the JSON format had asked for. Here are the last few lines of your response reference:
<last 3,000 characters of LLM's first response>
Please correct your response and provide me with the matching in the following JSON format, enclosed in
tags.<aama <answer>>
"M1": "<woman matched with M1>",
"M2": "<woman matched with M2>"
"M3": "<woman matched with M3>"
"M4": "<woman matched with M4
"M5": "<woman matched with M5
</answer>>
Make sure that each man/woman is matched with exactly ONE partner.
J.7 Example Prompt for Repeated Queries Due to Incorrectly Formatted JSON Object
Similar to the prompt Appendix J.6 the following prompt passed the model when the model's initial response contains an incorrectly formatted JSON object. Once again, the <initially passed prompt> and <last 3,000 characters of LLM's first response XML tags are replaced by the initial prompt and the tail of the models initial response, respectively.
Previously. gave you the following task:
<initially passed prompt>
In your response, you failed adhere to the JSON format had asked for. Here are the last few lines of your response for reference:
<last 3,000 characters LLM's first response>
Please correct your response and provide me with the matching in the following JSON format, enclosed in </nsser>></answer>>>>>> bogs.<answerr>>
"M1": "<woman matched with M1 >
"M2": "<woman matched with M2>
"M3": "<woman matched with M3>
"M4": "<woman matched with M4>
"M5": "<woman matched with M5>
< </answer>>
Make sure that each man/woman is matched with exactly ONE partner.
35

---

J.8 Example Prompt for Repeated Queries Due to Incomplete Matching
Similar to the prompt in Appendix J.6 the following prompt is passed to the model when the model's initial response contains a correctly formatted JSON object, but the matching itself is incomplete, or some agents have multiple partners. After the initially passed prompt, note that additional details are provided to assist the LLM in rectifying its response. Again, the <initially passed prompt> and <last 3, 3,000 characters of LLM's first response>> XML tags replaced by the initial prompt and the tail of the models initial response, respectively.
Previously, gave you the following task:
<initially passed prompt>
In your response, the matching you selected involves some women being matched with multiple men, which is not allowed. For example, W2 is matched with M1, M2, and M5. Additionally, W3, and W4 unmatched. Here are the last few lines of your response for reference:
<last 3,000 characters of LLM's first response>
Please correct your response and provide with the matching in the following JSON format, enclosed in <answer> </answe>>>>>>>>o tags.< <answer>>
"M1": "<woman matched with M1>",
"M2": "<woman matched with M2>"
"M3": "<woman matched with M3>
"M4": "<woman matched with M4>".
"M5": "<woman matched with M5:"
</answer>>
Make sure that each man/woman is matched with exactly ONE partner.
K Training Examples for Fine-tuning
K.1
System-prompt
This is the first part of the input, and is common across tasks.
Below is an instruction that describes a task, paired with an input that provides further context. Write a response that appropriately completes the request. Before answering, think carefully about the question and create step-by-step chain of thoughts ensure a logical and accurate response.
K.2 High-level instruction (u)
Generating:
### Instruction;
You are an intelligent assistant who is an expert in algorithms. Your task is to find the proposer-optimal stable matching, for the two-sided matching problem.
### Question:
Consider the following instance of the two-sided matching problem, where to be matched with 5 women.
Here are the preference lists for all individuals:
Comprehension:
36

---

### Instruction:
You are intelligent assistant who is an expert in algorithms. You will be given instance of the two-sided matching problem, and will be asked to answer a question about the preferences of the agents involved.
### Question: First, here are the preference lists for all individuals:
K.3 Preference Profile (p())
<preferences>
M: {
M1: [W5, W3, W4, W2, W1].
M2: W3, W5, W1, W4].
M3: [W5, W3. W1, W4, W2].
M4: [W1, W3, W2, W5, W4],
M5: [W2,W3,WA, W1, W5],
}.
W:
W1: N..3.M5,4.MM M2),
W2: [M1 M3,M4, M4,M5,M2
W3: 113.M2.44.M M5),
W4: M4. M3.M5,M11 ].
W5: M5, M3],,
ppeferences>>>>
preferences.>>>
K.4
Task-prompt (t))
Generating:
Your task find the proposer-optimal stable matching.
Once you have found stable matching, please return your matching the JSON format given below:
<answer>>
"M1": "<wwoman matched with M1:"".
"M2": "<woman matched with M2:"
"M3": "<woomn matched with M3>
"M4": "<woman matched with M4>"
"M5": "<woman matched with M5>"
</answer>>
Make sure that each man/woman is matched with exactly ONE partner. is important that you enclose your JSON object in <answer><<ansswer>> tags.
Comprehension (Level-1):
37

---

Now, you will be asked specific question about agent preferences: <question>>
Who is agent W3's, 5-most preferred agent? </question>>
Once you have determined the answer, provide your output in the following format: single agent name. For example, "W1"
1. The solution
Present your final answer within <answer> tags.
IMPORTANT: ONLY RETURN THE NAME OF THE SINGLE AGENT THAT THE ANSWER TO THE QUESTION. Do not include any explanations or additional infor- mation in your final answer.
Comprehension (Level-2):
Now, you will be asked a specific question about agent preferences: <question>>
Would agent W3, prefer M4 and M3 over M1? </question>>
Once you have determined the answer, provide your output in the following format: YES NO. For example, "NO"
1. The solution
Present your final answer within <answer>> tags.
IMPORTANT: ONLY RETURN YES OR THAT THE ANSWER TO THE QUES- TION. Do not include any explanations or additional information in your final answer.
Comprehension (Level-3):
Now, you will be asked a specific question about agent preferences: <question>>
If agent W5 is currently engaged to M3, would she accept proposals from M1 and M4?
</question>>
Once you have determined the answer, provide your output in the following format:
1. The solution YES or a NO. For example, "NO"
Present your final answer within <answer> tags.
IMPORTANT: ONLY RETURN YES OR THAT THE ANSWER TO THE QUES-
TION. Do not include any explanations or additional information your final answer.
The input (5) ends with the following text, to indicate the start of the chain-of silin-of-hhouse ttouggtht reasoning trace,
### Response:
<think>>
K.5
Reasoning-trace (r (r));;
Generating:
38

---

### Response:
<think>
Okay, need find a stable matching for 5 men and women. For this, use the Sale-Shapley algorithm. Before compute the solution for this instance, will list the steps of the Gale-Shapley algorithm.
1. Initialize all men and women as unmatched.
Create list keep track of each man's next proposal (initially set to for all men).
3. While there are unmatched men:
a. Select an unmatched man (M).
b. Find the next woman (W) on M's preference list that he hasn't proposed to yet.
C. If W is unmatched, match M and W.
d. W is matched but prefers M to her current partner:
Unmatch W from her current partner.
Match M and W.
Set the unmatched
W's previous partner.
e. rejects M, move the next woman on M's preference list.
4. Repeat step until all men are matched.
Next, will exectute the above algorithm for the given instance. The steps are as follows:
M1 is free. M1 proposes W3
Since W3 free, W3 accepts the proposal. Now M1 and W3 are matched.
M2 is free. M2 proposes to W5
Since W5 is free, W5 accepts the proposal. Now M2 and W5 are matched.
M3 is free. M3 proposes to W1
Since W1 free, W1 accepts the proposal. Now M3 and are matched. M4 is free. M4 proposes to W4
Since W4 is free, W4 accepts the proposal. Now M4 and W4 are matched. M5 is free. M5 proposes to W4
Since W4 prefers their current partner M4 to M5, W4 rejects the proposal. M4 and W4 are still matched, and M5 still free.
M5 is free. M5 proposes to W1
Since W1 prefers M5 to their current partner M3, W1 accepts the proposal. Now M5 and W1 are matched, and M3 is free.
M3 is free.
proposes W4
Since W4 prefers their current partner M4 to M3, W4 rejects the proposal. M4 and W4 are still matched, and M3 is still free.
M3 is free. M3 proposes to W3
Since W3 prefers their current partner M1 to M3, W3 rejects the proposal. M1 and W3 are still matched, and M3 still free.
M3 is free. M3 proposes to W2
Since W2 is free, W2 accepts the proposal. Now M3 and W2 are matched.
</think>
Comprehension (Level-1):
Alright, have been given the task of determining W3's 5-most preferred agent. For this, let me look at her preference list in order:
position 1: M4
position 2: M5
position 3: M1
position 4: M3
position 5: M2
Hence, W3's 5-most preferred agent M2.
</think>
Comprehension (Level-2):
39

---

Alright, have been asked to determine whether agent W3 would prefer M4 and M3
over M1. For this, let look W3's preference list in order:
position 1: M4
position 2: M5
position 3: M1
position 4: M3
position 5: M2
So, M4 is W3's 1-most preferred partner, M3 is W3's 4-most preferred partner, and M1 is W3's 3-most preferred partner. Hence, agent W3 preters M4 over M1, and agent W3 does not prefer M3 over M1. This means that the order of preference is M4 M1 M3.
Therefore, since the question was whether agent W3 would prefer BOTH M4 AND M3, given that it DOES NOT prefer M3 over M1, the answer is 'NO'.
</think>
Comprehension (Level-3):
Alright, have been asked to determine whether agent W5 would accept proposal from M1 or M4, if she currently matched with M3. For this, me look at W5's preference list in order:
position 1: M5
position 2: M4
position 3: M2
position 4:
position 5: M1
So, M1 is W5's 5-most preferred partner, M4 is W5's 2-most preferred partner, and M3 is W5's 4-most preferred partner.
Hence, agent W5 does not prefer M1 over their current partner M3, and agent W5 prefers M4 over their current partner M3. This means that the order of preference is M4 > M3 > M1.
Therefore, since the question was whether agent W5 would prefer EITHER M1 OR M4, given that prefers M4 M3, the answer 'YES'.
</think>
K.6
Answer (a)))
Generating:
<answer>
"M1": "W3",
"M5": "W1"
</answer>
Comprehension (Level-1):
<answer:M2<<answer
Comprehension (Level-2):
<answer-NO<</nswee>>
Comprehension (Level-3):
Ynswer>>ES<<aansee
40

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims made the abstract are an accurate representation of the paper's contributions and scope; more detailed summary of results and contributions is present in main paper.
Section I.] and detailed discussion for each result is present in subsequent sections in the
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The limitations of the work presented in this paper is included in the supple- mental material (present in the appendix)
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
41

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: All code and parameters required to run the experiments are present in the main paper and the supplemental material (the supplemental code).
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
42

---

reproducible, they 5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: All code used to run the experiments described in the main paper and appendix is available part of the supplemental material
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cc)
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/nips. wwtpcc/pccppcpcceeeooeoooop gwwcc//uu/ee//eee Seeeeeeee/ooeubbiiieceeee semiisssonPpe oiionccccy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All experimental settings and details (including model parameters) are detailed in the supplemental material (in the appendix, well as the supplemental code).
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification: The statistical significance tests used throughout the paper have been mentioned on Page 5 (footnote 4).
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
43

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: All details about computational resources used are mentioned in the supple- mental material (in the appendix)
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't fidn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: The research conducted in this paper conforms in every respect with the NeurIPS Code of Ethics
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: the broader positive and negative socictal impacts of this work are discussed in the supplemental work (in the appendix).
Guidelines:
44

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negatíve societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (c.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: While pretrained language models are used this paper, datasets and models mentioned in this paper randomly-generated and openly available data.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All original owners and creators of assets (code and models) have been properly credited and respected in both the main paper and supplemental materials.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
45

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperssi thooe cww datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: All assets introduced in the paper are well documented and openly available through the supplemental materials.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
46

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
This paper does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https://neurd) (btr:://eerrrpp.cc/o/oofeeeeeee/ /c/////oeeeeeeeee/222////.. for what should or should not be described.
47


Reviews:
[{"review_id": "5ofnt2lMQZ", "reviewer": "Reviewer_Jvsm", "summary": "The paper investigates whether current large language models can reason over ranked preferences in combinatorial settings by focusing on matching-market problems. The authors build a benchmark suite that escalates from generating stable matchings to detecting and resolving instabilities and answering fine-grained preference queries. Seven state-of-the-art models are tested. Results reveal that even the strongest LLMs regularly miss blocking pairs and struggle with the iterative logic needed to repair unstable matchings, especially as market size grows.", "questions": "**Questions for the Authors**\n\n1. Have you tested the benchmark—or a subset of it—on any real‐world matching-market data (e.g., residency matching or ride-sharing logs) to verify that the observed limitations persist outside synthetic instances?\n\n2. What factors drive the LoRA fine-tuning trade-off that improves large-market performance while degrading small-market accuracy? Could additional ablations (e.g., rank size, layer selection, or data volume) clarify this behavior?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n1. The paper targets an underexplored yet practically important domain—ranked-preference reasoning in matching markets—providing clear motivation and relevance to real-world allocation systems.\n2. It introduces a well-structured benchmark spanning four task types and varying market sizes, and evaluates seven strong LLMs plus LoRA fine-tuning, yielding a comprehensive empirical picture.\n\n**Weaknesses**\n\n1. All preference profiles are synthetically generated; the absence of real-world datasets limits external validity and may overstate model shortcomings.\n2. The study notes that LoRA helps on large markets but harms small ones, yet offers little diagnostic analysis or ablation to explain this scale-dependent trade-off.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and insightful questions. We shall address them below:\n\n> Have you tested the benchmark—or a subset of it—on any real‐world matching-market data (e.g., residency matching or ride-sharing logs) to verify that the observed limitations persist outside synthetic instances?\n\nOur work currently does not include tests on real-world data for two primary reasons:  \n1. **Lack of availability:** Human preference data from popular applications of matching markets, such as the National Resident Matching Program (NRMP), school choice programs in cities such as New York and Boston, and college admissions in various countries, is not publicly available.\n\n2. **Additional layers of complexity:** Public deployments typically involve incomplete lists, ties, programme capacities, and many‑to‑one constraints—often with hundreds of agents per side. Such variants are often NP-hard [1][2][3], and go beyond the scope of our present study, whose goal is to probe whether LLMs can execute even the baseline polynomial‑time procedures such as Deferred‑Acceptance (DA). We show that current models already fail on 50 × 50 one‑to‑one instances with complete and strict preferences; introducing larger, many‑to‑one markets would obscure the diagnosis without changing the takeaway.\n\n[1] Delorme, M., García, S., Gondzio, J., Kalcsics, J., Manlove, D., & Pettersson, W. (2019). Mathematical models for stable matching problems with ties and incomplete lists. European Journal of Operational Research, 277(2), 426-441.\n\n[2] Kwanashie, A., Manlove, D.F. (2014). An Integer Programming Approach to the Hospitals/Residents Problem with Ties. In: Huisman, D., Louwerse, I., Wagelmans, A. (eds) Operations Research Proceedings 2013. Operations Research Proceedings. Springer, Cham.\n\n[3] Manlove, D.F., O’Malley, G., Prosser, P., Unsworth, C. (2007). A Constraint Programming Approach to the Hospitals / Residents Problem. In: Van Hentenryck, P., Wolsey, L. (eds) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. CPAIOR 2007. Lecture Notes in Computer Science, vol 4510. Springer, Berlin, Heidelberg.\n\n> What factors drive the LoRA fine-tuning trade-off that improves large-market performance while degrading small-market accuracy? Could additional ablations (e.g., rank size, layer selection, or data volume) clarify this behavior?\n\nAs shown in our results (section 7), the performance drastically improves on smaller markets and fails to improve clearly on large markets. This is primarily due to the inability of models, even those with advanced reasoning capabilities, to handle large inputs - something we show throughout the paper. Since properly solving large instances requires a much larger number of steps, the likelihood of models making an error in the execution process is much higher (as discussed in section 6), leading to a much higher chance of failure.\n\nAblation with various hyperparameters in the fine-tuning pipeline provide additional insights. We observe that performance does not improve when only one type of instance (either IC or ML) is included in the training dataset, indicating that both types of instances are necessary for an overall improvement. Similarly, we observe that while a larger volume of data leads to better performance (e.g. 10000 samples vs. 5000), a larger LoRA rank (64 vs. 32) does not yield an improvement, indicating that a larger set of trainable parameters is not required for the model to learn the necessary reasoning patterns. We will update the paper with more detailed results.\n\nAny improvements, through fine-tuning or methods involving reinforcement learning that helps mitigate errors made by LLMs while reasoning about large preference profiles, will help improve performance on larger markets. A meaningful step in this direction could be to fine-tune LLMs to use tools that accurately answer comparative questions based on provided preferences, or keep track of intermediate states in the execution of the concerned algorithm."}, {"review_id": "DGxafCiCOV", "reviewer": "Reviewer_YmHR", "summary": "The paper delves into how LLMs handle ranked preferences in matching markets. By evaluating several models on tasks like generating stable solutions and detecting instability, the authors create a benchmark with diverse difficulty levels and preference distributions. The results show that existing models struggle with large-scale instances, often failing to identify blocking pairs or execute algorithms iteratively. The authors try to improve the performance by applying LoRA, which only works in small markets. IN summary, the paper reveals the limitations of existing LLMs in combinatorial reasoning.", "questions": "1. How do LLMs' performances on these tasks compare to traditional algorithmic solutions for matching markets? Are there certain situations where LLMs have advantages over traditional methods?\n\n2. The paper uses synthetic data. Could the authors talk about the possible difficulties and chances of using their discussion in real-world matching markets with more complex preference structures?\n\n3. The experiment only tests in strictly preferred cases(IC/ML distributions), which limits the conclusion's universality. Could the authors add some experiments on datasets with indifferent preferences?\n\n4. Please check formatting and detail errors of the paper, e.g., the garble error on line 301.", "limitations": "The authors have pointed out some limitations of their work. However, to make the paper better, it would be helpful to:\n\n1. Look into more strategies for improving LLM performance on large-scale instances in addition to LoRA fine-tuning.\n\n2. Offer a more in-depth comparison with traditional algorithmic approaches in this field to better understand the LLMs' performance.\n\n3. Discuss the possible challenges of applying this work in real-world situations with more complex preference structures.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "- Strengths:\n1. The paper reveals the limitations of LLMs from a special perspective, offering some directions for future research.\n2. The paper is well organized, and the experimental setup is rational, supporting its discussion and conclusion, making it easy to read and persuasive.\n\n- Weaknesses:\n1. The experimental results are based on synthetic data, and the paper does not thoroughly explore how well these findings generalize to real-world matching markets with more complex preference structures.\n2. The paper's exploration of methods to enhance performance is inadequate, making its contribution limited and lacking novelty.", "was_revised": true, "final_justification": "Thank you to the authors for the rebuttal. The responses have been helpful in clarifying the paper. However, I recommend that the authors incorporate the new discussions, experiments, and clarifications mentioned in the rebuttal into the final version of the paper.\n\nTherefore, I maintain my borderline accept rating.", "rebuttal": "We thank the reviewer for their suggestions on improving the paper, which we will take into consideration. Below we shall answer the questions they raise.\n\n> How do LLMs' performances on these tasks compare to traditional algorithmic solutions for matching markets? Are there certain situations where LLMs have advantages over traditional methods?\n\n**Why LLMs?**  There are efficient algorithms for finding solutions in standard matching markets. However, studying the performance of LLMs in matching markets is crucial for several reasons:\n\n-   **Widespread adoption of LLMs:** LLMs are becoming ubiquitous in everyday life, for example, doctors and nurses are reportedly using generative AI in the medical field. Consequently, laypeople are likely to rely on LLMs for tasks like matching since they may not know the appropriate algorithms or may lack the time to apply them.\n    \n\n  \n\n-   **Matching markets as a testbed:** Matching markets are nuanced systems with well-studied axiomatic properties, making them an ideal setting to evaluate the reasoning capabilities of LLMs.\n    \n\n  \n\n-   **Rise of LLM agents:** As autonomous LLM-based agents emerge, they must understand user preferences and make decisions on their behalf in alignment with those preferences.\n    \n\n  \n\n-   **Reasoning about preferences:** A key aspect of advanced reasoning is the ability to interpret and manipulate ranked preferences, a concept that spans domains from voting systems to market design.\n    \n\n  \n\n-   **Multi-agent interactions:** Many real-world problems require collective decision-making and compromise among agents—domains where reasoning over ranked choices and outcomes is essential.\n    \n\n  \n\n**Advantages over traditional methods.** While the stylized toy version of matching markets admit efficient algorithms, these problems often become computationally intractable (NP-hard) in the presence of weak preferences (ties) and incomplete/partial preferences.  \n  \n\nLLMs are fantastic for generating preferences [1], making them ideal not only in computing solutions when no efficient algorithms are known to exist, but also to complete and complement preferences when data about ranked preferences is unknown, ill-defined, or incomplete.\n\n  \n\nFinally, LLMs have the potential to function as end-to-end solutions for preference aggregation settings. Having an LLM-based decision system that can process natural language inputs from humans to identify preferences, apply appropriate algorithms to aggregate these preferences (ensuring desirable properties), and explain solutions to stakeholders involved, will streamline and enhance decision-making processes in diverse applications. In fact, various works already demonstrated the effectiveness of preference elicitation from natural language inputs using LLMs, in settings such as auctions [2] and course assignment [3].\n\n  \n  \n\n[1] Fish, S., Gölz, P., Parkes, D. C., Procaccia, A. D., Rusak, G., Shapira, I., & Wüthrich, M. (2023). Generative social choice. arXiv preprint arXiv:2309.01291.\n\n  \n\n[2] Huang, D., Marmolejo-Cossío, F., Lock, E., & Parkes, D. (2025). Accelerated Preference Elicitation with LLM-Based Proxies. arXiv preprint arXiv:2501.14625.\n\n  \n\n[3] Soumalias, E., Jiang, Y., Zhu, K., Curry, M., Seuken, S., & Parkes, D. C. (2025). LLM-Powered Preference Elicitation in Combinatorial Assignment. arXiv preprint arXiv:2502.10308.\n\n\n> The paper uses synthetic data. Could the authors talk about the possible difficulties and chances of using their discussion in real-world matching markets with more complex preference structures?\n\nThe challenges with using real-world data in our evaluation set-up are two-fold:\n\n  \n\n1.  **Lack of availability:** Real data from popular applications of matching markets, such as matching residents to hospitals, school choice programs in cities such as New York and Boston, and college admissions, is not publicly available due to privacy constraints.\n    \n\n  \n\n2.  **Increased complexity:** We show that even advanced reasoning LLMs fail in rather small and stylized markets (50x50 one-to-one instances). Real‑world applications are much larger, with hundreds or thousands of agents, and additional layers of complexity (e.g., incomplete preference lists, ties, programme quotas, and many‑to‑one capacities). Most of these variants either require more complicated algorithms, or are NP‑hard to solve exactly [1][2][3]. Hence, we suspect worse (or at best, the same) performance from LLMs in real-world settings, which are far more complicated.\n    \n\n  \n\n[1] Delorme, M., García, S., Gondzio, J., Kalcsics, J., Manlove, D., & Pettersson, W. (2019). Mathematical models for stable matching problems with ties and incomplete lists. European Journal of Operational Research, 277(2), 426-441.\n\n  \n\n[2] Kwanashie, A., Manlove, D.F. (2014). An Integer Programming Approach to the Hospitals/Residents Problem with Ties. In: Huisman, D., Louwerse, I., Wagelmans, A. (eds) Operations Research Proceedings 2013. Operations Research Proceedings. Springer, Cham.\n\n  \n\n[3] Manlove, D.F., O’Malley, G., Prosser, P., Unsworth, C. (2007). A Constraint Programming Approach to the Hospitals / Residents Problem. In: Van Hentenryck, P., Wolsey, L. (eds) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. CPAIOR 2007. Lecture Notes in Computer Science, vol 4510. Springer, Berlin, Heidelberg.\n\n> The experiment only tests in strictly preferred cases(IC/ML distributions), which limits the conclusion's universality. Could the authors add some experiments on datasets with indifferent preferences?\n\nOur results extend to the case when ties (indifference between alternatives) are present. If each tie is broken arbitrarily, the ordinary DA algorithm still returns a “weakly stable” matching [4]. Because this refinement requires no more procedural effort than the strict‑preference case, an LLM’s success rate on weak stability with ties can be expected to match, at best, its performance on strict preferences. Stronger notions such as “strong” and “super” stability are more demanding: a solution may not exist, and specialised tie‑handling variants of DA are needed [4].\n\n  \n\nThis is exactly what we observe through new experiments where we introduce ties in the preference lists. LLMs continue to apply the DA algorithm and ensure weak stability at the same rate at which they compute stable matchings when preferences are strict. However, less than 50% of the matchings computed in the former case satisfy notions such as strong or super stability.\n\n  \n  \n\n[4] Robert W. Irving. 1994. Stable marriage and indifference. Discrete Appl. Math. 48, 3 (Feb. 15, 1994), 261–272.\n\n\n> Please check formatting and detail errors of the paper, e.g., the garble error on line 301.\n\nWe were not able to locate the formatting error. We would appreciate it if you could share the exact sentence so we can address the error."}, {"review_id": "tG5diWJJEF", "reviewer": "Reviewer_e1sx", "summary": "This manuscript investigates the reasoning capabilities of LLMs in the domain of matching markets, a key area in economics, with a particular focus on their ability to handle preference rankings and execute structured algorithms. The authors construct a dedicated dataset and conduct comprehensive evaluations, and they further explore the use of LoRA-based SFT as a preliminary attempt to enhance LLM performance.", "questions": "See weaknesses.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "# Strengths\n1. The experiments presented in this manuscript are highly comprehensive, encompassing hierarchical tasks of varying difficulty levels, multi-dimensional evaluation metrics, diverse types of models, and well-controlled experimental variables.\n2. The manuscript establishes a standardized benchmark for the domain of matching markets.\n3. The study incorporates several state-of-the-art models, including DeepSeek-R1 and Qwen-QwQ-32B.\n\n# Weaknesses\n1. Although this manuscript effectively demonstrates the limitations of existing LLMs in tasks of matching markets, it does not provide a concrete solution. In the supplementary materials, I noticed the authors attempt to address this issue using reinforcement learning algorithms. However, I have concerns regarding this approach. Prior work has shown that post-training techniques—including SFT and reinforcement learning—do not inject new knowledge into LLMs. Rather, they serve primarily to align model outputs with human preferences (both correct and incorrect) via behavioral control, often improving performance from pass@N to pass@1. In contrast, the experimental results in this manuscript suggest that the models lack fundamental knowledge relevant to matching markets, rather than simply failing to align with correctness-related preferences. Therefore, I believe the authors need to better articulate the contributions of this work. A strong empirical study should inspire future research directions, yet this manuscript currently lacks a compelling discussion on potential avenues for follow-up work.\n2. What is the practical value of applying LLMs to matching markets? If such value is limited or unclear, what is the justification for introducing LLMs to a domain that has not traditionally relied on them?\n3. I believe including a comparison between LLM performance and that of human experts would significantly improve the manuscript’s clarity. Without such context, readers unfamiliar with the matching markets domain may find it difficult to judge whether the LLMs' low performance stems from the intrinsic difficulty of the task or from the models’ inadequacy.\n4. I would encourage the authors to provide several case studies to help elucidate the underlying reasons for LLM failure in this domain.\n5. The manuscript would benefit from a teaser figure to guide readers through its core contributions and structure.\n6. What is the difference between open-source and closed-source models? As I understand it, the distinction lies in whether the model developers publicly release the model parameters. However, this distinction is not inherently related to the model's performance.\n\n# Minor comment\n1. This work may be more suitable for the NeurIPS Benchmark Track rather than the NeurIPS Main Track.", "was_revised": true, "final_justification": "I have completed the full review of the manuscript and its rebuttal. \n\nI recommend the author to improve the readability of the manuscript, including adding teaser figures and case studies, to assist readers who are not Matching Markets.\n\nI maintain my borderline accept rating.", "rebuttal": "We thank the reviewer for their meaningful comments and questions, which we address below:\n\n> Therefore, I believe the authors need to better articulate the contributions of this work. A strong empirical study should inspire future research directions, yet this manuscript currently lacks a compelling discussion on potential avenues for follow-up work.\n\n  \n\nThe contributions of this work are three-fold:\n\n1.  In settings involving the aggregation of human preferences, we demonstrate that the ability of even the most advanced reasoning LLMs to reason about and execute straightforward algorithms does not scale with the input size (sections 3-5). This finding has implications across a wide-range of settings involving reasoning about human preferences such as voting, recommender systems, and resource allocation.\n    \n2.  We provide potential explanations for this phenomenon, by showing how LLMs make errors while reasoning about provided preferences, which can compound over a large number of steps that involve such reasoning (section 6).\n    \n3.  We illustrate the potential of supervised fine-tuning on synthetically generated reasoning traces in improving LLMs’ ability to compute correct solutions (section 7).\n    \n\n  \n\nThe jump‑in accuracy we see after trace‑level SFT on small markets shows that models do grasp both the deferred‑acceptance invariants and the step‑wise procedure once those steps are demonstrated explicitly. The residual failures with larger inputs therefore stem from computational bandwidth and hallucinations, rather than missing knowledge of the algorithms or setting. Concretely, the model must carry out ≈ n^2 propose/reject rounds while maintaining a growing state vector; attention and position‑encoding limits may cause the intermediate state to drift and compound. Closing this gap calls for methods that extend the effective reasoning horizon. Possible follow‑up directions are:\n\n-   **Step‑Level Reinforcement Learning:**  Reward models not just for final stability but for correct intermediate actions (valid proposal, correct understanding of preferences), extending the effective reasoning horizon without requiring longer context windows.\n    \n-   **Scratch‑Pad Execution with Verifier:**  Let the LLM run one proposal/reject round at a time on an external scratch‑pad, then call a lightweight checker that rejects states containing blocking pairs, creating an iterative self‑correction loop.\n    \n-   **Curriculum + Trace Distillation:**  Start with small reasoning traces for small inputs and gradually increase the input size, freezing lower layers as capacity grows.  \n      \n    \n\n  \n\n> What is the practical value of applying LLMs to matching markets? If such value is limited or unclear, what is the justification for introducing LLMs to a domain that has not traditionally relied on them?\n\n  \nAlthough efficient algorithms exist for solving problems in traditional matching markets, analyzing how LLMs perform in these contexts is important for several key reasons:\n\n-   **Growing Ubiquity of LLMs:** Large Language Models are becoming increasingly integrated into daily life. For instance, healthcare professionals are reportedly using generative AI tools in clinical settings. As a result, everyday users may turn to LLMs for tasks like matching, especially when they are unfamiliar with the correct algorithms or lack the time to apply them manually.  \n      \n    \n-   **Matching Markets as a Benchmark:** Matching markets offer a rich and theoretically grounded environment with well-established axiomatic structures. This makes them a valuable domain for assessing the reasoning abilities of LLMs.  \n      \n    \n-   **Emergence of LLM Agents:** As autonomous agents powered by LLMs become more prevalent, these systems will need to infer and act on user preferences, making informed decisions that align with individual goals.  \n      \n    \n-   **Reasoning with Ranked Preferences:** Sophisticated reasoning involves understanding and manipulating ranked choices—an essential capability across domains such as voting, market design, and social choice theory.  \n      \n    \n-   **Multi-agent Decision-Making:** Many practical problems involve negotiation and coordination among multiple agents, requiring reasoning over ordered preferences and group outcomes.  \n      \n    \n-   **Beyond Classic Algorithms:** While simplified matching problems can be solved efficiently, real-world scenarios often involve complexities like indifferences (ties) and partial information, with some versions being computationally intractable (NP-hard) [1][2].  \n      \n    \n\nAdditionally, LLMs excel at generating and completing ranked preferences [4], making them well-suited for solving problems where no efficient algorithm exists or where the input data is sparse or ambiguous.\n\nUltimately, LLMs have the potential to serve as comprehensive, end-to-end systems in preference aggregation tasks. Such a system could translate natural language inputs into formalized preferences, apply suitable aggregation algorithms while satisfying key normative criteria, and explain various aspects of the results clearly to stakeholders. In fact, several studies have already shown that LLMs are effective at extracting preferences from language in domains such as auctions [5] and course allocation [6].\n\n  \n\n[1] Delorme, M., García, S., Gondzio, J., Kalcsics, J., Manlove, D., & Pettersson, W. (2019). Mathematical models for stable matching problems with ties and incomplete lists. European Journal of Operational Research, 277(2), 426-441.\n\n  \n\n[2] Kwanashie, A., Manlove, D.F. (2014). An Integer Programming Approach to the Hospitals/Residents Problem with Ties. In: Huisman, D., Louwerse, I., Wagelmans, A. (eds) Operations Research Proceedings 2013. Operations Research Proceedings. Springer, Cham.\n\n  \n\n[3] Fish, S., Gölz, P., Parkes, D. C., Procaccia, A. D., Rusak, G., Shapira, I., & Wüthrich, M. (2023). Generative social choice. arXiv preprint arXiv:2309.01291.\n\n  \n\n[4] Huang, D., Marmolejo-Cossío, F., Lock, E., & Parkes, D. (2025). Accelerated Preference Elicitation with LLM-Based Proxies. arXiv preprint arXiv:2501.14625.\n\n  \n\n[5] Soumalias, E., Jiang, Y., Zhu, K., Curry, M., Seuken, S., & Parkes, D. C. (2025). LLM-Powered Preference Elicitation in Combinatorial Assignment. arXiv preprint arXiv:2502.10308.\n\n  \n  \n  \n\n> I believe including a comparison between LLM performance and that of human experts would significantly improve the manuscript’s clarity. Without such context, readers unfamiliar with the matching markets domain may find it difficult to judge whether the LLMs' low performance stems from the intrinsic difficulty of the task or from the models’ inadequacy.\n\n  \n\nGiven that there exist polynomial-time algorithms for computing and verifying solutions in the matching market setting, human experts use such algorithms for decision-making in applications such as the National Resident Matching Program (NRMP), school selection, and college admissions.The setting we consider is the most simplistic version of matching markets, involving ordinal preferences that are complete and strict (no indifference). Here, stable solutions are obtained using the Deferred Acceptance that requires a number of steps that is quadratic in the number of agents involved. While LLMs are able to solve this problem with 10 to 20 agents (on each side), they fail when the number of agents increases to 50. This reflects shortcomings of LLMs in handling larger context inputs rather than the growing difficulty of the task.\n\n  \n\n> I would encourage the authors to provide several case studies to help elucidate the underlying reasons for LLM failure in this domain.\n\n  \n\nThrough our analysis in section 6 (confirm), we shed light on potential reasons for LLMs' failure on large instances. The Deferred Acceptance (DA) algorithm requires keeping track of preference lists and accepted/rejected proposals at any given stage, and the accurate interpretation of preferences to move to the next step. We show that LLMs make errors on even such small isolated tasks. Since the size of the context and number of such steps increases with a factor of n^2, the errors made by LLMs compound and lead to a larger chance of failure in larger instances. We also show that LLMs make hallucinations about blocking pairs (sources of instability) while evaluating the stability of a given matching (section 5). While isolating the reason behind LLMs’ hallucinations in general is beyond the scope of this study, we clearly identify that their failure is not due to a lack of understanding of the economic knowledge necessary to reason about these problems, but from challenges with handling large context inputs.\n\n  \n\n> The manuscript would benefit from a teaser figure to guide readers through its core contributions and structure.\n\n  \n\nThat’s a great suggestion. We will definitely add such a diagram in the paper.\n\n  \n\n> What is the difference between open-source and closed-source models? As I understand it, the distinction lies in whether the model developers publicly release the model parameters. However, this distinction is not inherently related to the model's performance.\n\n  \nBeyond the (un)availability of model parameters, there is a lack of transparency regarding the training data and pipelines used to enhance the performance of closed-source models. Our comparison of both classes of models on the selected series of tasks aims to identify whether there is a clear gap, potentially due to the differences in training paradigms. Most importantly, it is not possible to modify closed-source models through post-training methods such as fine-tuning and reinforcement learning, limiting the amount of experimentation and control that researchers have for enhancing LLMs’ capabilities in this setting."}, {"review_id": "9s21x6CmUV", "reviewer": "Reviewer_xbG7", "summary": "The paper presents a study of LLM's ability on several matching related tasks—generating stable matchings, detecting and fixing instabilities, and answering preference queries. The authors curate a dataset comprising 2850 questions and find that across seven models, accuracy is reasonable on 10×10 markets (for reasoning models) but collapses on 50×50: outputs become unstable or invalid, blocking pairs are missed, and attempts to “repair” near-stable matchings often introduce new flaws. Parameter-efficient LoRA fine-tuning sharply improves small-scale performance yet leaves the large-instance failures unresolved, highlighting that current LLMs still lack robust, long-horizon algorithmic reasoning on these matching tasks.", "questions": "- Can the authors better summarize and present the key novelty and impact of their paper, in light of the points I raised in the weaknesses section\n- The case and result for finetuning perhaps warrant a deeper investigation. The authors claim in line 339 that \"... fine-tuning clearly improves the reasoning capabilities\". How is the training data generated? Are they all from the same settings? It will be helpful to know that this improvement is a true improvement in its reasoning capabilities, instead of overfitting / formatting improvement, and whether it generalizes to different matching types, e.g. is one finetuned on ML able to yield performance gain with IC distributions, and e.g. whether one finetuned on 50x50 data can improve performance on 10x10. It seems slightly puzzling why there's zero and even negative improvement in the hard setting if the conclusion is that there are improvements in reasoning capabilities.\n- Your benchmark encodes preferences in a highly compact, tabular form (e.g., “M1: [W5, W3, W4, W2, W1]”), whereas any real-world motivation for using an LLM—rather than calling the DA algorithm directly—would presumably involve free-form, natural-language preference statements. Have you experimented with preferences are expressed as natural sentences or excerpts on real items rather than numbered dummies? If not, what challenges prevent such an extension, and how might you expect model performance to change under more realistic textual inputs?\n- As mentioned above, SOTA LLM like GPT-O3 are equipped with tool-calling and evaluation functionalities. Do they possess the capabilities of computing the solution algorithmically by writing code, and if so how does this fit into the overall agenda of the paper?", "limitations": "yes", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 1, "originality": 2, "strengths_and_weaknesses": "Strength: this is an underexplored area bridging matching and LLM, it is an interesting topic and relatively clearly-written. There is sufficient experiments in the evaluation section.\n\nWeaknesses: \n\n- Intuitive, low-impact main finding – The headline result is that state-of-the-art “reasoning” LLMs underperform on classical matching tasks. Given that the deferred-acceptance (DA) algorithm is trivial to code, runs in $O(n^2)$ time, and guarantees stability, practitioners have no incentive to replace it with a brittle black-box whose accuracy collapses on 50 × 50 instances. Thus the negative outcome, while well documented, confirms an expectation rather than delivering a surprising finding or advance.\n\n- Limited novelty in empirical patterns – On top of the above, the authors do not end up deriving or proposing an approach that reliably closes the gap across the board, leaving little actionable guidance. Observations that larger models perform better and LoRA fine-tuning helps only on simple cases mirror the findings of prior reasoning benchmarks and papers, diluting the contribution’s impact. \n\n- Missing algorithmic baselines – The paper reports only language-only results. Omitting a direct DA baseline or a hybrid LLM-calls-DA agent prevents readers from quantifying the true performance gap and weakens the core motivation: if a ten-line Python DA script (easily produced by modern tool-calling LLMs) solves the problem perfectly, why test pure language execution at all? If there's little motivation to use pure language execution in the first place, then it undercuts the significance of the key negative result that the author tries to highlight.\n\n- Narrow benchmark scope – Another direction in light of the above is to consider this paper as a benchmark paper. However, the dataset comprises just 300 synthetic, one-to-one preference profiles from two stylized distributions, with no ties, quotas, or many-to-one constraints. Real markets are larger and messier, so the documented failure modes may not generalize, and the benchmark’s appeal may be limited to a small sub-community.\n\nTaken together, these points suggest the work functions more as a cautionary note than as a substantive advance, raising doubts about its novelty and significance for a broad-audience venue such as NeurIPS.", "was_revised": true, "final_justification": "The authors’ rebuttal is clear and thorough, but they echoes the reservations I had earlier - this is a setting where there exist simple algorithms that solve the problem without computational burden. Given this, the applicability and necessity of LLMs are inherently limited, as practitioners or advanced LLMs with tool-calling abilities can simply adopt simple algorithms to solve them easily, downplaying the paper's significance.\n\nOn the merits of using them as a new benchmark on improving LLMs, I'm also not certain that diagnosing these failures in such a simplified domain constitutes a major contribution for the main track. As the authors stated in the rebuttals, moving beyond tabular form introduces new complexities, but the current framework of using those tabular form inputs instead of natural language does not line up with the nascent field that tries to use natural language for matching or preferences. As such, I maintain my original assessment and score.", "rebuttal": "We appreciate the important points raised by the reviewer. We address their questions below:\n\n> Can the authors better summarize and present the key novelty and impact of their paper, in light of the points I raised in the weaknesses section\n\n1.  \"Intuitive finding\": While it is “expected” or “intuitive” that LLMs would fail with arbitrary large input sizes, we find it noteworthy that models with impressive performance on diverse reasoning tasks fail with inputs much smaller than those relevant in real-world scenarios. The fact that the input sizes are well below the context-window limits of each of these models, and since they understand and successfully execute the appropriate algorithms with even smaller instances, makes this finding less intuitive, given that the size of the input should not affect the ability to mechanically execute a series of steps. Furthermore, this is the first work (to the best of our knowledge) that evaluates LLMs in the domain of algorithmic reasoning with preferences.\n\n\n2.  \"Limited novelty in empirical patterns\": Through our analysis of LLMs’ ability to reason about the correctness of pre-computed solutions (section 5), about provided preferences (section 6), we identify how LLMs are susceptible to hallucinations that compound over a large sequence of steps, resulting in a failure to compute correct solutions. We show that this challenge is addressed for small markets by supervised fine-tuning on reasoning traces generated using a Python-based execution of the relevant algorithm.\n\n3.  \"Missing algorithmic baselines/benefits of natural language\": As is articulated in the paper, there exist polynomial-time algorithms for each task considered. Our question, hence, is not whether LLMs (tool-assisted or not) can improve over such algorithms, but instead whether they can reason about preferences as well as understand and execute the algorithms required to compute desirable solutions. The reason for this is precisely to leverage the natural language capabilities of LLMs, which have the potential to serve as an end-to-end solution for preference aggregation scenarios, where they can elicit preferences from natural language inputs [1][2], apply appropriate algorithms to aggregate these preferences (ensuring desirable properties), and ultimately explain solutions to stakeholders involved. For fool-proof explainability, it is essential that LLMs fully understand how solutions are computed. As we show in section 5 (“Detecting Instability”), even current SOTA reasoning LLMs are susceptible to errors in judgment about solutions that are pre-computed, which raises questions about their ability to effectively function as explainable systems when using tools to arrive at solutions.\n\n4.  \"Narrow benchmark scope\": The dataset we curate adequately allows us to demonstrate the shortcomings of LLMs in algorithmic reasoning with preferences. We specifically select IC and ML instances as representatives of two sides of the spectrum of correlation between preferences of different agents. While IC instances require the execution of the original DA algorithm, ML instances can be solved using a simplified version that runs in O(n) steps, allowing a comparison in terms of the complexity required to solve an instance. The reviewer correctly points out the existence of more complicated variations of the simplistic setting of one-to-one matching with complete and strict preferences. While some of these variations settings are NP-hard, those that can be solved in polynomial time require the execution of algorithms that are more complicated than the original (widely known) version of DA. Given the fact that LLMs fail to consistently execute even the simplest version of the algorithm, we suspect similar, if not worse, performance in more complicated settings.\n\nWe shall include more detailed discussions on the above points in the final version of the paper.\n\n\n[1] Huang, D., Marmolejo-Cossío, F., Lock, E., & Parkes, D. (2025). Accelerated Preference Elicitation with LLM-Based Proxies. arXiv preprint arXiv:2501.14625.\n\n[2] Soumalias, E., Jiang, Y., Zhu, K., Curry, M., Seuken, S., & Parkes, D. C. (2025). LLM-Powered Preference Elicitation in Combinatorial Assignment. arXiv preprint arXiv:2502.10308.\n\n> The case and result for finetuning perhaps warrant a deeper investigation ... It seems slightly puzzling why there's zero and even negative improvement in the hard setting if the conclusion is that there are improvements in reasoning capabilities.\n\n The training data used for fine-tuning consists of 10000 instances with sizes ranging from 5 agents on each side to 50 (Hard), and consists of both types of instances, i.e. IC and ML, in equal proportion. Each instance is generated randomly, and there is no overlap between instances in the training and evaluation sets. Given that any mistake in the execution steps of the DA algorithm would lead to incorrect solution, the fact that fine-tuning clearly enhances LLMs’ ability to compute stable matchings indicates some improvement in their ability to reason about preferences and execute the necessary steps.\n\nHowever, as we point out in the paper, this does not translate into a clear improvement in the case of larger markets (the models do improve in terms of the instability rate, but not in terms of the percentage of instances where stable matchings are computed). Additionally, based on a new set of experiments, we observe that including only a single type of instance (IC or ML) in the training data leads to an overall drop in performance, as compared to the case when both types are included. Similarly, models trained only on Hard instances (50x50) do not improve on Easy instances (10x10). While these observations indicate that LLMs perform better on the kind of instances they are trained on, they serve as a starting point for improving LLMs’ ability to solve problems involving the execution of algorithms and reasoning about preferences. For example, a meaningful next step is to combine fine-tuning with the use of step-level verification modules for preference reasoning, or modules that keep track of information about the algorithm's intermediate states (e.g. the proposals accepted/rejected).\n\n\nWe shall include more detailed results and discussions about the effect of different fine-tuning hyperparameters and ways to improve LLMs further, in the updated version of the paper.\n\n\n> Your benchmark encodes preferences in a highly compact, tabular form ... If not, what challenges prevent such an extension, and how might you expect model performance to change under more realistic textual inputs?\n\n While we show that LLMs are robust to the terminology used in describing the matching setting (e.g. “workers” and “tasks” instead of “men” and “women”), we do not evaluate LLMs using preferences expressed in natural language. The reason for that is simple—it adds another layer of complexity in the process, by adding a task that requires the interpretation of how various alternatives are compared with each other in natural language inputs. Since such expressions of preference in natural language often do not contain an interpretable order of alternatives that is complete and strict (often having inconsistencies such as cycles), we suspect the performance to decrease (or at best, stay the same) with the addition of this extra step.\n\n> As mentioned above, SOTA LLM like GPT-O3 are equipped with tool-calling and evaluation functionalities. Do they possess the capabilities of computing the solution algorithmically by writing code, and if so how does this fit into the overall agenda of the paper?\n\nThis is an important point raised by the reviewer. Through a few preliminary tests, we have verified that LLMs can indeed write Python code to solve the simplistic two-sided matching problem accurately. However, there are two important reasons why evaluating LLMs’ capabilities without tool use is relevant in this setting.\n\nThe first, as discussed above, has to do with their potential to act as end-to-end solutions that parse preferences expressed in natural language, execute the necessary procedures to compute desirable outcomes, and explain important aspects of the solutions to the (potentially large number of) individuals involved. While tool-use may assist LLMs in computing correct solutions, it does not guarantee that they can properly reason about such pre-computed solutions (as demonstrated in section 5).\n\nSecondly, most variants of matching markets in real-world applications have constraints that make the problems computationally intractable [1][2][3]. With improved capabilities, LLMs have the potential to act as optimizers that compute desirable solutions even in situations where polynomial-time algorithms do not exist.\n\n[1] Delorme, M., García, S., Gondzio, J., Kalcsics, J., Manlove, D., & Pettersson, W. (2019). Mathematical models for stable matching problems with ties and incomplete lists. European Journal of Operational Research, 277(2), 426-441.\n\n[2] Kwanashie, A., Manlove, D.F. (2014). An Integer Programming Approach to the Hospitals/Residents Problem with Ties. In: Huisman, D., Louwerse, I., Wagelmans, A. (eds) Operations Research Proceedings 2013. Operations Research Proceedings. Springer, Cham.\n\n[3] Manlove, D.F., O’Malley, G., Prosser, P., Unsworth, C. (2007). A Constraint Programming Approach to the Hospitals / Residents Problem. In: Van Hentenryck, P., Wolsey, L. (eds) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. CPAIOR 2007. Lecture Notes in Computer Science, vol 4510. Springer, Berlin, Heidelberg."}]

Author rebuttal:

Meta-review: This paper provides a valuable and comprehensive empirical study on the capabilities of LLMs to reason with ranked preferences in the context of matching markets. The reviews are largely positive, with three reviewers leaning towards acceptance.

* Strengths: The paper is commended for tackling an important and underexplored area (R-Jvsm, R-YmHR). It introduces a well-structured benchmark with a hierarchy of tasks and evaluates a strong suite of modern LLMs, providing clear evidence of their limitations on algorithmic reasoning, especially at scale (R-Jvsm, R-e1sx). The work is seen as a high-quality empirical study that establishes a standardized benchmark (R-e1sx).

* Weaknesses & Rebuttal: Reviewers raised concerns about the use of synthetic data (R-Jvsm, R-YmHR) and the lack of a novel solution to the identified problem (R-e1sx, R-xbG7). The authors provided convincing rebuttals, justifying the use of synthetic data due to the unavailability and added complexity of real-world data, and framing the work as a crucial diagnostic study that exposes core reasoning failures. This was sufficient to maintain the positive scores of three reviewers (R-Jvsm, R-YmHR, R-e1sx).

The paper's contribution lies in its rigorous demonstration of a fundamental gap in LLM reasoning. While the practical application of using a pure-language LLM for a task with a known algorithmic solution was questioned (R-xbG7), the authors successfully argue that this setting serves as an essential testbed for algorithmic fidelity. The findings are significant for understanding the scaling limits of reasoning in LLMs, and I believe this work will inspire valuable follow-up research.
Decision: Accept (poster)