Preference Reasoning under Indeterminacy in Large Language Models

# Preference Reasoning under Indeterminacyin Large Language Models
Source: [https://arxiv.org/html/2608.18631](https://arxiv.org/html/2608.18631)
Samarth Khanna111Corresponding author\.Affiliation:Penn State University, USAEmail:[samarth\.khanna@psu\.edu](mailto:)Xiyuan WangAffiliation:Penn State University, USAEmail:[xjw5253@psu\.edu](mailto:)

###### Abstract

As large language models evolve into decision\-making agents, the ability to reason over preferences becomes fundamental to alignment, coordination, and collective intelligence\. Yet, unlike standard benchmarks, real\-world preference reasoning is inherentlyindeterminate: information may be incomplete, and valid solutions may not exist\. We argue that indeterminacy, rather than correctness alone, is a central challenge for AI reasoning\. We formalize this challenge along two axes, \(i\)epistemic indeterminacy, arising from incomplete, partial, or expressive preferences, and \(ii\)structural indeterminacy, arising from the non\-existence of solutions under standard social choice concepts\. Across a hierarchy of tasks, we show that state\-of\-the\-art language models systematically fail to distinguish between determined and undetermined instances, exhibiting miscalibrated reasoning even in verification settings\.

## 1Introduction

Large Language Models \(LLMs\) have evolved from statistical language generators into systems capable of executing increasingly complex reasoning tasks, including logical inference and algorithmic problem solving\. This progression signals a shift toward models that operate over structured representations rather than purely linguistic patterns, enabling reasoning over preferences\.

Preference reasoning is a foundational component of modern AI systems, spanning across alignment, fine\-tuning, and recommender systems\. In agentic settings, LLMs are tasked with acting on behalf of users, requiring eitherimplicitorexplicitinference, comparison, and aggregation of potentially conflicting preferences when interacting with environments and other agents\. At scale, these mechanisms extend to collective decision\-making, where models are used to elicit and aggregate preferences into social judgments\[[26](https://arxiv.org/html/2608.18631#bib.bib5),[19](https://arxiv.org/html/2608.18631#bib.bib61)\], as in platforms such as Pol\.is, Remesh, and deliberative frameworks like the Habermas Machine\[[75](https://arxiv.org/html/2608.18631#bib.bib7)\]\.

Despite these advances, current evaluation paradigms for LLM reasoning rely primarily \(and often exclusively\) onclosed\-world benchmarksin which a ground\-truth solution is often assumed to exist\. However, real\-world decision\-making is inherently more complex, often characterized by undetermined scenarios in which preferences are incomplete or structural constraints preclude the existence of a valid solution under a given objective \(aka a solution concept\)\. This motivates a shift in assessing whether a model can distinguish between what is determined \(entailed by axioms or existing as a solution\) and what is undetermined \(not entailed or non\-existent\)\. With this lens, a central axis of evaluation extends beyond correctness to whether models can identify the boundary between determinacy and indeterminacy:Can advanced reasoning models identify whether a preference query is not answerable or whether a solution is infeasible under given specification?

We study preference reasoning under two distinct forms ofindeterminacy: \(i\)epistemic indeterminacy, arising from incomplete preference information, and \(ii\)structural indeterminacy, arising from the interaction between preference structure \(e\.g\., ties\) and solution concepts, which may render objectives infeasible even when preferences are fully specified\.111We avoid using the term “decidable/undecidable” since decidability is often used to imply computational tractability\. In this paper, we are concerned about epistemological determinacy when efficient algorithms exist\.This view is formally aligned with the Open\-World Assumption \(OWA\) and multi\-valued semantic frameworks such as Kleene’s three\-valued logic \(K​3K3\), in which propositions may take an explicit “unknown” or “indeterminate” truth value\[[48](https://arxiv.org/html/2608.18631#bib.bib1)\]\.

We ground our evaluation in classical economic problems over ranked preferences, which provide a principled testbed for reasoning under constraints\. These settings require models to interpret incomplete preferences and ties, resolve conflicts across agents, and satisfy global objectives defined by axiomatic solution concepts such as stability and welfare\. Crucially, these concepts distinguish between feasible and infeasible outcomes, making this domain ideal for evaluating not only reasoning accuracy but also indeterminacy\. Consequently, we transform indeterminacy into an observable and measurable failure mode of LLMs\.

![Refer to caption](https://arxiv.org/html/2608.18631v1/teaser.png)Figure 1:Overview of our taxonomy of evaluating LLMs’ reasoning with indeterminacy\.### 1\.1Main Results

We study preference\-based reasoning in LLMs and introduce a formal taxonomy of determined vs\. undetermined reasoning across increasing levels of complexity: \(i\)atomic queries, requiring retrieval from a single preference \(e\.g\., what is the rank of alternative ‘aa’?\); \(ii\)comparative queries, requiring entailment or refutation of relations \(e\.g\., whether ‘aa’ is preferred to ‘bb’\); \(iii\)aggregative queries, requiring aggregation across multiple preferences \(e\.g\., how many agents prefer ‘aa’ over ‘bb’?\); and \(iv\)structural \(algorithmic\) queries, requiring the construction of outcomes satisfying social choice solution concepts \(e\.g\., finding a matching solution in thecore\)\.

We leverage the nuanced interaction betweenpreference expressivity\(e\.g\., partial orders, ties, and incomplete lists\) and solution concepts from social choice to generate a spectrum of complex reasoning tasks within an axiomatic framework of indeterminacy\. Crucially, all tasks—both query resolution and feasibility determination—are computable in polynomial time using well\-established combinatorial algorithms, isolating reasoning, rather than computational hardness, as the primary challenge for LLMs\. Our main findings are as follows\.

1. 1\.Epistemic Indeterminacy: LLMs perform significantly worse on undetermined questions compared to determined ones, owing to systematic assumptions \(e\.g\. lexicographic ordering of preferences\) made when inputs are under\-specified\. Providing an explicit indeterminacy option helps on a subset of tasks, but models continue to exhibit systematic reasoning errors\.
2. 2\.Structural Indeterminacy: LLMs’ performance on tasks requiring algorithmic reasoning degrades rapidly with market size—even in settings where solutions are guaranteed to exist—and deteriorates further in the presence of structural infeasibility, with models failing both to correctly identify infeasible instances and to generate valid solutions when they do exist\. Providing anindeterminacy option\(aka “return null when infeasible”\) improves infeasibility detection but induces systematic bias, leading models to incorrectly declare non\-existence on feasible instances\.
3. 3\.Verification of Solution Concepts: Even in selection tasks where only verification is required \(as opposed to generation\), LLMs continue to select incorrect options even when valid solutions are present\. Although NOTA improves average accuracy, models seldom use this option, rarely abstaining even when no valid option is present, which reflects poor calibration in distinguishing feasible from infeasible cases\. In addition, LLMs exhibit a systematicintention–action misalignmentin preference reasoning: even when they appear to target a specific solution concept, the outcomes they select frequently fail to satisfy that concept, including in selection tasks where only verification is required\.
4. 4\.Assisted Reasoning: We consider assisted reasoning under two settings:\(i\) refinement via feedback, where models are given violations of the target property and attempt to iteratively repair invalid solutions, and\(ii\) reasoning with code execution, where models generate and execute programs to solve instances\. While both settings improve performance, the gains are largely driven by brute\-force enumeration on small markets and heuristic search on larger instances, neither of which scales to deployment\-relevant market sizes\.

### 1\.2Related Work

LLM Reasoning and Abstention\.A growing body of work evaluates LLMs as procedural reasoners\. Recent benchmarks show that LLMs fail to reliably execute classical algorithms as instance size grows\[[31](https://arxiv.org/html/2608.18631#bib.bib14),[70](https://arxiv.org/html/2608.18631#bib.bib58)\]\. A separate but related literature studies whether models know when to abstain: frontier models systematically miscalculate their uncertainty\[[46](https://arxiv.org/html/2608.18631#bib.bib28),[83](https://arxiv.org/html/2608.18631#bib.bib25)\], hallucinate confidently even on questions they could answer correctly\[[71](https://arxiv.org/html/2608.18631#bib.bib29),[1](https://arxiv.org/html/2608.18631#bib.bib27)\], and in many settings fail to abstain at all\[[47](https://arxiv.org/html/2608.18631#bib.bib36)\]\. Our findings sit at the intersection of these threads\. Our findings sit at their intersection, linking procedural failure with abstention failure in preference reasoning\.

Beyond the fact that these benchmarks pose questions in natural language and do not consider structured preferences, two differences matter\. First, because the ways of resolving an underdetermined query are enumerable in our setting, we identify the specific assumption a model substitutes for the missing information \(e\.g\., ordering bundles by their highest\-ranked item\) rather than only whether it failed to abstain\. Second, and more importantly, our benchmark includes problems for which the requested solution does not exist at all, a case with no counterpart in the abstention setting\.

LLMs in Economic Settings\.Adjacent literature evaluate LLMs as agents in economic and social\-choice contexts\. On strategic decision\-making, recent reasoning models come closer to equilibrium play than earlier ones\[[43](https://arxiv.org/html/2608.18631#bib.bib71),[79](https://arxiv.org/html/2608.18631#bib.bib32)\]but remain susceptible to anchoring effects\[[61](https://arxiv.org/html/2608.18631#bib.bib21),[58](https://arxiv.org/html/2608.18631#bib.bib33)\]and Bayesian inconsistency\[[81](https://arxiv.org/html/2608.18631#bib.bib24),[37](https://arxiv.org/html/2608.18631#bib.bib22)\]\. Computational social choice, an extensively studied domain on which we build\[[53](https://arxiv.org/html/2608.18631#bib.bib40),[4](https://arxiv.org/html/2608.18631#bib.bib44),[23](https://arxiv.org/html/2608.18631#bib.bib47)\], has begun engaging with LLMs both as fairness\-aligned allocators\[[32](https://arxiv.org/html/2608.18631#bib.bib15),[20](https://arxiv.org/html/2608.18631#bib.bib8)\]and as solvers of canonical solution concepts\[[31](https://arxiv.org/html/2608.18631#bib.bib14),[27](https://arxiv.org/html/2608.18631#bib.bib17)\], alongside applications to voting and participatory budgeting\[[82](https://arxiv.org/html/2608.18631#bib.bib68),[76](https://arxiv.org/html/2608.18631#bib.bib20)\]\. A parallel line of work uses LLMs as proxies in preference elicitation pipelines\[[29](https://arxiv.org/html/2608.18631#bib.bib19),[36](https://arxiv.org/html/2608.18631#bib.bib67),[50](https://arxiv.org/html/2608.18631#bib.bib30)\], to which our work also contributes by characterizing how reliably LLMs parse structured preferences\.[AppendixD](https://arxiv.org/html/2608.18631#A4)contains an extended related work\.

## 2Preference\-Based Tasks and Methodology

### 2\.1Formalizing Problems and Solution Concepts

Problem Domains\.We consider three economic problems requiring reasoning over preferences:house \(or object\) allocation\[[73](https://arxiv.org/html/2608.18631#bib.bib10)\],Shapley\-Scarf housing marketswith endowments\[[68](https://arxiv.org/html/2608.18631#bib.bib59)\], andtwo\-sided matching markets\[[28](https://arxiv.org/html/2608.18631#bib.bib66)\], each with increasing structural complexity and distinct axiomatic solution requirements\. LetAAdenote a set of agents andBBa set of alternatives \(objects\)\. Each agenti∈Ai\\in Ais endowed with a preference relation⪰i\\succeq\_\{i\}overBB, which is a weak and potentially partial order\. We writeb1≻ib2b\_\{1\}\\succ\_\{i\}b\_\{2\}if agentiistrictly prefersb1b\_\{1\}tob2b\_\{2\}, andb1⪰ib2b\_\{1\}\\succeq\_\{i\}b\_\{2\}ifiiweakly prefersb1b\_\{1\}tob2b\_\{2\}, allowing indifference\. In two\-sided markets eachb∈Bb\\in Blikewise holds a preference relation⪰b\\succeq\_\{b\}overAA\. In settings with incomplete preferences,ϕ≻ib\\phi\\succ\_\{i\}bindicates thatbbis not present in agentii’s preference list and is thus unranked or incomparable\. Apreference profileis the collection of all agents’ preferences, denoted by⪰=\(⪰a1,…,⪰am,⪰b1,…,⪰bn\)\\succeq=\(\\succeq\_\{a\_\{1\}\},\\dots,\\succeq\_\{a\_\{m\}\},\\succeq\_\{b\_\{1\}\},\\dots,\\succeq\_\{b\_\{n\}\}\), wherem=\|A\|m=\|A\|andn=\|B\|n=\|B\|\.

In ahouse allocationproblem, agents inAAare assigned objects inBBwith no initial endowments; in theShapley–Scarf housing market, each agenti∈Ai\\in Ais initially endowed with an objectei∈Be\_\{i\}\\in B, forming an exchange economy; and intwo\-sided matching markets, agents inAAandBBboth have preferences over each other, inducing bilateral matching constraints\. Amatchingis a mappingμ:A∪B→A∪B\\mu:A\\cup B\\rightarrow A\\cup Bsuch that for alla∈Aa\\in A,μ⁡\(a\)∈B∪\{∅\}\\mu\(a\)\\in B\\cup\\\{\\emptyset\\\}and for allb∈Bb\\in B,μ⁡\(b\)∈A∪\{∅\}\\mu\(b\)\\in A\\cup\\\{\\emptyset\\\}, with the properties that each agent and object is matched to at most one counterpart andb=μ⁡\(a\)b=\\mu\(a\)if and only ifa=μ⁡\(b\)a=\\mu\(b\)\.

Solution Concepts\.Preferences and market structure induce standardsolution concepts: in house allocation, the primary objective isPareto optimality; in Shapley–Scarf markets, the central solution concept is thecore, where no coalition of agents can reallocate their endowments to make all members strictly better off; and in two\-sided matching markets, the standard concept isstability, requiring that no blocking pair exists\. All three settings admit polynomial\-time algorithms for computing canonical solutions and verifying feasibility under standard assumptions\.

Stronger Notions under Ties\.When preferences admit ties, the canonical solution concepts above split into refinements that differ in their robustness to indifference\. In Shapley–Scarf markets, aweak coreallocation is one that no coalition can strictly improve upon, while thestrict corerequires that no coalition can find a reallocation under which every member is weakly better off and at least one is strictly better off\. In two\-sided matching, an analogous hierarchy arises: a matching isweakly stableif no pair strictly prefers each other to their current partners;strongly stableif no pair contains an agent who weakly prefers a partner who strictly prefers them back; andsuper stableif no pair contains agents who weakly prefer each other\. The stronger refinements \(strict core, strong stability, super stability\) may be infeasible for some instances, generating the structural indeterminacy we study in[Section4](https://arxiv.org/html/2608.18631#S4)\.[SectionE\.1](https://arxiv.org/html/2608.18631#A5.SS1)provides detailed formalisms, and a review of the relevant algorithms\.

### 2\.2Methodology and Experimental Setup

Preference Expressivity and Reasoning Tasks\.Preference expressivity gives rise to nuanced query tasks and solution concepts; we consider a spectrum of structures ranging from strict complete orders \(SO\), strict but possibly incomplete orders \(SI\), complete orders with ties \(TO\), and incomplete orders with ties \(TI\), as well as general partial orders \(See[Table2](https://arxiv.org/html/2608.18631#A5.T2)\)\.

We categorize evaluation into a hierarchy of increasing complexity to isolate where LLMs fail:atomic queriestest direct preference retrieval,comparative queriestest relational entailment/refutation,aggregative queriestest collective preference computation, andstructural \(algorithmic\) queriestest the ability to construct or verify solution concepts given an instance\.[Table1](https://arxiv.org/html/2608.18631#S2.T1)provides representative examples of determined and undetermined tasks in each category\.

Queries\.For preference queries, we distinguish betweendeterminedqueries, whose answers are uniquely implied by the input preferences, andundeterminedqueries, where the available information is insufficient to resolve the query\. Formally in logic, the former corresponds to whether the query isentailed\(orrefuted\) by the preference instance, while the latter implies lack of information\. For example, preferencea≻ca\\succ cis determined if it is a necessary consequence of the provided axioms \(e\.g\.,a≻ba\\succ bandb≻cb\\succ cvia transitive closure\)\. Otherwise, it is undetermined\.

An undetermined query is scored correct only if the response indicates that the answer cannot be determined\. A response that commits to an answer counts as incorrect even when it names the assumption it relied on\.[SectionH\.3](https://arxiv.org/html/2608.18631#A8.SS3)re\-scores those responses as correct and shows that the gap is essentially unchanged\.

For algorithmic queries, given an instance, a solution concept isfeasibleif there exists a solution satisfying the concept, andinfeasibleotherwise\. For example, an instance of a matching market may admitnosuper stable matching, in which case it is infeasible with respect to super stability\.

This taxonomy enables us to move beyond “accuracy” and instead evaluate the Invalid Rate, i\.e\. the frequency with which a model produces a “determined” response to an “undetermined” query\. This measure captures speculative completion, or thehallucination of certainty\[[71](https://arxiv.org/html/2608.18631#bib.bib29),[1](https://arxiv.org/html/2608.18631#bib.bib27)\], providing a principled diagnostic of a key failure mode in LLM reasoning\.

Table 1:Taxonomy of preference reasoning tasks, each exhibiting determined or undetermined instances depending on preference expressivity and feasibility of solutions\.Task TypeSubtypeExample \(Determined / Undetermined\)AtomicRank retrievalDetermined: rank ofaain⪰i\\succeq\_\{i\}
Undetermined: rank ofbbunder incomplete listComparativePairwise, RS\-extension, rankingDetermined:a≻iba\\succ\_\{i\}bholds
Undetermined:a≻iba\\succ\_\{i\}bunder partial informationAggregativePreference aggregation \(counts\)Determined:\#\{i:a≻ib\}\\\#\\\{i:a\\succ\_\{i\}b\\\}
Undetermined: count under missing comparisonsStructuralCore, stability \(weak/strong/super\)Determined: existence of stable matching
Undetermined: existence under ties / incompletenessModels\.We evaluate four large language models that achieve state\-of\-the\-art results in reasoning and coding benchmarks \(see, for example\[[60](https://arxiv.org/html/2608.18631#bib.bib73),[44](https://arxiv.org/html/2608.18631#bib.bib70)\]\):GPT\-5\.2\[[72](https://arxiv.org/html/2608.18631#bib.bib11)\],Gemini\-2\.5\-Pro\[[21](https://arxiv.org/html/2608.18631#bib.bib69)\],Claude\-4\.5\-Sonnet\(Claude\-4\.5\-S\)\[[6](https://arxiv.org/html/2608.18631#bib.bib13)\], and a frontier\-class open\-source modelOSS\-120B\[[3](https://arxiv.org/html/2608.18631#bib.bib12)\]\.

Prompt Generation\.Each model was queried3030times on a given question type \(See Appendix[K](https://arxiv.org/html/2608.18631#A11)for the prompt\-templates used for each type of task\)\. Each query is a zero\-shot, single\-turn setting at the default temperature\. In addition, we evaluated the models through two critical variations: i\)multi\-shot refinements with feedback, enabling models to refine and evaluate responses, and ii\)code\-execution capability, enabling multiple iterations and with the ability to write code and verify responses \([Section5](https://arxiv.org/html/2608.18631#S5)\)\. Throughout the paper, we report results at four reference sizes by the number of agents/itemsnn:Small\(n=10n\{=\}10\),Modest\(n=30n\{=\}30\),Medium\(n=50n\{=\}50\), andLarge\(n≥100n\\geq 100\)\.

## 3Epistemic Indeterminacy: Preference Reasoning

We begin with epistemic indeterminacy: cases where a question is not answerable based on the information provided in the input preferences\. Across the three query families introduced in[Section2\.2](https://arxiv.org/html/2608.18631#S2.SS2)\(atomic, comparative, and aggregative\), we vary preference expressivity \(i\.e\. completeness, ties, partial orders\) to construct analogous questions ofdeterminedandundeterminedinstances on the same profile222By default, we use structured JSON format to express preference profiles as inputs to the models\. In[SectionH\.5](https://arxiv.org/html/2608.18631#A8.SS5)we include an additional experiment of rendering preferences in natural language, and demonstrate that our findings persist in that setting as well\.\(see[SectionF\.1](https://arxiv.org/html/2608.18631#A6.SS1)for details on how each type of question is designed\)\.[Figure1](https://arxiv.org/html/2608.18631#S1.F1)illustrates a few examples per query type\. Our experiments investigate three criteria, \(i\) how performance depends on whether a query is determined, \(ii\) how it scales with input size, and \(iii\) how it depends on the way the question is framed\.333We report model accuracy, aggregated by problem types in the plots\. We include statistical analysis of each single experiment and paired comparisons in the corresponding tables in the appendices\. An overview of our statistical methods is in[AppendixJ](https://arxiv.org/html/2608.18631#A10)\.

Figure 2:Comparing LLMs’ performance \(a\) on determined vs\. undetermined preference queries, and \(b\) with different prompting formats on undetermined preference queries, split by task type\.Determined vs\. Undetermined Queries\.We compare performance on determined and undetermined queries across the question types in[Figure1](https://arxiv.org/html/2608.18631#S1.F1), considering Medium and Large preferences\. To reflect a more realistic setting, queries are issued in afree\-flowformat that does not provide explicit options to choose from\. Responses are scored against the ground truth on determined queries, and on whether the model correctly indicates that the question is unanswerable, on undetermined ones \(see[AppendixK](https://arxiv.org/html/2608.18631#A11)for the exact prompt templates\)\.[Figure2](https://arxiv.org/html/2608.18631#S3.F2)\(a\) shows that accuracy on undetermined queries is substantially lower than on the matched determined queries, collapsing to near\-zero in several settings\. The gap is driven by assumptions the models silently impose on the input, which suppress the under\-specification rather than flag it\. The gap is smallest on atomic queries, where the model only has to notice that an item is missing from the list, and largest on comparative queries, where nothing is missing and it has to work out that no answer follows from the preferences it was given\.

Figure 3:Behavior of LLMs on RS\-incomparable bundle comparisons \(a\), aggregated across different preference types, and partial\-order pairwise queries \(b\)\.LLMs’ Systematic Biases\.We illustrate two such patterns, on bundle comparisons and on partial\-order pairwise queries\. Two bundles areresponsive set\(RS\) incomparable when neither can be paired with the other via an injection that maps each item to a weakly preferred counterpart\. Intuitively, neither bundle dominates the other item\-by\-item\. Resolving such a comparison requires an extra\-axiomatic assumption, such as the lexicographic rule, which compares bundles by their most\-preferred item, breaking ties by the next\-most\-preferred\. As[Figure3](https://arxiv.org/html/2608.18631#S3.F3)\(a\) shows, all four models default to lexicographic ordering on almost every RS\-incomparable pair, across multiple preference types\. We show in[SectionH\.3](https://arxiv.org/html/2608.18631#A8.SS3)that only in a small numbers of responses, this ordering is explicitly flagged as an "assumption", while others default to the rule silently\. This assumption also persists even when the lexicographically weaker bundle is much larger \(20 items vs\. 1\)\.

Partial\-order queries elicit a different pattern\. To answer whetheraais preferred tobb, a model must check whether the stated comparisons induce a chain between the two items; if no chain exists in either direction, the pair is incomparable\.[Figure3](https://arxiv.org/html/2608.18631#S3.F3)\(b\) shows that models split into two failure modes\. Claude\-4\.5\-S and Gemini\-2\.5\-Pro commit on undetermined pairs by either rejecting the input as incorrectly specified or using ad\-hoc heuristics such as out\-degree counts in the DAG induced by the stated comparisons \(See[SectionH\.4](https://arxiv.org/html/2608.18631#A8.SS4)for details\), at the cost of accuracy when no chain exists\. OSS\-120B and GPT\-5\.2 do the opposite: they perform an incomplete search and prematurely conclude that two items are incomparable, scoring well on undetermined queries but poorly on determined ones where a chain does exist\.

Framing Effects\.The free\-flow prompt used above does not signal that a query may be undetermined\. To test whether the indeterminacy gap reflects a reasoning failure or a framing artefact, we evaluate two prompt variations:free\-flow \+ “if known”, where the prompt ends with the qualifier “if known”, andMCQ, where the model chooses among a set of options that includes “there is not enough information to decide” \(see[AppendixK](https://arxiv.org/html/2608.18631#A11)for the exact prompts\)\.[Figure2](https://arxiv.org/html/2608.18631#S3.F2)\(b\) shows that providing a way to report indeterminacy improves how often models do so depending on the task, with the largest gains under MCQ\. However, we show in[SectionH\.4](https://arxiv.org/html/2608.18631#A8.SS4)through the example of partial\-order queries, the MCQ format is potentially a double\-edged sword\. It improves Gemini\-2\.5\-Pro’s detection of indeterminacy while biasing Claude\-4\.5\-S into selecting that option even when the query is determined\.

Scaling\.Beyond the indeterminacy gap, accuracy degrades as the input grows\.[Figure7](https://arxiv.org/html/2608.18631#A8.F7)\([AppendixH](https://arxiv.org/html/2608.18631#A8)\) shows a clear decline as the number of alternatives or agents moves from 100 to 200\. The decline is more pronounced on determined queries: models make essentially no errors on atomic and comparative queries up to size 100, but begin to fail at size 200\.

## 4Structural Indeterminacy: Algorithmic Reasoning over Preferences

Algorithmic reasoning over preferences extends beyond preference inference, requiring models to \(i\) interpret structured preference profiles, \(ii\) execute multi\-step procedures, and \(iii\) satisfy the constraints imposed by a target solution concept\. In this setting, a fundamental challenge arises fromstructural indeterminacy: even under fully specified preferences, a solution concept may be infeasible for a given instance\. This phenomenon is central to computational social choice, where the interaction between preference domains \(e\.g\., strict versus weak orders\) and solution concepts \(e\.g\., core stability or matching stability notions\) governs the existence of admissible outcomes\.

In this section, we systematically evaluate the ability of large language models to reason in such settings\. Specifically, we investigate: \(i\) whether LLMs can carry out algorithmic reasoning reliably as market size and problem complexity scale across different solution concepts; \(ii\) whether they can correctly identify infeasible instances, where no solution exists; and \(iii\) whether their behavior changes when provided with anindeterminacy option, allowing them to indicate that no valid solution can be found\. We sample instances based on Impartial Culture\[[13](https://arxiv.org/html/2608.18631#bib.bib65),[24](https://arxiv.org/html/2608.18631#bib.bib64)\]\(i\.e\. uniformly at random\), and perform arejection samplingstrategy to include an equal number of feasible and infeasible instances \(for solution concepts that admit both types\)\. See[SectionF\.2](https://arxiv.org/html/2608.18631#A6.SS2)for further details on how instances are created\.

### 4\.1Scaling, Infeasibility, and Indeterminate Option

\(a\)Decrease in accuracy of computing solutions due to an increase in input size, across different domains\.\(b\)Performance on the generation task by model, problem size, and existence category, pooled across Shapley\-Scarf and Matching Markets\.
Scaling\.We begin with a baseline setting in which preferences are given as complete strict linear orders, ensuring that standard solution concepts are guaranteed to exist\. We consider a range of canonical objectives, including Pareto optimality, core outcomes, and stability, as well as social welfare criteria such as egalitarian, utilitarian, and rank\-maximal solutions\.444See[SectionE\.1](https://arxiv.org/html/2608.18631#A5.SS1), for detailed formalism of each solution concept and[AppendixI](https://arxiv.org/html/2608.18631#A9)\([Figure9](https://arxiv.org/html/2608.18631#A9.F9)\) for performance on each\.\. As shown in[Figure4\(a\)](https://arxiv.org/html/2608.18631#S4.F4.sf1), model performance degrades rapidly as market size increases, even in moderately sized instances\. This decline is consistent across solution concepts, indicating limited scalability of LLMs in multi\-step algorithmic reasoning tasks\. While performance is comparatively stronger for concepts with well\-structured canonical algorithms, the overall trend aligns with prior findings on the limitations of LLM reasoning in complex settings\[[70](https://arxiv.org/html/2608.18631#bib.bib58),[31](https://arxiv.org/html/2608.18631#bib.bib14)\]\. In[AppendixI](https://arxiv.org/html/2608.18631#A9), we demonstrate that models default to canonical algorithms for the domain when the solution concept is unspecified \([SectionI\.3](https://arxiv.org/html/2608.18631#A9.SS3)\), and display similar behavior when tasked with computing weaker solution concepts \([SectionI\.2](https://arxiv.org/html/2608.18631#A9.SS2)\)\.

Deciding Infeasibility\.We consider two market settings, namely Shapley\-Scarf and two\-sided matching markets, in which the presence of ties in preferences gives rise to richer, but more demanding, solution concepts\. In particular, stronger refinements such as the strict core \(in contrast to the weak core\) in house allocation, and super stability and strong stability \(in contrast to weak stability\) in matching markets, impose stringent constraints that may render instances infeasible\. This lack of guaranteed existence is not incidental, but arises from the interaction between ties in preferences and the robustness requirements encoded by these solution concepts\. Consequently, these markets provide a natural testbed for evaluating whether models can both construct valid solutions when they exist and correctly identify infeasibility when no such solutions are admissible\.

[Figure4\(b\)](https://arxiv.org/html/2608.18631#S4.F4.sf2)provides an overview of model performance across the two domains\. As shown, all models exhibit declining performance both in correctly identifying infeasible instances, where no solution exists, and in generating valid outputs when the corresponding solution concepts are feasible\. In small markets \(n=10n=10\), GPT\-5\.2 performs well in identifying infeasible instances, likely due to its ability to rely on heuristics and near\-exhaustive search \(see[AppendixL](https://arxiv.org/html/2608.18631#A12)for details\)\. However, even at modest scales \(e\.g\.,n=30n=30\), its performance deteriorates to the level of other models, as such approaches are no longer computationally feasible\.

Indeterminacy Option\.Given that certain instances may not admit a solution under specific concepts \(e\.g\., super stability or the strict core\), we further examine whether LLMs can correctly reason about such infeasibility when explicitly provided with an abstention option \(i\.e\., declaring non\-existence or returning a null solution\)\.

[Figure5](https://arxiv.org/html/2608.18631#S4.F5)\(a\) summarizes model accuracy across three solution concepts in both markets, disaggregated by feasible and infeasible instances\. While the indeterminacy option improves accuracy in detecting infeasible instances, it introduces a systematic bias toward over\-declaring non\-existence, even when solutions exist\. Consequently, performance on feasible instances deteriorates, as models increasingly abstain rather than produce valid solutions\.[AppendixL](https://arxiv.org/html/2608.18631#A12)provides an in\-depth analysis of the heuristic strategies underlying these behaviors\.

Figure 5:Errors made by models on generation \(a\) and selection \(b\) tasks as a function of problem feasibility and availability of an indeterminacy option, averaged over different solution concepts \(Modest instance size\)\. An ideal model would cluster near the origin in all four quadrants\.
### 4\.2Verification: Selection from a Menu of Options

Thus far, we observe that language models struggle to correctly reason about solution concepts, both in generating feasible outcomes and in identifying infeasibility, even when explicitly provided with an abstention option\. This raises the question of whether these failures stem from limitations in algorithmic reasoning \(i\.e\., executing the underlying steps\) or from more fundamental deficiencies in feasibility reasoning\. To disentangle these effects, we follow prior work \(e\.g\.,\[[32](https://arxiv.org/html/2608.18631#bib.bib15)\]\) in distinguishing between generation and selection tasks\. Selection tasks are strictly easier, as they require onlyverificationof candidate solutions rather than the synthesis of a solution via multi\-step procedures\.

We consider the same market settings with weak preferences\. For each instance, the model is presented with a set of pre\-computed candidate solutions \(five in general, and four for smaller instances\) and is required to select a valid one\. Instances are generated via rejection sampling \([SectionF\.2](https://arxiv.org/html/2608.18631#A6.SS2)\), and candidate solutions are constructed so that each satisfies a distinct solution concept, with no overlap across options\. In certain variants, a “none of the above” \(NOTA\) option is included to permit abstention; in others, it is omitted to enforce selection\.

[Figure5](https://arxiv.org/html/2608.18631#S4.F5)\(b\) shows that models frequently select incorrect candidates even when a valid solution is present\.555Note that, in the selection case, nearly all incorrect responses select the “weaker version” of the intended notion, i\.e\. weak core instead of strict, weak stability instead of strong, and strong stability instead of super \(see[SectionI\.4](https://arxiv.org/html/2608.18631#A9.SS4)for more details\)\.For infeasible instances, the removal of the NOTA option significantly increases the likelihood with which they select an incorrect option instead of indicating that no option applies\. The effect is one\-sided, i\.e\. when NOTA is available, no model selects it on feasible instances, and models under\-select it on infeasible ones\. Moreover, while GPT\-5\.2 substantially outperforms other models when a valid solution is present, its performance degrades markedly on infeasible instances, particularly as problem size increases or when the NOTA option is absent\.

Intention\-Action Misalignment\.Given these failures in selection tasks, a key question is what objective LLMs are implicitly optimizing when selecting among candidate solutions\. To investigate this, we construct instances across different preference types—strict complete, complete with ties, and incomplete with ties—in each domain, such that the candidate options each satisfy distinct \(and, in many cases, non\-overlapping\) solution concepts\. Our objective is to characterize the implicit criteria guiding model behavior and to assess whether these criteria are consistently realized in the selected outcomes\.

[Figure14](https://arxiv.org/html/2608.18631#A9.F14)\([SectionI\.5](https://arxiv.org/html/2608.18631#A9.SS5)\) shows the fraction of responses in which models select solutions satisfying various properties\. To ensure comprehensive coverage, the candidate set includes outcomes aligned with standard welfarist criteria, such as utilitarian and egalitarian objectives\. We further infer model intentions using LLM\-based judges, enabling a comparison between the property a model appears to target and the property actually satisfied by its selected solution\.666We analyze reasoning traces to identify the “intended” concepts using LLM\-as\-a\-judge\. See[AppendixP](https://arxiv.org/html/2608.18631#A16)for details of the setup and validation of the judges\.This analysis reveals a systematic intention\-action misalignment: models frequently imply adherence to a particular solution concept, yet select outcomes that violate the very criteria they appear to optimize\. This intention\-action gap is especially pronounced in settings with ties or incomplete preferences, where structural constraints may render certain solution concepts infeasible\.

## 5Performance Improvements with Assisted Reasoning

We consider assisted reasoning under two settings: \(i\) refinement via feedback and \(ii\) reasoning with code execution, to examine whether the models recover their performance gap on indeterminacy\. Both are presented below\. In[AppendixM](https://arxiv.org/html/2608.18631#A13), we demonstrate how prompt\-level mitigation such as providing few\-shot examples or explicit instructions to not make assumption \(both general and problem specific\), fail to reliably calibrate the models\.

Refinements with Feedback\.

Figure 6:The effect of allowing models to refine their solutions using feedback\. Each bar shows the fraction of instances that were ultimately answered correctly or incorrectly after up to three attempts with verification feedback\.[Section4\.1](https://arxiv.org/html/2608.18631#S4.SS1)showed that models struggle to compute solutions on potentially infeasible instances in a one\-shot prompting setup\. Although these are reasoning models with internal chain\-of\-thought, it is unclear whether their failures stem from being unable to recognize that a candidate solution is incorrect, or from being able to recognize the error but unable to repair it \(because the complexity of the task inhibits them from verifying and then trying again\)\. To distinguish the two, we evaluate OSS\-120B and GPT\-5\.2 in a multi\-round setup, where after each response we return structured feedback identifying the violation \(a blocking pair in matching markets, a blocking coalition in Shapley\-Scarf markets\) and allow the model up to two retries \(see[AppendixO](https://arxiv.org/html/2608.18631#A15)for more details\)\. For each model we use the smallest instance size at which it begins to fail in the one\-shot setting: Small for OSS\-120B and Modest for GPT\-5\.2\.

[Figure6](https://arxiv.org/html/2608.18631#S5.F6)shows that feedback improves performance substantially on Shapley\-Scarf markets but barely at all on matching markets\. The asymmetry follows from what the models produce in the first round\. On Shapley\-Scarf instances they typically generate a valid \(though incorrect\) allocation, which the feedback then correctly redirects in many cases\. On matching instances, both models are biased toward declaring infeasibility from the first round, and once a model has returned no solution there is nothing for the feedback mechanism to act on\. Refinement is therefore effective only when the model produces a candidate solution to begin with; when its dominant failure mode is over\-abstention, additional rounds do not change the outcome\.

Reasoning with Code Execution\.In the previous sections we observed how LLMs fail to recognize when questions are undetermined, and are miscalibrated in identifying when a given solution concept is achievable for a given input\. To understand whether these limitations are present only when LLMs reason in\-context, we evaluate their performance when allowed to write code to solve the same problems, given their impressive ability to write code\[[44](https://arxiv.org/html/2608.18631#bib.bib70),[41](https://arxiv.org/html/2608.18631#bib.bib34)\]\.

For preference reasoning, solving determined questions with code execution completely eliminates errors related to scale\. However, on undetermined queries such as \(RS\-incomparable\) bundle comparisons and the ranking task, the answers arealwaysincorrect\. The assumptions models make now become part of the implemented algorithmic steps\. The contrast with the structural setting is informative\. There, models often write an explicit feasibility check and return no solution when the search finds none \([AppendixL](https://arxiv.org/html/2608.18631#A12)\), but on undetermined preference queries they write no such check\.

For algorithmic reasoning, allowing LLMs to write code to solve both feasible and infeasible problems significantly improves their performance, although not by implementing the “correct” approach \(see[Table29](https://arxiv.org/html/2608.18631#A14.T29)in[AppendixN](https://arxiv.org/html/2608.18631#A14)for exact accuracy levels\)\. In fact, their approach changes with the input size\. For Small instances, the models resort to brute\-force enumeration of all solutions\. The strategy changes for Modest and for Medium instances, where they could use slightly more efficient heuristics to solve the problem \(See[AppendixN](https://arxiv.org/html/2608.18631#A14)for detailed descriptions of the approaches used\)\.

However, as becomes clear with Medium instances, these approaches are not scalable\. For Shapley\-Scarf Markets, the models perform well on feasible instances, but often time\-out on infeasible ones777We set a limit of 20 minutes after which \(if the model doesn’t return a response\) the response is treated as timed\-out\.\. Similarly, the strategy used for Matching Markets misidentifies feasible instances as infeasible, in the few responses that do not time\-out\. Hence, while code improves performance on smaller markets, it does not enable models to recognize and use approaches relevant for deployment\-level sizes\.

Dissociating the two axes\.The two forms of indeterminacy respond to different interventions, which is what separates them from a single shared calibration failure\. Code execution improves structural reasoning but not epistemic queries, where the model compiles its assumption into the program it writes\. Prompt\-level intervention does the reverse\. It raises indeterminacy detection on preference queries \([Figure2](https://arxiv.org/html/2608.18631#S3.F2)\(b\)\) but does not improve feasibility reasoning due to structural \(in\)determinacy\. This suggest that the escape hatch instead moves the error into over\-abstention \([Figure5](https://arxiv.org/html/2608.18631#S4.F5)\(a\)\)\.

## 6Concluding Remarks

We argue that indeterminacy is a fundamental dimension of reasoning in preference\-based AI systems\. As language models increasingly mediate alignment, coordination, and collective decisions, current closed\-world training paradigms systematically bias models toward hallucinating determinacy, feasibility, and preference information where none is entailed—a broader manifestation ofverisimilitudein AI, where outputs appear plausible despite lacking logical grounding\. Our results suggest that robust AI will require open\-world reasoning frameworks \(e\.g\. multi\-valued semantics\), richer notions of non\-entailment and impossibility, and benchmarks that evaluate not only correctness, but the ability to recognize when no justified answer exists\.

## Acknowledgments

This research was supported in part by NSF Awards IIS\-2144413 and IIS\-2107173\. We also thank the anonymous reviewers for their careful reading and constructive feedback, which improved the paper\.

## References

- \[1\]Y\. Abbasi\-Yadkori, I\. Kuzborskij, A\. György, and C\. Szepesvari\(2024\)To believe or not to believe your LLM: iterative prompting for estimating epistemic uncertainty\.InThe Thirty\-eighth Annual Conference on Neural Information Processing Systems,External Links:[Link](https://openreview.net/forum?id=k6iyUfwdI9)Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p6.1),[§1\.2](https://arxiv.org/html/2608.18631#S1.SS2.p1.1),[§2\.2](https://arxiv.org/html/2608.18631#S2.SS2.p6.1)\.
- \[2\]A\. Abdulkadiroğlu and T\. Sönmez\(1999\)House allocation with existing tenants\.Journal of Economic Theory88\(2\),pp\. 233–260\.Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p3.1)\.
- \[3\]S\. Agarwal, L\. Ahmad, J\. Ai, S\. Altman, A\. Applebaum, E\. Arbus, R\. K\. Arora, Y\. Bai, B\. Baker, H\. Bao,et al\.\(2025\)Gpt\-oss\-120b & gpt\-oss\-20b model card\.arXiv preprint arXiv:2508\.10925\.Cited by:[§2\.2](https://arxiv.org/html/2608.18631#S2.SS2.p7.1)\.
- \[4\]G\. Amanatidis, G\. Birmpas, A\. Filos\-Ratsikas, and A\. A\. Voudouris\(2022\)Fair division of indivisible goods: A survey\.InProceedings of the Thirty\-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23\-29 July 2022,L\. D\. Raedt \(Ed\.\),pp\. 5385–5393\.External Links:[Link](https://doi.org/10.24963/ijcai.2022/756),[Document](https://dx.doi.org/10.24963/IJCAI.2022/756)Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p3.1),[§1\.2](https://arxiv.org/html/2608.18631#S1.SS2.p3.1)\.
- \[5\]E\. Ameisen, J\. Lindsey, A\. Pearce, W\. Gurnee, N\. L\. Turner, B\. Chen, C\. Citro, D\. Abrahams, S\. Carter, B\. Hosmer, J\. Marcus, M\. Sklar, A\. Templeton, T\. Bricken, C\. McDougall, H\. Cunningham, T\. Henighan, A\. Jermyn, A\. Jones, A\. Persic, Z\. Qi, T\. Ben Thompson, S\. Zimmerman, K\. Rivoire, T\. Conerly, C\. Olah, and J\. Batson\(2025\)Circuit tracing: revealing computational graphs in language models\.Transformer Circuits Thread\.External Links:[Link](https://transformer-circuits.pub/2025/attribution-graphs/methods.html)Cited by:[Appendix B](https://arxiv.org/html/2608.18631#A2.p2.1)\.
- \[6\]Anthropic\(2025\)Introducing claude sonnet 4\.5\.External Links:[Link](https://www.anthropic.com/news/claude-sonnet-4-5)Cited by:[§2\.2](https://arxiv.org/html/2608.18631#S2.SS2.p7.1)\.
- \[7\]D\. E\. Austin, A\. Korikov, A\. Toroghi, and S\. Sanner\(2024\)Bayesian optimization with llm\-based acquisition functions for natural language preference elicitation\.InProceedings of the 18th ACM Conference on Recommender Systems, RecSys 2024, Bari, Italy, October 14\-18, 2024,T\. D\. Noia, P\. Lops, T\. Joachims, K\. Verbert, P\. Castells, Z\. Dong, and B\. London \(Eds\.\),pp\. 74–83\.External Links:[Link](https://doi.org/10.1145/3640457.3688142),[Document](https://dx.doi.org/10.1145/3640457.3688142)Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p5.1)\.
- \[8\]H\. Aziz, P\. Biró, and M\. Yokoo\(2022\)Matching market design with constraints\.Proceedings of the AAAI Conference on Artificial Intelligence36\(11\),pp\. 12308–12316\.External Links:[Link](https://ojs.aaai.org/index.php/AAAI/article/view/21495),[Document](https://dx.doi.org/10.1609/aaai.v36i11.21495)Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p3.1)\.
- \[9\]H\. Aziz, I\. Caragiannis, A\. Igarashi, and T\. Walsh\(2022\)Fair allocation of indivisible goods and chores\.Auton\. Agents Multi Agent Syst\.36\(1\),pp\. 3\.External Links:[Link](https://doi.org/10.1007/s10458-021-09532-8),[Document](https://dx.doi.org/10.1007/S10458-021-09532-8)Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p3.1)\.
- \[10\]H\. Aziz, X\. Huang, N\. Mattei, and E\. Segal\-Halevi\(2023\)Computing welfare\-maximizing fair allocations of indivisible goods\.European Journal of Operational Research307\(2\),pp\. 773–784\.External Links:ISSN 0377\-2217,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/j.ejor.2022.10.013),[Link](https://www.sciencedirect.com/science/article/pii/S0377221722007822)Cited by:[§E\.1](https://arxiv.org/html/2608.18631#A5.SS1.p6.2)\.
- \[11\]H\. Aziz, I\. Iliffe, B\. Li, A\. Ritossa, A\. Sun, and M\. Suzuki\(2024\)Envy\-free house allocation under uncertain preferences\.Proceedings of the AAAI Conference on Artificial Intelligence38\(9\),pp\. 9477–9484\.External Links:[Link](https://ojs.aaai.org/index.php/AAAI/article/view/28802),[Document](https://dx.doi.org/10.1609/aaai.v38i9.28802)Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p3.1)\.
- \[12\]S\. Bhattacharyya, S\. Khanna, L\. Chen, L\. Craig, T\. Dilliraj, and J\. Z\. Wang\(2026\)Beyond confidence: rethinking self\-assessments for performance prediction in llms\.External Links:2605\.07806,[Link](https://arxiv.org/abs/2605.07806)Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p6.1)\.
- \[13\]D\. Blacket al\.\(1958\)The theory of committees and elections\.Springer\.Cited by:[§4](https://arxiv.org/html/2608.18631#S4.p2.1)\.
- \[14\]G\. Brightwell\(1993\)Models of random partial orders\.Surveys in combinatorics5383\.Cited by:[§F\.1\.1](https://arxiv.org/html/2608.18631#A6.SS1.SSS1.p4.1)\.
- \[15\]O\. Çelebi and J\. P\. Flynn\(2022\)Priority design in centralized matching markets\.The Review of Economic Studies89\(3\),pp\. 1245–1277\.External Links:ISSN 0034\-6527,[Document](https://dx.doi.org/10.1093/restud/rdab053),[Link](https://doi.org/10.1093/restud/rdab053),https://academic\.oup\.com/restud/article\-pdf/89/3/1245/43615945/rdab053\_supplementary\_data\.pdfCited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p3.1)\.
- \[16\]J\. Chen, Y\. Luo, and L\. Pan\(2026\)Mechanistic data attribution: tracing the training origins of interpretable LLM units\.CoRRabs/2601\.21996\.External Links:[Link](https://doi.org/10.48550/arXiv.2601.21996),[Document](https://dx.doi.org/10.48550/ARXIV.2601.21996),2601\.21996Cited by:[Appendix B](https://arxiv.org/html/2608.18631#A2.p4.1)\.
- \[17\]S\. K\. Choe, H\. Ahn, J\. Bae, K\. Zhao, Y\. Chung, A\. Pratapa, W\. Neiswanger, E\. Strubell, T\. Mitamura, J\. Schneider, E\. Hovy, R\. B\. Grosse, and E\. P\. Xing\(2026\)What is your data worth to GPT? LLM\-scale data valuation with influence functions\.InThe Thirty\-ninth Annual Conference on Neural Information Processing Systems,External Links:[Link](https://openreview.net/forum?id=zPKeJAEo27)Cited by:[Appendix B](https://arxiv.org/html/2608.18631#A2.p4.1)\.
- \[18\]K\. Cobbe, V\. Kosaraju, M\. Bavarian, M\. Chen, H\. Jun, L\. Kaiser, M\. Plappert, J\. Tworek, J\. Hilton, R\. Nakano, C\. Hesse, and J\. Schulman\(2021\)Training verifiers to solve math word problems\.CoRRabs/2110\.14168\.External Links:[Link](https://arxiv.org/abs/2110.14168),2110\.14168Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p1.1)\.
- \[19\]V\. Conitzer, R\. Freedman, J\. Heitzig, W\. H\. Holliday, B\. M\. Jacobs, N\. Lambert, M\. Mossé, E\. Pacuit, S\. Russell, H\. Schoelkopf,et al\.\(2024\)Social choice should guide AI alignment in dealing with diverse human feedback\.arXiv preprint arXiv:2404\.10271\.Cited by:[§1](https://arxiv.org/html/2608.18631#S1.p2.1)\.
- \[20\]B\. Cookson, S\. Ebadian, and N\. Shah\(2026\)Fairness perceptions of large language models\.InFortieth AAAI Conference on Artificial Intelligence, Thirty\-Eighth Conference on Innovative Applications of Artificial Intelligence, Sixteenth Symposium on Educational Advances in Artificial Intelligence, AAAI 2026, Singapore, January 20\-27, 2026,S\. Koenig, C\. Jenkins, and M\. E\. Taylor \(Eds\.\),pp\. 35393–35401\.External Links:[Link](https://doi.org/10.1609/aaai.v40i42.40848),[Document](https://dx.doi.org/10.1609/AAAI.V40I42.40848)Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p4.1),[§I\.5](https://arxiv.org/html/2608.18631#A9.SS5.SSS0.Px1.p1.1),[§1\.2](https://arxiv.org/html/2608.18631#S1.SS2.p3.1)\.
- \[21\]G\. Deepmind\(2025\)Gemini pro\.External Links:[Link](https://deepmind.google/technologies/gemini/pro/)Cited by:[§2\.2](https://arxiv.org/html/2608.18631#S2.SS2.p7.1)\.
- \[22\]J\. P\. Dickerson, H\. Hosseini, S\. Khanna, and L\. Pierce\(2026\)Who gets the kidney? human\-ai alignment, indecision, and moral values\.InProceedings of the 2026 ACM Conference on Fairness, Accountability, and Transparency,FAccT ’26,New York, NY, USA,pp\. 8128–8147\.External Links:ISBN 9798400725968,[Link](https://doi.org/10.1145/3805689.3806437),[Document](https://dx.doi.org/10.1145/3805689.3806437)Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p6.1)\.
- \[23\]F\. Echenique, N\. Immorlica, V\.V\. Vazirani, and A\.E\. Roth\(2023\)Online and matching\-based market design\.Cambridge University Press\.External Links:ISBN 9781108831994,[Link](https://books.google.com/books?id=1ea-EAAAQBAJ)Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p3.1),[§1\.2](https://arxiv.org/html/2608.18631#S1.SS2.p3.1)\.
- \[24\]Ö\. Eğecioğlu and A\. E\. Giritligil\(2013\)The impartial, anonymous, and neutral culture model: a probability model for sampling public preference structures\.The Journal of Mathematical Sociology37\(4\),pp\. 203–222\.Cited by:[§4](https://arxiv.org/html/2608.18631#S4.p2.1)\.
- \[25\]P\. Erdős and A\. Rényi\(1959\)On random graphs i\.Publ\. math\. debrecen6\(290\-297\),pp\. 18\.Cited by:[§F\.1\.1](https://arxiv.org/html/2608.18631#A6.SS1.SSS1.p4.1)\.
- \[26\]S\. Fish, P\. Gölz, D\. Parkes, A\. Procaccia, G\. Rusak, I\. Shapira, and M\. Wuthrich\(2023\)Generative social choice\.Journal of the ACM\.Cited by:[§1](https://arxiv.org/html/2608.18631#S1.p2.1)\.
- \[27\]S\. Fish, J\. Shephard, M\. Li, R\. I\. Shorrer, and Y\. A\. Gonczarowski\(2025\)EconEvals: benchmarks and litmus tests for economic decision\-making by llm agents\.arXiv preprint arXiv:2503\.18825\.Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p4.1),[§1\.2](https://arxiv.org/html/2608.18631#S1.SS2.p3.1)\.
- \[28\]D\. Gale and L\. S\. Shapley\(1962\)College admissions and the stability of marriage\.The American Mathematical Monthly69\(1\),pp\. 9–15\.Cited by:[3rd item](https://arxiv.org/html/2608.18631#A5.I3.i3.p1.1),[§E\.1](https://arxiv.org/html/2608.18631#A5.SS1.p8.1),[§2\.1](https://arxiv.org/html/2608.18631#S2.SS1.p1.1)\.
- \[29\]K\. Handa, Y\. Gal, E\. Pavlick, N\. D\. Goodman, J\. Andreas, A\. Tamkin, and B\. Z\. Li\(2024\)Bayesian preference elicitation with language models\.CoRRabs/2403\.05534\.External Links:[Link](https://doi.org/10.48550/arXiv.2403.05534),[Document](https://dx.doi.org/10.48550/ARXIV.2403.05534),2403\.05534Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p5.1),[§1\.2](https://arxiv.org/html/2608.18631#S1.SS2.p3.1)\.
- \[30\]D\. Hendrycks, C\. Burns, S\. Kadavath, A\. Arora, S\. Basart, E\. Tang, D\. Song, and J\. Steinhardt\(2021\)Measuring mathematical problem solving with the MATH dataset\.InProceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks 1, NeurIPS Datasets and Benchmarks 2021, December 2021, virtual,J\. Vanschoren and S\. Yeung \(Eds\.\),External Links:[Link](https://datasets-benchmarks-proceedings.neurips.cc/paper/2021/hash/be83ab3ecd0db773eb2dc1b0a17836a1-Abstract-round2.html)Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p1.1)\.
- \[31\]H\. Hosseini, S\. Khanna, and R\. Singh\(2025\)Matching markets meet LLMs: algorithmic reasoning with ranked preferences\.InThe Thirty\-ninth Annual Conference on Neural Information Processing Systems,External Links:[Link](https://openreview.net/forum?id=1zKElu2MuQ)Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p1.1),[Appendix D](https://arxiv.org/html/2608.18631#A4.p4.1),[§1\.2](https://arxiv.org/html/2608.18631#S1.SS2.p1.1),[§1\.2](https://arxiv.org/html/2608.18631#S1.SS2.p3.1),[§4\.1](https://arxiv.org/html/2608.18631#S4.SS1.p1.1)\.
- \[32\]H\. Hosseini and S\. Khanna\(2025\)Distributive fairness in large language models: evaluating alignment with human values\.InThe Thirty\-ninth Annual Conference on Neural Information Processing Systems,External Links:[Link](https://openreview.net/forum?id=5pQFE4yIZ5)Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p4.1),[§I\.5](https://arxiv.org/html/2608.18631#A9.SS5.SSS0.Px1.p1.1),[§1\.2](https://arxiv.org/html/2608.18631#S1.SS2.p3.1),[§4\.2](https://arxiv.org/html/2608.18631#S4.SS2.p1.1)\.
- \[33\]H\. Hosseini, M\. Kumar, and S\. Roy\(2024\)The degree of fairness in efficient house allocation\.InECAI 2024 \- 27th European Conference on Artificial Intelligence, 19\-24 October 2024, Santiago de Compostela, Spain \- Including 13th Conference on Prestigious Applications of Intelligent Systems \(PAIS 2024\),U\. Endriss, F\. S\. Melo, K\. Bach, A\. J\. B\. Diz, J\. M\. Alonso\-Moral, S\. Barro, and F\. Heintz \(Eds\.\),Frontiers in Artificial Intelligence and Applications,pp\. 3636–3643\.External Links:[Link](https://doi.org/10.3233/FAIA240920),[Document](https://dx.doi.org/10.3233/FAIA240920)Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p3.1)\.
- \[34\]H\. Hosseini, S\. Roy, and A\. Sethia\(2026\)Fair societies: algorithms for house allocations\.Proceedings of the AAAI Conference on Artificial Intelligence40\(20\),pp\. 17050–17058\.External Links:[Link](https://ojs.aaai.org/index.php/AAAI/article/view/38753),[Document](https://dx.doi.org/10.1609/aaai.v40i20.38753)Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p3.1)\.
- \[35\]W\. Hua, O\. Liu, L\. Li, A\. Amayuelas, J\. Chen, L\. Jiang, M\. Jin, L\. Fan, F\. Sun, W\. Wang, X\. Wang, and Y\. Zhang\(2024\)Game\-theoretic LLM: agent workflow for negotiation games\.CoRRabs/2411\.05990\.External Links:[Link](https://doi.org/10.48550/arXiv.2411.05990),[Document](https://dx.doi.org/10.48550/ARXIV.2411.05990),2411\.05990Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p2.1)\.
- \[36\]D\. Huang, F\. J\. M\. Cossío, E\. Lock, and D\. C\. Parkes\(2025\)Accelerated preference elicitation with llm\-based proxies\.CoRRabs/2501\.14625\.External Links:[Link](https://doi.org/10.48550/arXiv.2501.14625),[Document](https://dx.doi.org/10.48550/ARXIV.2501.14625),2501\.14625Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p5.1),[§1\.2](https://arxiv.org/html/2608.18631#S1.SS2.p3.1)\.
- \[37\]T\. Huynh, D\. Dao\-Sy, T\. Cao, P\. Le, H\. Nguyen, P\. Nguyen\-Lam, M\. Nguyen\-Vo, H\. Pham, P\. Pham, T\. Than, C\. Tran, H\. Tran, G\. Tran\-Le, A\. Buscemi, L\. H\. Trang, and T\. A\. Han\(2025\)Understanding LLM agent behaviours via game theory: strategy recognition, biases and multi\-agent dynamics\.CoRRabs/2512\.07462\.External Links:[Link](https://doi.org/10.48550/arXiv.2512.07462),[Document](https://dx.doi.org/10.48550/ARXIV.2512.07462),2512\.07462Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p2.1),[§1\.2](https://arxiv.org/html/2608.18631#S1.SS2.p3.1)\.
- \[38\]A\. Igarashi, M\. Lackner, O\. Nardi, and A\. Novaro\(2024\)Repeated fair allocation of indivisible items\.Proceedings of the AAAI Conference on Artificial Intelligence38\(9\),pp\. 9781–9789\.External Links:[Link](https://ojs.aaai.org/index.php/AAAI/article/view/28837),[Document](https://dx.doi.org/10.1609/aaai.v38i9.28837)Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p3.1)\.
- \[39\]R\. W\. Irving, T\. Kavitha, K\. Mehlhorn, D\. Michail, and K\. E\. Paluch\(2006\)Rank\-maximal matchings\.ACM Trans\. Algorithms2\(4\),pp\. 602–610\.External Links:ISSN 1549\-6325,[Link](https://doi.org/10.1145/1198513.1198520),[Document](https://dx.doi.org/10.1145/1198513.1198520)Cited by:[§E\.1](https://arxiv.org/html/2608.18631#A5.SS1.p7.1)\.
- \[40\]R\. W\. Irving\(1994\)Stable marriage and indifference\.Discrete Applied Mathematics48\(3\),pp\. 261–272\.External Links:ISSN 0166\-218X,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/0166-218X%2892%2900179-P),[Link](https://www.sciencedirect.com/science/article/pii/0166218X9200179P)Cited by:[2nd item](https://arxiv.org/html/2608.18631#A5.I2.i2.p1.1),[3rd item](https://arxiv.org/html/2608.18631#A5.I2.i3.p1.1)\.
- \[41\]N\. Jain, K\. Han, A\. Gu, W\. Li, F\. Yan, T\. Zhang, S\. Wang, A\. Solar\-Lezama, K\. Sen, and I\. Stoica\(2024\)Livecodebench: holistic and contamination free evaluation of large language models for code\.arXiv preprint arXiv:2403\.07974\.Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p1.1),[§5](https://arxiv.org/html/2608.18631#S5.p5.1)\.
- \[42\]M\. Jang, S\. Kim, C\. Suh, and S\. Oh\(2016\)Top\-k ranking from pairwise comparisons: when spectral ranking is optimal\.CoRRabs/1603\.04153\.External Links:[Link](http://arxiv.org/abs/1603.04153),1603\.04153Cited by:[§F\.1\.1](https://arxiv.org/html/2608.18631#A6.SS1.SSS1.p4.1)\.
- \[43\]J\. Jia, Z\. Yuan, J\. Pan, P\. McNamara, and D\. Chen\(2025\)Large language model strategic reasoning evaluation through behavioral game theory\.CoRRabs/2502\.20432\.External Links:[Link](https://doi.org/10.48550/arXiv.2502.20432),[Document](https://dx.doi.org/10.48550/ARXIV.2502.20432),2502\.20432Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p2.1),[§1\.2](https://arxiv.org/html/2608.18631#S1.SS2.p3.1)\.
- \[44\]C\. E\. Jimenez, J\. Yang, A\. Wettig, S\. Yao, K\. Pei, O\. Press, and K\. R\. Narasimhan\(2024\)SWE\-bench: can language models resolve real\-world github issues?\.InThe Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7\-11, 2024,External Links:[Link](https://openreview.net/forum?id=VTF8yNQM66)Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p1.1),[§2\.2](https://arxiv.org/html/2608.18631#S2.SS2.p7.1),[§5](https://arxiv.org/html/2608.18631#S5.p5.1)\.
- \[45\]S\. Kadavath, T\. Conerly, A\. Askell, T\. Henighan, D\. Drain, E\. Perez, N\. Schiefer, Z\. Hatfield\-Dodds, N\. DasSarma, E\. Tran\-Johnson,et al\.\(2022\)Language models \(mostly\) know what they know\.arXiv preprint arXiv:2207\.05221\.Cited by:[Appendix B](https://arxiv.org/html/2608.18631#A2.p4.1)\.
- \[46\]S\. Kapoor, N\. Gruver, M\. Roberts, K\. M\. Collins, A\. Pal, U\. Bhatt, A\. Weller, S\. Dooley, M\. Goldblum, and A\. G\. Wilson\(2024\)Large language models must be taught to know what they don’t know\.InThe Thirty\-eighth Annual Conference on Neural Information Processing Systems,External Links:[Link](https://openreview.net/forum?id=QzvWyggrYB)Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p6.1),[§1\.2](https://arxiv.org/html/2608.18631#S1.SS2.p1.1)\.
- \[47\]P\. Kirichenko, M\. Ibrahim, K\. Chaudhuri, and S\. Bell\(2025\)AbstentionBench: reasoning LLMs fail on unanswerable questions\.InThe Thirty\-ninth Annual Conference on Neural Information Processing Systems Datasets and Benchmarks Track,External Links:[Link](https://openreview.net/forum?id=OkHC30LLpO)Cited by:[Appendix B](https://arxiv.org/html/2608.18631#A2.p3.1),[Appendix D](https://arxiv.org/html/2608.18631#A4.p6.1),[§1\.2](https://arxiv.org/html/2608.18631#S1.SS2.p1.1)\.
- \[48\]S\. Kleene\(1952\)Introduction to metamathematics\.North\-Holland\.Cited by:[§1](https://arxiv.org/html/2608.18631#S1.p4.1)\.
- \[49\]T\. Knipe and J\. Ortega\(2025\)Improvable students in school choice\.QBS Working PaperTechnical Report2025/03,Queen’s University Belfast, Queen’s Business School,Belfast\(eng\)\.External Links:[Link](https://hdl.handle.net/10419/315576)Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p3.1)\.
- \[50\]B\. Z\. Li, A\. Tamkin, N\. D\. Goodman, and J\. Andreas\(2025\)Eliciting human preferences with language models\.InThe Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24\-28, 2025,External Links:[Link](https://openreview.net/forum?id=LvDwwAgMEW)Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p5.1),[§1\.2](https://arxiv.org/html/2608.18631#S1.SS2.p3.1)\.
- \[51\]J\. Lindsey, W\. Gurnee, E\. Ameisen, B\. Chen, A\. Pearce, N\. L\. Turner, C\. Citro, D\. Abrahams, S\. Carter, B\. Hosmer, J\. Marcus, M\. Sklar, A\. Templeton, T\. Bricken, C\. McDougall, H\. Cunningham, T\. Henighan, A\. Jermyn, A\. Jones, A\. Persic, Z\. Qi, T\. B\. Thompson, S\. Zimmerman, K\. Rivoire, T\. Conerly, C\. Olah, and J\. Batson\(2025\)On the biology of a large language model\.Transformer Circuits Thread\.External Links:[Link](https://transformer-circuits.pub/2025/attribution-graphs/biology.html)Cited by:[Appendix B](https://arxiv.org/html/2608.18631#A2.p2.1)\.
- \[52\]S\. Liu, X\. Lu, M\. Suzuki, and T\. Walsh\(2024\)Mixed fair division: A survey\.J\. Artif\. Intell\. Res\.80,pp\. 1373–1406\.External Links:[Link](https://doi.org/10.1613/jair.1.15800),[Document](https://dx.doi.org/10.1613/JAIR.1.15800)Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p3.1)\.
- \[53\]X\. Long and R\. A\. Velez\(2021\)Balanced house allocation\.arXiv preprint arXiv:2109\.01992\.Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p3.1),[§1\.2](https://arxiv.org/html/2608.18631#S1.SS2.p3.1)\.
- \[54\]J\. Ma\(1994\)Strategy\-proofness and the strict core in a market with indivisibilities\.Int\. J\. Game Theory23\(1\),pp\. 75–83\.External Links:ISSN 0020\-7276,[Link](https://doi.org/10.1007/BF01242849),[Document](https://dx.doi.org/10.1007/BF01242849)Cited by:[1st item](https://arxiv.org/html/2608.18631#A5.I3.i1.p1.1)\.
- \[55\]A\. Montazeralghaem, G\. Tennenholtz, C\. Boutilier, and O\. Meshi\(2025\)Asking clarifying questions for preference elicitation with large language models\.CoRRabs/2510\.12015\.External Links:[Link](https://doi.org/10.48550/arXiv.2510.12015),[Document](https://dx.doi.org/10.48550/ARXIV.2510.12015),2510\.12015Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p5.1)\.
- \[56\]N\. Nisan, T\. Roughgarden, E\. Tardos, and V\. V\. Vazirani\(2007\)Algorithmic game theory\.Cambridge University Press\.Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p2.1)\.
- \[57\]L\. Phan, A\. Gatti, Z\. Han, N\. Li, J\. Hu, H\. Zhang, C\. B\. C\. Zhang, M\. Shaaban, J\. Ling, S\. Shi,et al\.\(2025\)Humanity’s last exam\.arXiv preprint arXiv:2501\.14249\.Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p1.1)\.
- \[58\]C\. Qian, K\. Zhu, J\. J\. Horton, B\. S\. Manning, V\. Tsai, J\. Wexler, and N\. Thain\(2026\)Strategic tradeoffs between humans and AI in multi\-agent bargaining\.InProceedings of the 31st International Conference on Intelligent User Interfaces, IUI 2026, Paphos, Cyprus, March 23\-26, 2026,T\. Kuflik, S\. Kleanthous, L\. Chen, G\. Jaccuci, and A\. Smith\-Renner \(Eds\.\),pp\. 1625–1646\.External Links:[Link](https://doi.org/10.1145/3742413.3789078),[Document](https://dx.doi.org/10.1145/3742413.3789078)Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p2.1),[§1\.2](https://arxiv.org/html/2608.18631#S1.SS2.p3.1)\.
- \[59\]T\. Quint and J\. Wako\(2004\)On houseswapping, the strict core, segmentation, and linear programming\.Mathematics of Operations Research29\(4\),pp\. 861–877\.External Links:[Document](https://dx.doi.org/10.1287/moor.1040.0106),[Link](https://doi.org/10.1287/moor.1040.0106),https://doi\.org/10\.1287/moor\.1040\.0106Cited by:[2nd item](https://arxiv.org/html/2608.18631#A5.I1.i2.p1.1)\.
- \[60\]D\. Rein, B\. L\. Hou, A\. C\. Stickland, J\. Petty, R\. Y\. Pang, J\. Dirani, J\. Michael, and S\. R\. Bowman\(2023\)GPQA: A graduate\-level google\-proof q&a benchmark\.CoRRabs/2311\.12022\.External Links:[Link](https://doi.org/10.48550/arXiv.2311.12022),[Document](https://dx.doi.org/10.48550/ARXIV.2311.12022),2311\.12022Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p1.1),[§2\.2](https://arxiv.org/html/2608.18631#S2.SS2.p7.1)\.
- \[61\]M\. Ríos, R\. F\. Manrique, N\. Quijano, and L\. F\. Giraldo\(2025\)The illusion of rationality: tacit bias and strategic dominance in frontier LLM negotiation games\.CoRRabs/2512\.09254\.External Links:[Link](https://doi.org/10.48550/arXiv.2512.09254),[Document](https://dx.doi.org/10.48550/ARXIV.2512.09254),2512\.09254Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p2.1),[§1\.2](https://arxiv.org/html/2608.18631#S1.SS2.p3.1)\.
- \[62\]K\. Rong, Q\. Tang, and Y\. Zhang\(2024\)The core of school choice problems\.Economic Theory77\(3\),pp\. 783–800\.Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p3.1)\.
- \[63\]A\. E\. Roth and A\. Postlewaite\(1977\)Weak versus strong domination in a market with indivisible goods\.Journal of Mathematical Economics4\(2\),pp\. 131–137\.External Links:ISSN 0304\-4068,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/0304-4068%2877%2990004-0),[Link](https://www.sciencedirect.com/science/article/pii/0304406877900040)Cited by:[§E\.1](https://arxiv.org/html/2608.18631#A5.SS1.p3.1),[§E\.1](https://arxiv.org/html/2608.18631#A5.SS1.p5.1)\.
- \[64\]A\. E\. Roth\(1982\)The economics of matching: stability and incentives\.Mathematics of operations research7\(4\),pp\. 617–628\.Cited by:[1st item](https://arxiv.org/html/2608.18631#A5.I3.i1.p1.1),[3rd item](https://arxiv.org/html/2608.18631#A5.I3.i3.p1.1)\.
- \[65\]I\. Schlotter and L\. M\. Mendoza\-Cadena\(2025\)The strong core of housing markets with partial order preferences\.InProceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2025, Detroit, MI, USA, May 19\-23, 2025,S\. Das, A\. Nowé, and Y\. Vorobeychik \(Eds\.\),pp\. 1867–1875\.External Links:[Link](https://dl.acm.org/doi/10.5555/3709347.3743823),[Document](https://dx.doi.org/10.5555/3709347.3743823)Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p3.1)\.
- \[66\]M\. Sclar, Y\. Choi, Y\. Tsvetkov, and A\. Suhr\(2023\)Quantifying language models’ sensitivity to spurious features in prompt design or: how i learned to start worrying about prompt formatting\.arXiv preprint arXiv:2310\.11324\.Cited by:[Appendix B](https://arxiv.org/html/2608.18631#A2.p3.1)\.
- \[67\]A\. SEN\(2017\)Collective choice and social welfare: an expanded edition\.Harvard University Press\.External Links:ISBN 9780674971608,[Link](http://www.jstor.org/stable/j.ctv2sp3dqx)Cited by:[§E\.1](https://arxiv.org/html/2608.18631#A5.SS1.p6.2)\.
- \[68\]L\. Shapley and H\. Scarf\(1974\)On cores and indivisibility\.Journal of mathematical economics1\(1\),pp\. 23–37\.Cited by:[1st item](https://arxiv.org/html/2608.18631#A5.I3.i1.p1.1),[§E\.1](https://arxiv.org/html/2608.18631#A5.SS1.p3.1),[§2\.1](https://arxiv.org/html/2608.18631#S2.SS1.p1.1)\.
- \[69\]Z\. Shi, R\. Ma, J\. Huang, X\. Ma, X\. Chen, M\. Wang, Q\. Yang, Y\. Wang, F\. Ye, Z\. Chen, S\. Wang, C\. Li, W\. Wang, Z\. Tu, X\. Li, Z\. Ren, and Linus\(2025\)Social welfare function leaderboard: when LLM agents allocate social welfare\.CoRRabs/2510\.01164\.External Links:[Link](https://doi.org/10.48550/arXiv.2510.01164),[Document](https://dx.doi.org/10.48550/ARXIV.2510.01164),2510\.01164Cited by:[§I\.5](https://arxiv.org/html/2608.18631#A9.SS5.SSS0.Px1.p1.1)\.
- \[70\]P\. Shojaee, I\. Mirzadeh, K\. Alizadeh, M\. Horton, S\. Bengio, and M\. Farajtabar\(2025\)The illusion of thinking: understanding the strengths and limitations of reasoning models via the lens of problem complexity\.InNeurIPS,External Links:[Link](https://arxiv.org/abs/2506.06941)Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p1.1),[§1\.2](https://arxiv.org/html/2608.18631#S1.SS2.p1.1),[§4\.1](https://arxiv.org/html/2608.18631#S4.SS1.p1.1)\.
- \[71\]A\. Simhi, I\. Itzhak, F\. Barez, G\. Stanovsky, and Y\. Belinkov\(2025\)Trust me, i’m wrong: llms hallucinate with certainty despite knowing the answer\.InFindings of the Association for Computational Linguistics: EMNLP 2025, Suzhou, China, November 4\-9, 2025,C\. Christodoulopoulos, T\. Chakraborty, C\. Rose, and V\. Peng \(Eds\.\),pp\. 14665–14688\.External Links:[Link](https://aclanthology.org/2025.findings-emnlp.792/)Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p6.1),[§1\.2](https://arxiv.org/html/2608.18631#S1.SS2.p1.1),[§2\.2](https://arxiv.org/html/2608.18631#S2.SS2.p6.1)\.
- \[72\]A\. Singh, A\. Fry, A\. Perelman, A\. Tart, A\. Ganesh, A\. El\-Kishky, A\. McLaughlin, A\. Low, A\. Ostrow, A\. Ananthram,et al\.\(2025\)Openai gpt\-5 system card\.arXiv preprint arXiv:2601\.03267\.Cited by:[§2\.2](https://arxiv.org/html/2608.18631#S2.SS2.p7.1)\.
- \[73\]L\. Svensson\(1999\)Strategy\-proof allocation of indivisible goods\.Social Choice and Welfare16\(4\),pp\. 557–567\.External Links:ISSN 01761714, 1432217X,[Link](http://www.jstor.org/stable/41106323)Cited by:[2nd item](https://arxiv.org/html/2608.18631#A5.I3.i2.p1.1),[§2\.1](https://arxiv.org/html/2608.18631#S2.SS1.p1.1)\.
- \[74\]A\. Templeton, T\. Conerly, J\. Marcus, J\. Lindsey, T\. Bricken, B\. Chen, A\. Pearce, C\. Citro, E\. Ameisen, A\. Jones, H\. Cunningham, N\. L\. Turner, C\. McDougall, M\. MacDiarmid, C\. D\. Freeman, T\. R\. Sumers, E\. Rees, J\. Batson, A\. Jermyn, S\. Carter, C\. Olah, and T\. Henighan\(2024\)Scaling monosemanticity: extracting interpretable features from claude 3 sonnet\.Transformer Circuits Thread\.External Links:[Link](https://transformer-circuits.pub/2024/scaling-monosemanticity/index.html)Cited by:[Appendix B](https://arxiv.org/html/2608.18631#A2.p2.1)\.
- \[75\]M\. H\. Tessler, M\. A\. Bakker, D\. Jarrett, H\. Sheahan, M\. J\. Chadwick, R\. Koster, G\. Evans, L\. Campbell\-Gillingham, T\. Collins, D\. C\. Parkes, M\. Botvinick, and C\. Summerfield\(2024\)AI can help humans find common ground in democratic deliberation\.Science386\(6719\),pp\. eadq2852\.External Links:[Document](https://dx.doi.org/10.1126/science.adq2852),[Link](https://www.science.org/doi/abs/10.1126/science.adq2852),https://www\.science\.org/doi/pdf/10\.1126/science\.adq2852Cited by:[§1](https://arxiv.org/html/2608.18631#S1.p2.1)\.
- \[76\]N\. Thach, X\. Sha, and H\. Chan\(2026\)Large language models for designing participatory budgeting rules\.CoRRabs/2602\.09349\.External Links:[Link](https://doi.org/10.48550/arXiv.2602.09349),[Document](https://dx.doi.org/10.48550/ARXIV.2602.09349),2602\.09349Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p4.1),[§1\.2](https://arxiv.org/html/2608.18631#S1.SS2.p3.1)\.
- \[77\]K\. Tian, E\. Mitchell, A\. Zhou, A\. Sharma, R\. Rafailov, H\. Yao, C\. Finn, and C\. D\. Manning\(2023\)Just ask for calibration: strategies for eliciting calibrated confidence scores from language models fine\-tuned with human feedback\.InProceedings of the 2023 Conference on Empirical Methods in Natural Language Processing,pp\. 5433–5442\.Cited by:[Appendix B](https://arxiv.org/html/2608.18631#A2.p4.1)\.
- \[78\]D\. Waldinger\(2021\)Targeting in\-kind transfers through market design: a revealed preference analysis of public housing allocation\.American Economic Review111\(8\),pp\. 2660–96\.External Links:[Document](https://dx.doi.org/10.1257/aer.20190516),[Link](https://www.aeaweb.org/articles?id=10.1257/aer.20190516)Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p3.1)\.
- \[79\]C\. Wang, D\. Kasenberg, K\. Stachenfeld, and P\. S\. Castro\(2026\)Discovering differences in strategic behavior between humans and llms\.CoRRabs/2602\.10324\.External Links:[Link](https://doi.org/10.48550/arXiv.2602.10324),[Document](https://dx.doi.org/10.48550/ARXIV.2602.10324),2602\.10324Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p2.1),[§1\.2](https://arxiv.org/html/2608.18631#S1.SS2.p3.1)\.
- \[80\]Y\. Wang, X\. Ma, G\. Zhang, Y\. Ni, A\. Chandra, S\. Guo, W\. Ren, A\. Arulraj, X\. He, Z\. Jiang,et al\.\(2024\)Mmlu\-pro: a more robust and challenging multi\-task language understanding benchmark\.Advances in Neural Information Processing Systems37,pp\. 95266–95290\.Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p1.1)\.
- \[81\]K\. Yamin, J\. Tang, S\. Cortes\-Gomez, A\. Sharma, E\. Horvitz, and B\. Wilder\(2026\)Do llms act like rational agents? measuring belief coherence in probabilistic decision making\.CoRRabs/2602\.06286\.External Links:[Link](https://doi.org/10.48550/arXiv.2602.06286),[Document](https://dx.doi.org/10.48550/ARXIV.2602.06286),2602\.06286Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p2.1),[§1\.2](https://arxiv.org/html/2608.18631#S1.SS2.p3.1)\.
- \[82\]J\. C\. Yang, D\. Dailisan, M\. Korecki, C\. I\. Hausladen, and D\. Helbing\(2024\)LLM voting: human choices and AI collective decision\-making\.InProceedings of the Seventh AAAI/ACM Conference on AI, Ethics, and Society \(AIES\-24\) \- Full Archival Papers, October 21\-23, 2024, San Jose, California, USA \- Volume 1,S\. Das, B\. P\. Green, K\. Varshney, M\. Ganapini, and A\. Renda \(Eds\.\),pp\. 1696–1708\.External Links:[Link](https://doi.org/10.1609/aies.v7i1.31758),[Document](https://dx.doi.org/10.1609/AIES.V7I1.31758)Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p4.1),[§1\.2](https://arxiv.org/html/2608.18631#S1.SS2.p3.1)\.
- \[83\]G\. Yona, R\. Aharoni, and M\. Geva\(2024\)Can large language models faithfully express their intrinsic uncertainty in words?\.InProceedings of the 2024 Conference on Empirical Methods in Natural Language Processing,Y\. Al\-Onaizan, M\. Bansal, and Y\. Chen \(Eds\.\),Miami, Florida, USA,pp\. 7752–7764\.External Links:[Link](https://aclanthology.org/2024.emnlp-main.443/),[Document](https://dx.doi.org/10.18653/v1/2024.emnlp-main.443)Cited by:[Appendix D](https://arxiv.org/html/2608.18631#A4.p6.1),[§1\.2](https://arxiv.org/html/2608.18631#S1.SS2.p1.1)\.

Technical Appendices and Supplementary Material

## Appendix AGenerative AI Use Statement

AI tools were used in three ways in the course of this work\. First, they assisted with implementation, including writing and debugging the benchmark generation, inference, and analysis code\. Second, they were used to polish the writing of the main paper, without generating any of its claims or results\. Third, they helped synthesize findings about the reasoning traces collected in the LLM\-judge experiments of[AppendixL](https://arxiv.org/html/2608.18631#A12)and[AppendixP](https://arxiv.org/html/2608.18631#A16), where the judge outputs are themselves model\-generated and are validated against additional judges and a human annotator in[SectionP\.3](https://arxiv.org/html/2608.18631#A16.SS3)\. All experimental results, numbers, and claims in the paper were produced and checked by the authors\.

## Appendix BLimitations and future directions

Our evaluation is bounded in three ways that are worth stating\. First, we test four models, spanning two closed families and one open\-weights family\. They are the current frontier, but the panel is small, so we report per\-model results throughout rather than a single pooled number\. Second, we sample instances under Impartial Culture, which lets us build matched determined and undetermined instances on the same profile and control feasibility exactly\. The sampler decides which instances turn out feasible, not the reasoning a task demands, so we do not expect structured distributions such as Mallows or single\-peaked preferences to change the picture, though we have not tested this\. Third, two of our analyses infer what a model intended from its reasoning trace, and so depend on a judge model\.[SectionP\.3](https://arxiv.org/html/2608.18631#A16.SS3)reports that judge’s agreement with two additional judges and with a human annotator, and flags the one cell where they disagree\. Every other result is scored by deterministic checkers, which we validate against a brute\-force solver in the same appendix\.

These bounds aside, our evaluation establishes what current reasoning models do when confronted with indeterminate preference queries, and leaves open why they do it\. The systematic assumptions we identify \(e\.g\. lexicographic tie\-breaking on bundles, premature termination on partial\-order chains\) are robust empirical patterns, but their underlying mechanism is opaque to the input\-output methodology used here\. Recent advances in mechanistic interpretability\[[51](https://arxiv.org/html/2608.18631#bib.bib76),[5](https://arxiv.org/html/2608.18631#bib.bib77),[74](https://arxiv.org/html/2608.18631#bib.bib78)\]suggest that these failures could be traced to specific circuits or features within the model, illuminating whether models silently override their own indeterminacy detection or fail to recognize it altogether\.

The role of prompt framing is likewise only partly mapped\. We vary it along three coarse axes \(free\-flow, free\-flow \+ “if known”, MCQ\) but do not characterize the threshold at which a prompt becomes informative enough to elicit reliable abstention\. Finer\-grained probing along the lines of[66](https://arxiv.org/html/2608.18631#bib.bib79)and[47](https://arxiv.org/html/2608.18631#bib.bib36)could map this transition more precisely\.

A final question is which aspects of training data and post\-training procedures determine a model’s calibration to indeterminacy\. Recent advances in scalable data attribution\[[17](https://arxiv.org/html/2608.18631#bib.bib82)\]and frameworks that bridge interpretability and data influence\[[16](https://arxiv.org/html/2608.18631#bib.bib83)\], combined with analyses of calibration shifts during alignment\[[45](https://arxiv.org/html/2608.18631#bib.bib62),[77](https://arxiv.org/html/2608.18631#bib.bib63)\], could distinguish whether targeted fine\-tuning would address the underlying calibration issue or merely mask the surface symptoms\.

## Appendix CBroader Impacts

The findings in this paper bear directly on two deployment contexts where LLMs are increasingly used to reason over preferences\. First, agentic systems acting on behalf of users — making purchases, scheduling commitments, mediating between conflicting goals — must distinguish between situations in which the user’s stated preferences determine an action and situations in which they do not\. Our results show that current frontier models systematically fail at this distinction, which means an agentic system built on these models may, by default, take actions that the user has not actually authorized, while presenting them as reflecting the user’s preferences\. Second, platforms that aggregate preferences for collective decision\-making — participatory budgeting tools, deliberation platforms, large\-scale opinion\-mapping systems — depend on the assumption that the aggregation faithfully reflects the inputs\. When the input is structurally indeterminate \(incomplete preferences, infeasibility under ties, etc\.\), a model that confidently produces an aggregate is generating an artificial consensus that does not exist in the data\. Our work surfaces these failure modes in a controlled evaluation, with the goal of making them measurable and addressable before such systems are deployed in higher\-stakes settings\.

## Appendix DExtended Related Work

LLM Reasoning Benchmarks\.Existing benchmarks evaluate LLMs on mathematical reasoning\[[18](https://arxiv.org/html/2608.18631#bib.bib72),[30](https://arxiv.org/html/2608.18631#bib.bib74),[80](https://arxiv.org/html/2608.18631#bib.bib35)\], scientific reasoning\[[57](https://arxiv.org/html/2608.18631#bib.bib16),[60](https://arxiv.org/html/2608.18631#bib.bib73)\], and code generation\[[41](https://arxiv.org/html/2608.18631#bib.bib34),[44](https://arxiv.org/html/2608.18631#bib.bib70)\]\. These assess whether a model reaches the correct answer, but provide limited insights into the ability of LLMs to execute algorithms correctly\. Two recent papers show that LLMs fail to execute well\-known algorithms as instance size grows:[31](https://arxiv.org/html/2608.18631#bib.bib14)trace this collapse in the commonly used Deferred Acceptance algorithm to compounding step\-level errors, and[70](https://arxiv.org/html/2608.18631#bib.bib58)find the same pattern on combinatorial puzzles \(e\.g\. the missionaries and cannibals problem, tower of Hanoi, etc\.\)\. Both papers characterize algorithmic failure without distinguishing among algorithms — that is, they do not ask whether some algorithms are harder than others or why\. We build on this by asking a finer question: do LLMs fail uniformly across algorithms, or is performance related to properties of the algorithm itself? Our findings suggest the latter, with training\-data familiarity playing a larger role than computational complexity\.

Rationality and Strategic Reasoning\.A complementary literature asks whether LLMs behave as rational agents in strategic settings\. Recent reasoning models come closer to equilibrium play than earlier ones\[[43](https://arxiv.org/html/2608.18631#bib.bib71)\]and identify strategic patterns faster than humans\[[79](https://arxiv.org/html/2608.18631#bib.bib32)\], yet LLMs still exhibit anchoring effects and model\-specific biases that prevent convergence to optimal solutions\[[61](https://arxiv.org/html/2608.18631#bib.bib21),[58](https://arxiv.org/html/2608.18631#bib.bib33)\], and their stated probabilities over outcomes frequently violate basic Bayesian consistency conditions\[[81](https://arxiv.org/html/2608.18631#bib.bib24),[37](https://arxiv.org/html/2608.18631#bib.bib22)\]\. These papers evaluate LLMs as strategic actors optimizing over outcomes\. Our focus is orthogonal: we evaluate LLMs as procedure executors applying a specified algorithm to a given input\. This distinction is consequential because optimal strategy computation in many settings itself requires running sophisticated algorithms \(for instance, computing the core of a cooperative game or finding a stable matching\) so failures in procedure execution place a ceiling on strategic rationality as well\[[56](https://arxiv.org/html/2608.18631#bib.bib26)\]\.[35](https://arxiv.org/html/2608.18631#bib.bib18)show that LLMs can achieve Pareto\-optimal and envy\-free outcomes in negotiation settings; our results suggest this may reflect approximate pattern\-matching rather than principled computation, since the same notions are computed unreliably when formally defined and applied to structured inputs\.

LLMs for Social Choice\.Computational social choice studies how individual preferences can be aggregated into collective decisions, with active subliteratures on house allocation\[[2](https://arxiv.org/html/2608.18631#bib.bib60),[53](https://arxiv.org/html/2608.18631#bib.bib40),[33](https://arxiv.org/html/2608.18631#bib.bib41),[34](https://arxiv.org/html/2608.18631#bib.bib42),[65](https://arxiv.org/html/2608.18631#bib.bib55),[11](https://arxiv.org/html/2608.18631#bib.bib43),[78](https://arxiv.org/html/2608.18631#bib.bib50)\], resource allocation\[[4](https://arxiv.org/html/2608.18631#bib.bib44),[9](https://arxiv.org/html/2608.18631#bib.bib46),[52](https://arxiv.org/html/2608.18631#bib.bib51),[38](https://arxiv.org/html/2608.18631#bib.bib52)\], and matching markets\[[23](https://arxiv.org/html/2608.18631#bib.bib47),[15](https://arxiv.org/html/2608.18631#bib.bib45),[62](https://arxiv.org/html/2608.18631#bib.bib48),[8](https://arxiv.org/html/2608.18631#bib.bib49),[49](https://arxiv.org/html/2608.18631#bib.bib53)\]\. As LLMs are increasingly proposed as components of decision\-making pipelines in these domains, recent work has begun to ask both whether LLMs can compute the outcomes that social\-choice theory prescribes, and whether their default behaviour aligns with how humans think about fairness\.

On the fairness alignment side,[32](https://arxiv.org/html/2608.18631#bib.bib15)and[20](https://arxiv.org/html/2608.18631#bib.bib8)both find that when LLMs are asked to allocate resources fairly, their choices differ from human judgments in the same way: they tend to maximise overall welfare rather than spread benefits equally, and this pattern is robust to changes in how the prompt is phrased\.[32](https://arxiv.org/html/2608.18631#bib.bib15)additionally find that what the LLM says it will do does not always match the allocation it actually produces\. We recover both findings on a broader range of solution concepts and preference structures \(Section[I\.5](https://arxiv.org/html/2608.18631#A9.SS5)\), suggesting that they extend beyond resource allocation to allocation and matching tasks more generally\. On the solving side,[31](https://arxiv.org/html/2608.18631#bib.bib14)evaluate LLMs as one\-shot solvers on stable\-matching instances, while[27](https://arxiv.org/html/2608.18631#bib.bib17)embed an LLM in an iterative loop, giving it feedback in the form of blocking pairs and measuring how its solution improves over rounds\. Both papers analyse the kinds of failures the model makes; we contribute to this line of work by studying how LLMs behave when a question is underspecified or when no valid solution exists\. Other recent work has applied LLMs to voting\[[82](https://arxiv.org/html/2608.18631#bib.bib68)\], where the choice an LLM makes among candidates depends on the order in which the options are listed and on which voting rule is used, and to participatory budgeting\[[76](https://arxiv.org/html/2608.18631#bib.bib20)\], where LLMs are used to design heuristics for selecting which projects to fund\.

LLMs for Preference Elicitation\.LLMs are increasingly deployed as proxies for human preferences in elicitation pipelines, using techniques ranging from Bayesian query selection\[[29](https://arxiv.org/html/2608.18631#bib.bib19),[7](https://arxiv.org/html/2608.18631#bib.bib23)\]to LLM\-simulated preference profiles\[[36](https://arxiv.org/html/2608.18631#bib.bib67),[55](https://arxiv.org/html/2608.18631#bib.bib31)\]and direct comparative elicitation\[[50](https://arxiv.org/html/2608.18631#bib.bib30)\]\. These systems implicitly assume that LLMs can reason reliably about structured preferences\. Our benchmark directly tests this assumption and finds it to be optimistic, particularly under incomplete information and multi\-agent aggregation\.

Abstention and Uncertainty\.[47](https://arxiv.org/html/2608.18631#bib.bib36)show that abstention, i\.e\. the ability to refrain from answering when unsure, is unsolved across frontier models and that reasoning fine\-tuning can degrade it\. Systematic miscalibration between models’ intrinsic uncertainty and how they express it is well documented\[[83](https://arxiv.org/html/2608.18631#bib.bib25),[46](https://arxiv.org/html/2608.18631#bib.bib28)\], and models can hallucinate with high confidence even on questions they have the capacity to answer correctly\[[71](https://arxiv.org/html/2608.18631#bib.bib29),[1](https://arxiv.org/html/2608.18631#bib.bib27),[12](https://arxiv.org/html/2608.18631#bib.bib6)\]\. A related failure appears in moral decision\-making, where models do not reproduce the indecision humans express on hard choices, even though that indecision signals a need for further deliberation\[[22](https://arxiv.org/html/2608.18631#bib.bib3)\]\. Our results contribute a more structured instance of this failure: when preference queries are formally underdetermined, models do not abstain but instead make implicit, predictable assumptions, such as lexicographic tie\-breaking or alphabetical completion of partial lists\. Crucially, providing an explicit uncertainty option eliminates this behavior in some settings but not others, suggesting the failure is not purely one of output formatting but of recognizing underdetermination itself\.

## Appendix EExtended Preliminaries

Table 2:Preference expressivity, axioms, and properties\. In each case, we consider complete orders and incomplete orders where the preference is truncated \(missing the tail\)\.Preference ExpressivityDescriptionDetermining PropertyComplete Strict Linear OrderAsymmetric, transitive, and total\.Always determined\.Complete Order with TiesAllows ties \(a∼ba\\sim b\); total\.Determined \(indifference is explicit\)\.Incomplete Order with TiesAllows ties and missing pairs\.Undetermined if incomparable \(a\|ba\\parallel b\)\.Partial Order / Pairwise SetsTransitive and asymmetric; missing pairs\.Determined only if in the transitive closure\.### E\.1Solution Concepts

We define the solution concepts evaluated in this work, grouped by the domain and preference structure in which they apply\.

Pareto optimality\.An outcomeμ\\muis*Pareto\-optimal*\(PO\) if there exists no feasible outcomeμ′\\mu^\{\\prime\}such thatμ′\(i\)⪰iμ\(i\)\\mu^\{\\prime\}\(i\)\\succeq\_\{i\}\\mu\(i\)for alli∈Ni\\in Nandμ′\(j\)≻jμ\(j\)\\mu^\{\\prime\}\(j\)\\succ\_\{j\}\\mu\(j\)for somej∈Nj\\in N\. Under incomplete preferences, we additionally consider*maximum\-cardinality Pareto\-optimal*\(MCPO\) allocations: among all allocations that match the maximum number of agents to ranked alternatives, those that are Pareto\-optimal\.

Core \(Shapley–Scarf housing market\)\.The core and TTC are notions of the endowment economy, so we state them for the Shapley–Scarf market rather than for house allocation without endowments\. LetS⊆NS\\subseteq Nbe a coalition\. Understrict preferences,SS*blocks*an allocationμ\\muif there exists a reassignmentμS\\mu\_\{S\}of\{e⁡\(i\):i∈S\}\\\{e\(i\):i\\in S\\\}among members ofSSsuch thatμS\(i\)≻iμ\(i\)\\mu\_\{S\}\(i\)\\succ\_\{i\}\\mu\(i\)for alli∈Si\\in S\. An allocation is in the*core*if no coalition blocks it\. The core always exists under strict preferences and coincides with the unique output of Top Trading Cycles \(TTC\)\[[68](https://arxiv.org/html/2608.18631#bib.bib59),[63](https://arxiv.org/html/2608.18631#bib.bib4)\]\.

Underpreferences with ties, the definition of blocking depends on how ties are treated, giving rise to two notions:

- •Weak core:SSblocksμ\\muif there exists a reassignmentμS\\mu\_\{S\}such thatμS\(i\)≻iμ\(i\)\\mu\_\{S\}\(i\)\\succ\_\{i\}\\mu\(i\)for alli∈Si\\in S\(every member strictly improves\)\. An allocation is in the weak core if no such coalition exists\. The weak core always exists and coincides with the TTC output under a consistent tie\-breaking rule\.
- •Strict core:SSblocksμ\\muif there exists a reassignmentμS\\mu\_\{S\}such thatμS\(i\)⪰iμ\(i\)\\mu\_\{S\}\(i\)\\succeq\_\{i\}\\mu\(i\)for alli∈Si\\in SandμS\(j\)≻jμ\(j\)\\mu\_\{S\}\(j\)\\succ\_\{j\}\\mu\(j\)for somej∈Sj\\in S\(every member weakly improves, at least one strictly improves\)\. An allocation is in the strict core if no such coalition exists\. The strict core may be empty, but can be computed in polynomial time if it exists\[[59](https://arxiv.org/html/2608.18631#bib.bib56)\]\.

Note that under strict preferences the two notions coincide \(weak preference improvements always resolve to strict ones when no indifference exists\), so we simply refer to the*core*in that setting\. It is worth making the uniqueness explicit: under strict preferences the strict core is a singleton, namely the TTC allocation\[[63](https://arxiv.org/html/2608.18631#bib.bib4)\], so the distinction between the weak and the strict core only has content once ties are present\.

Welfare objectives\.For an allocation or matchingμ\\mu:

UW⁡\(μ\)\\displaystyle\\mathrm\{UW\}\(\\mu\)=∑i∈N−1∗ranki\(μ\(i\)\),\(Utilitarian Welfare, maximized\)\\displaystyle=\\sum\_\{i\\in N\}\-1\*\\mathrm\{rank\}\_\{i\}\(\\mu\(i\)\),\\qquad\\text\{\(Utilitarian Welfare, maximized\)\}EW⁡\(μ\)\\displaystyle\\mathrm\{EW\}\(\\mu\)=maxi∈N−1∗ranki​\(μ⁡\(i\)\)\.\(Egalitarian Welfare, maximized\)\\displaystyle=\\max\_\{i\\in N\}\-1\*\\mathrm\{rank\}\_\{i\}\(\\mu\(i\)\)\.\\qquad\\text\{\(Egalitarian Welfare, maximized\)\}A*utilitarian welfare\-maximizing*\(UW\) outcome maximizesUW⁡\(μ\)\\mathrm\{UW\}\(\\mu\)\[[10](https://arxiv.org/html/2608.18631#bib.bib81)\]; an*egalitarian welfare\-maximizing*\(EW\) outcome maximizesEW⁡\(μ\)\\mathrm\{EW\}\(\\mu\)\[[67](https://arxiv.org/html/2608.18631#bib.bib80)\]\.

Rank\-maximality\.For an outcomeμ\\mu, define its*rank vector*r⁡\(μ\)=\(r1,r2,…,rm\)r\(\\mu\)=\(r\_\{1\},r\_\{2\},\\ldots,r\_\{m\}\), whererkr\_\{k\}is the number of agents assigned an alternative of rankkk\. An outcome is*rank\-maximal*\(RM\) if its rank vector is lexicographically maximal over all feasible outcomes\[[39](https://arxiv.org/html/2608.18631#bib.bib9)\]\.

###### Example 1\(Rank vector\)\.

With three agents assigned to rank\-1 alternatives, none to rank\-2, and one to rank\-3, the rank vector is\(3,0,1\)\(3,0,1\)\. Rank\-maximality prefers\(3,0,1\)\(3,0,1\)to\(2,2,0\)\(2,2,0\): as many rank\-1 assignments as possible first, then as many rank\-2, and so on\.

Stability \(two\-sided matching\)\.Let\(m,w\)\(m,w\)be an unmatched pair\. Understrict preferences,\(m,w\)\(m,w\)*blocks*a matchingμ\\muifw≻mμ\(m\)w\\succ\_\{m\}\\mu\(m\)andm≻wμ\(w\)m\\succ\_\{w\}\\mu\(w\), i\.e\. both strictly prefer each other to their current partners\. A matching is*stable*if no blocking pair exists\. Stable matchings always exist and can be computed by Deferred Acceptance \(DA\)\[[28](https://arxiv.org/html/2608.18631#bib.bib66)\]\.

Underpreferences with ties, the meaning of “blocking” is no longer unique, yielding three stability concepts of increasing strength:

- •Weak stability:\(m,w\)\(m,w\)blocksμ\\muif both strictly prefer each other to their assigned partners \(w≻mμ\(m\)w\\succ\_\{m\}\\mu\(m\)andm≻wμ\(w\)m\\succ\_\{w\}\\mu\(w\)\)\. This coincides with the strict\-preference definition; weakly stable matchings always exist\.
- •Strong stability:\(m,w\)\(m,w\)blocksμ\\muif both weakly prefer each other to their partners and at least one strictly prefers \(w⪰mμ\(m\)w\\succeq\_\{m\}\\mu\(m\),m⪰wμ\(w\)m\\succeq\_\{w\}\\mu\(w\), and at least one inequality is strict\)\. Strongly stable matchings may not exist, but can be found in polynomial time when they do\[[40](https://arxiv.org/html/2608.18631#bib.bib75)\]\.
- •Super stability:\(m,w\)\(m,w\)blocksμ\\muif both weakly prefer each other to their partners \(w⪰mμ\(m\)w\\succeq\_\{m\}\\mu\(m\)andm⪰wμ\(w\)m\\succeq\_\{w\}\\mu\(w\)\)\. Super stable matchings may not exist, but can be found in polynomial time when they do\[[40](https://arxiv.org/html/2608.18631#bib.bib75)\]\.

The three notions are nested: every super stable matching is strongly stable, and every strongly stable matching is weakly stable\. The converse does not hold in general\. Note that, the definitions of a stable matching when preferences are strict, and that of a super stable matching when preferences have ties, are equivalent \(similar to the relationship between strict core and core in the house allocation setting\)\.

Canonical algorithms\.Each domain admits a canonical algorithm, i\.e\. one that is not only computationally efficient but is uniquely characterized by a combination of desirable axiomatic properties, making it the natural first choice for practitioners and the standard reference in the literature\.

- •Top Trading Cycles \(TTC\)for the Shapley–Scarf housing market computes the unique allocation in the core\[[68](https://arxiv.org/html/2608.18631#bib.bib59)\]and is the only mechanism that is individually rational, Pareto\-optimal, and strategy\-proof\[[54](https://arxiv.org/html/2608.18631#bib.bib2),[64](https://arxiv.org/html/2608.18631#bib.bib57)\]\.
- •Serial Dictatorship \(SD\)for object allocation is the unique mechanism that is Pareto\-optimal, strategy\-proof, and non\-bossy\[[73](https://arxiv.org/html/2608.18631#bib.bib10)\]\.
- •Deferred Acceptance \(DA\)for stable matching computes a stable matching that is weakly preferred by the proposing side to all other stable matchings, and is the unique stable and strategy\-proof mechanism \(for that side\)\[[28](https://arxiv.org/html/2608.18631#bib.bib66),[64](https://arxiv.org/html/2608.18631#bib.bib57)\]\.

## Appendix FDataset Creation Details

### F\.1Preference Reasoning Tasks

#### F\.1\.1Instance Generation

Strict and complete preferences\.Preferences are sampled under the impartial culture model: each agent’s ranking is drawn uniformly at random from all permutations ofAA\. Profile sizes range from 30 to 200 items; results are reported at sizes 50, 100, and 200\.

Strict and incomplete preferences\.Starting from a strict and complete preference list, each agent’s ranking is truncated to a length drawn uniformly from\[⌊0\.5​n⌋,n\]\[\\lfloor 0\.5n\\rfloor,n\], wherennis the number of items\. Items beyond the truncation point are unranked\.

Complete preferences with ties\.Starting from a strict and complete preference list, ties are introduced by randomly selecting contiguous ranges of items and merging them into indifference classes\. Each generated profile contains two tie groups, with at least one item ranked outside any tie\. The starting and ending position of each tie are selected randomly from possible values\. Once these position are selected, we insert brackets into these positions and indicate that the items within the brackets are tied\.

Partial order preferences\.Partial\-order preferences are generated as Erdős–Rényi DAGs\[[25](https://arxiv.org/html/2608.18631#bib.bib39)\]\(a common approach in prior work\[[14](https://arxiv.org/html/2608.18631#bib.bib54),[42](https://arxiv.org/html/2608.18631#bib.bib38)\]\) oriented consistently with a latent total order\. We use up to 100 nodes and edge counts of 50, 80, or 150 \(denser graphs yielding fewer incomparable pairs\)\.

#### F\.1\.2Benchmark Design

The preference reasoning benchmark consists of task families, each targeting a different aspect of preference comprehension\.

Atomic queries\.Retrieval regarding single item within the preference profile:

- •Position query: at what position does a given item appear in the agent’s preference?
- •Item query: which item does the agent rank at a given positionkk?

Comparative queries\.Relative preference of multiple items by an agent:

- •Item comparison: between 2 given items, which is preferred by the agent?
- •Item ranking: given a set of four items, rank them according to the agent’s preference\.

Under strict and complete preferences, each question has a unique determined answer\. Under strict and incomplete preferences, some questions become undetermined \(e\.g\. the queried item may be absent, orkkmay exceed the length of the list\), and the correct response is to indicate that the answer cannot be determined\. Under complete preferences with ties, we additionally include atop\-kkquery: does a given item belong to the agent’s top\-kkalternatives? Whenkkfalls within a tie group, this question is undetermined\.

For all question types, models are prompted to return their answer in a specified format\. In the free\-flow format, we do not provide explicit options\. For undetermined questions, two free\-flow variants are used: one that includes “if known”, and one that does not\. We additionally create MCQ versions for all problems and explore the impact of prompt format on model responses\.

Bundle comparisons\.A special case of comparative task\. Given a single agent’s preference ranking and two bundlesB,B′⊆AB,B^\{\\prime\}\\subseteq A, the model is asked which bundle the agent prefers\. Pairs are drawn from three preference types \(strict and complete, strict and incomplete, complete with ties\), and are constructed to include both RS\-comparable cases \(where a definite answer exists\) and RS\-incomparable cases \(where the correct response is that the comparison is undetermined\)\.

Aggregative queries\.Given a preference profile over multiple agents, the model is asked: “how many agents prefer itemaaover itembb?” This requires scanning all agents’ lists and tallying correctly\. We evaluate accuracy \(fraction of exact correct counts\) and mean absolute error on incorrect responses\.

Partial order queries\.Given a preference specified as a set of pairwise comparisons, the model is asked whether itemaais preferred to itembb\. We test both comparable pairs \(connected by a chain of stated comparisons\) and incomparable pairs \(no such chain exists\)\.

We additionally evaluate a second representation \(Format 2\) in which partial order information is conveyed as query\-answer pairs: each data point specifies a subset of items and the most preferred item within it\. Although logically equivalent to pairwise comparisons, this representation requires an additional inference step to recover the underlying structure\.

#### F\.1\.3Prompt Counts

Table 3:Preference reasoning benchmark composition\. Profile size refers to the number of items in the preference list\. In formats, “ff” refers to free\-flow prompt, “ff\_if\_known” refers to free\-flow prompt, added with "if known" phrase, and MCQ refers to multiple\-choice question\.Task familyPref\. TypeQuestion typesProfile sizesFormatsPromptsAtomicStrict \+completeItem query,position query,50, 100, 200ff, MCQ360Strict \+incompleteItem query\(undetermined\),position query\(undetermined\),50, 100, 200ff,ff\_if\_known,MCQ540ComparativeStrict \+completeitem comparison,item ranking50, 100, 200ff, MCQ360Strict \+incompleteitem comparison\(undetermined\),item ranking50, 100, 200ff,ff\_if\_known,MCQ720BundlecomparisonStrict \+completeRS\-comparable,RS\-incomparable,larger bundle,unequal bundle sizes50, 100ff,ff\_if\_known,MCQ300Strict \+incompleteRS\-comparable,RS\-incomparable50ff\_if\_known60Ties \+completeRS\-comparable,RS\-incomparable50ff\_if\_known60Top\-kqueryTies \+completeDetermined,Undetermined,break\-down queries50ff,ff\_if\_known120AggregativeStrict \+completeAgent count query50, 100ff, MCQ120Strict \+incompleteAgent count query50, 100ff, MCQ120Ties \+completeAgent count query50, 100ff60PartialorderPairwise\(Format 1\)Comparable pair,incomparable pair100 nodes\+ \{50, 80, 150\}edgesff,ff\_if\_known,MCQ420Query\-answer\(Format 2\)Comparable pair,incomparable pair30 nodes\+ \{30, 50\} edgesff,ff\_if\_known,MCQ120Total3360

The complete breakdown of the types of questions asked for each task, preference\-type, and size, are provided in[Table3](https://arxiv.org/html/2608.18631#A6.T3)\. Total count of 3360 prompts includes different prompting format\. The unique number of prompts, not multiplying by format, is 1740\.

### F\.2Algorithmic Reasoning Tasks

#### F\.2\.1Instance Generation

Preference sampling\.Strict and complete preferences are sampled under the impartial culture model, with each agent’s ranking drawn uniformly at random from all permutations ofAA\. Complete preferences with ties are derived by post\-processing: adjacent items in a strict ranking are merged into a tie\-group independently with probabilitypp\(p=0\.3p\{=\}0\.3for house allocation;p=0\.2p\{=\}0\.2for stable matching\)\. Strict and incomplete preferences are obtained by truncating each agent’s ranking to a length drawn uniformly from\[⌊0\.5​n⌋,n\]\[\\lfloor 0\.5n\\rfloor,\\,n\]\. An agent is never assigned an alternative it has not ranked, and is left unmatched instead, following the standard convention that unranked alternatives are unacceptable\. This is what keeps each solution concept well defined, so that an infeasible instance is infeasible because of the instance rather than because of how the truncation is read\.

Rejection sampling with distinctness constraints\.Instances are selected via rejection sampling from the stream of randomly generated profiles\. Every accepted instance must satisfy a*distinctness constraint*: the optimal outcome for each solution concept evaluated in that setting must be distinct from every other, and no outcome satisfying one concept may simultaneously satisfy another\. This ensures that correct model responses can be attributed unambiguously to the target notion, ruling out cases where a model succeeds by accidentally satisfying an easier notion\.

#### F\.2\.2Benchmark Design

For each combination of domain, preference type, and sizen∈\{10,30\}n\\in\\\{10,30\\\}, we collect 30 instances satisfying the distinctness constraint\. Each instance gives rise to two types of tasks:generation, where the model computes a solution from scratch given the preference profile, andselection, where it chooses among a set of presented candidates\. Generation prompts include a definition of the target notion and, by default, an instruction that the model may return\{\}\\\{\\\}\(i\.e\. an empty solution\) if it determines no valid solution exists\. Selection prompts present one candidate per solution concept evaluated in that setting, together with one or two*contaminated*candidates obtained by randomly swapping one or two assignments in the canonical algorithm’s output, with options in uniformly random order\. All models are evaluated on the same instances in a zero\-shot, single\-turn setting at their default temperature\.

The benchmark is structured around two components reflecting a natural partition of the solution concepts\.

Strict preferences\.Under strict preferences, all solution concepts of interest are guaranteed to exist for every instance\. For each applicable solution concept, one generation prompt is produced per instance; a further*unspecified*generation prompt is included in which no notion or definition is provided and the model is simply asked to compute “a matching” or “an allocation\.” This condition tests whether models default to the canonical algorithm in the absence of an explicit instruction\. One selection task is also produced per instance, asking the model to select the option it “prefers the most” from the candidate set without naming a target notion; this tests whether models’ default preferences align with canonically characterised solutions\.

We evaluate house allocation, object allocation, and stable matching under strict and complete preferences as the primary settings\. We additionally evaluate house allocation under strict and incomplete preferences to examine whether incompleteness affects performance; since this involves a single domain with a narrower set of notions, we treat it as a secondary setting\.

Preferences with ties\.We evaluate house allocation and stable matching under complete preferences with ties\.888Given the similarity between house allocation and object allocation, we do not separately evaluate object allocation with ties\.For certain notions such as weak core, weak stability, and the welfare and rank\-based notions, the algorithms required are shared with the strict setting \(e\.g\. TTC for weak core, DA for weak stability, Hungarian algorithm for utilitarian welfare, etc\.\)\. This enables a direct comparison of performance across preference types\. Table[4](https://arxiv.org/html/2608.18631#A6.T4)summarises all settings and prompt counts for these standard tasks\.

Ties additionally involve three solution concepts not guaranteed to exist for every instance: the strict core \(house allocation\), and strong and super stability \(stable matching\)\. These are excluded from the standard task structure above and are instead evaluated under a dedicated experimental design\. For each notion, we collect 30*feasible*instances \(where a valid solution exists, drawn from the standard pool\) and 30*infeasible*instances \(where no solution satisfying the notion exists\)\.999Infeasible instances for super stability are constructed to admit a strongly stable solution, to test whether models conflate the two concepts\.Each instance receives four prompt variants forming a2×22\\times 2design:

- •Generation with and without escape hatch\.By default the model is instructed it may return\{\}\\\{\\\}if no solution exists; in the ablation this instruction is removed\. The latter tests whether models generate overconfident solutions when no valid one exists, or express infeasibility through other means \(e\.g\. returningNone, populating the output dictionary with"None"values, or issuing a natural\-language disclaimer\)\.
- •Selection with and without NOTA\.We vary whether a “None of the Above” \(NOTA\) option is included in the candidate set\. The NOTA condition tests whether models correctly identify infeasibility when given an explicit escape; the no\-NOTA condition tests whether they select a spurious solution under pressure\.

This yields2​\(feasibility\)×2​\(task type\)×2​\(escape hatch / NOTA\)×3​\(notions\)×30​\(instances\)=7202~\\text\{\(feasibility\)\}\\times 2~\\text\{\(task type\)\}\\times 2~\\text\{\(escape hatch / NOTA\)\}\\times 3~\\text\{\(notions\)\}\\times 30~\\text\{\(instances\)\}=720additional prompts per size\.

Total\.The benchmark comprises1,830 prompts per sizenn, consisting of 1,110 from the standard settings in Table[4](https://arxiv.org/html/2608.18631#A6.T4)and 720 from the harder\-notions experiment, for a total of3,660 promptsacross both sizesn∈\{10,30\}n\\in\\\{10,30\\\}\. Each prompt is answered independently by all four models, yielding14,640 model responsesin total\.

Table 4:Benchmark composition for standard tasks \(solution concepts guaranteed to exist\)\. Each setting uses 30 instances\. Generation includes one prompt per listed notion \(each with the\{\}\\\{\\\}instruction by default\) plus one*unspecified*prompt; selection asks the model to choose its most preferred candidate without specifying a target notion\.ngenn\_\{\\text\{gen\}\}andnseln\_\{\\text\{sel\}\}denote prompts per instance; total=30×\(ngen\+nsel\)=30\\times\(n\_\{\\text\{gen\}\}\+n\_\{\\text\{sel\}\}\)\. Harder notions under preferences with ties \(strict core; strong and super stability\) are excluded from this table and evaluated separately\.†\\daggerTreated as a secondary setting\.‡\\ddaggerPO for house allocation with ties is verified via strong Pareto\-optimality under weak preferences\.DomainPref\. typeNotions \(generation\)ngenn\_\{\\text\{gen\}\}nseln\_\{\\text\{sel\}\}PromptsHouse allocationStrict \+ completeCore, PO, UW, EW, RM61210Strict \+ incomplete†Core, RM, MCPO41150Ties \+ completeWeak core, PO‡, UW, EW, RM61210Object allocationStrict \+ completePO, UW, EW, RM51180Stable matchingStrict \+ completeStable, UW, EW, RM51180Ties \+ completeWeakly stable, UW, EW, RM51180Subtotal per sizenn1,110

## Appendix GModel and Inference Details

We evaluate four frontier models, listed in Table[5](https://arxiv.org/html/2608.18631#A7.T5)with their exact identifiers, hosting providers, and per\-call inference settings\. All four are accessed through their providers’ hosted APIs at decoding time, with no fine\-tuning\. Temperature is fixed at1\.01\.0across all models; we do not override top\-pp, top\-kk, or frequency / presence penalties\. The full inference scripts \(auth\-key handling, retry / resume logic, code\-assisted tool wiring\) are released alongside this paper\.

Temperature\.The two frontier reasoning models, GPT\-5\.2 and Gemini\-2\.5\-Pro, do not expose a temperature control and run at a fixed provider default, so a temperature\-0 condition is not available for them\. Claude\-4\.5\-Sonnet and OSS\-120B do expose it, and for these two we re\-ran a 40\-instance subset of the hard\-notion generation task atn=10n=10, drawn equally from feasible and infeasible instances of each notion, at temperature 0\.

The results are essentially unchanged\. Overall accuracy on this subset is 0\.00 for Claude\-4\.5\-Sonnet at temperature 1\.0 and 0\.03 at temperature 0, and 0\.03 at both temperatures for OSS\-120B, and the rate at which each model correctly identifies an infeasible instance does not move between the two temperatures\. The undetermined preference queries behave the same way: on 60 RS\-incomparable bundle comparisons, both models abstain on none of them at either temperature, so the lexicographic default is deterministic as well\. Temperature is not what drives these failures, and they are not sampling noise\.

Table 5:Inference settings for the four evaluated models\. “Max tokens” lists the per\-call output budget on the generation task and \(where it differs\) the selection task\. “Reasoning effort” is the provider\-side knob exposed by the OpenAI Responses API; the other three providers do not expose an analogue\.LabelProvider / APIModel identifierMax tokensTimeoutReasoning effortGPT\-5\.2OpenAI \(Responses API\)gpt\-5\.23030k \(gen\) 4040k \(sel\)2020minmedium \(concise summary\)Claude Sonnet 4\.5Anthropic \(Messages API\)claude\-sonnet\-4\-5\- 202509293030k \(gen\) 1515k \(sel\)2020min—Gemini 2\.5 ProGoogle \(google\.genai\)gemini\-2\.5\-proprovider defaultprovider default—GPT\-OSS 120BGroq \(chat\-completions\)openai/gpt\-oss\-120b2020k \(gen\) 1515k \(sel\)provider default—

## Appendix HAdditional Results: Preference Reasoning

This appendix provides the per\-model, per\-condition results underlying the findings about preference reasoning\. In each subsequent section, we present the accuracy of models on each task, and break down the assumptions they make leading to determined responses in undetermined problems\.

### H\.1Additional Figures

Figure 7:The models’ accuracy degrades with increasing problem size in both determined and undetermined queries\.In Figure[7](https://arxiv.org/html/2608.18631#A8.F7), we show that as the preference profile size increases, the accuracy of models decrease significantly on determined queries\. For atomic and comparative queries, models remain almost perfect accuracy up to size 100, but begins to fail at size 200\. For aggregative query, the threshold is much lower as model errors increase significantly at size 100, presumably related to the increase of both number of agents and length of preference list leading to quadratic increase in the profile\. The effect of sizes on undetermined problems is less pronounced and model variations exist, reflecting their diverse behavior pattern, either affirming incomparability with greater confidence or becoming more prone towards assumptions as input complexity increases\. A breakdown of model performance on different tasks is provided in subsequent sections\.

Figure 8:Comparing LLMs’ performance with different prompting formats on determined preference queries, split by task type\. The most notable effect of format isOSS\-120Bon aggregative tasks\. While completely failing to perform accurate aggregation in free\-flow format, it selects the correct count in MCQ for a certain portion, yet still significantly trailing other 3 models
### H\.2Detailed results of reasoning over total\-order preference profiles

Atomic and comparative queriesTable[6](https://arxiv.org/html/2608.18631#A8.T6)reports atomic and comparative queries on strict and complete preferences, which have a determined answer\.

Accuracy on item/position queries are high up to n=100, but significantly decrease as preference profile hit n=200\. Rate of decline varies across 4 models\.

Accuracy on pairwise comparison and ranking also decreases\. Pairwise comparison is less affected than atomic query \(presumably due to relative rather than precise location required\), while the accuracy is lower in the ranking task, due to the accumulation of pairwise comparisons needed to provide the ranking of 4 items\.

Table 6:Accuracy on determined atomic and comparative queries, under free\-form prompt\.Item queryPosition queryComparisonRankingModel50100200501002005010020050100200Gemini\-2\.5\-P1\.000\.9670\.501\.001\.000\.701\.001\.000\.801\.000\.9670\.633OSS\-120B1\.001\.000\.681\.001\.000\.591\.001\.000\.831\.000\.9670\.45Claude\-4\.5\-S1\.000\.9670\.501\.001\.000\.731\.001\.000\.901\.001\.000\.80GPT\-5\.21\.000\.9670\.601\.001\.000\.6331\.001\.001\.001\.001\.000\.667Table[7](https://arxiv.org/html/2608.18631#A8.T7)reports accuracy on undetermined atomic and comparative queries based on strict and incomplete preferences\.

On atomic queries, Gemini most often fails to acknowledge indeterminacy\. It invokes assumptions that lead to a definite output, including assumed typographical error in query, and manual completion of the incomplete preference list, by filling the missing items in lexical order behind the listed ones\.

On comparative queries, when both items to be compared are not listed, models make error by choose one definite answer, using assumption such as lexical ordering\. This accumulates in the ranking task, where all models most often return a full ranking of 4 items, even when only a partial ranking can be determined, as 2 of the items are not listed in the preference profile\.

Table 7:Accuracy on undetermined atomic and comparison tasks, with "ff \+ if known" prompts\. Correct response is: for item query, “unknown” \(queried item absent from profile\); for position query, “unknown” \(queried position out of bounds\); for comparison, “unknown” \(both items not listed\); for ranking, return only the listed items\. A score of 0 indicates the model never gives the correct response\.Item queryPosition queryComparisonRankingModel50100200501002005010020050100200Gemini\-2\.5\-P0\.500\.300\.000\.630\.400\.230\.630\.500\.370\.170\.200\.00OSS\-120B1\.000\.930\.871\.001\.001\.001\.000\.570\.220\.000\.000\.00Claude\-4\.5\-S0\.870\.800\.931\.001\.000\.830\.700\.900\.470\.000\.000\.00GPT\-5\.21\.001\.001\.001\.001\.001\.000\.431\.001\.000\.000\.000\.00Aggregative queriesTable[8](https://arxiv.org/html/2608.18631#A8.T8)reports aggregation accuracy across the three preference types\. The parenthetical numbers under incomplete profiles give the fraction of*incorrect*responses that match the count where agents ranking the preferred item in question but not the other one are included \(an implicit and unwarranted disambiguation\)\. OSS\-120B fails entirely across all conditions; the other three models are reasonable atn=50n=50on strict\-and\-complete profiles but degrade sharply atn=100n=100and on tie\-containing profiles\. The mean absolute errors of the incorrect responses are shown in Table[9](https://arxiv.org/html/2608.18631#A8.T9)\. Errors for incomplete preferences are not calculated, since the errors are not only caused by counting, but also induced by assumption on preference over item not being listed\.

Table 8:Accuracy on the aggregative task\. For incomplete preferences, values in parentheses give the fraction of*incorrect*responses matching the assumption made above\.Strict \+ completeStrict \+ incompleteComplete \+ tiesModelSize 50Size 100Size 50Size 100Size 50Size 100Gemini\-2\.5\-P0\.900\.570\.10 \(0\.89\)0\.17 \(0\.52\)0\.700\.50OSS\-120B0\.000\.000\.00 \(—\)0\.00 \(—\)0\.000\.00Claude\-4\.5\-S0\.700\.130\.30 \(0\.43\)0\.23 \(0\.17\)0\.300\.10GPT\-5\.21\.000\.400\.40 \(0\.83\)0\.40 \(0\.33\)0\.800\.33Table 9:Mean absolute error of incorrect responses for the aggregation task\.Strict \+ completeComplete \+ tiesModelSize 50Size 100Size 50Size 100Gemini\-2\.5\-P1\.004\.541\.083\.93OSS\-120B4\.6027\.79\.6032\.5Claude\-4\.5\-S1\.802\.622\.653\.22GPT\-5\.20\.002\.831\.132\.69OSS\-120B on aggregation: a note on catastrophic failure\.OSS\-120B returns 0\.00 accuracy on aggregation across all preference types and both sizes\. Inspection of responses shows that the model returns counts that differ from the ground truth by large margins, rather than failing in a structured way\. We treat this as a per\-model anomaly and exclude OSS\-120B from finding\-level claims about aggregation that depend on the structured\-error pattern\.

### H\.3Special undetermined queries: detailed bundle comparison and top\-kkresults

Bundle comparison, all preference types and sizes\.Table[10](https://arxiv.org/html/2608.18631#A8.T10)gives the full per\-model breakdown of the lexicographic\-ordering finding\. The values in parentheses give the fraction of RS\-incomparable responses where the model applied lexicographic ordering by highest\-ranked element\. Across all twelve \(model×\\timespreference type\) cells, the lexicographic share is 80% or higher; the only deviation from pure lexicographic behaviour is Claude\-4\.5\-S, which occasionally uses the sum of item ranks instead, which can yield the opposite conclusion\.

Our results score an undetermined response correct only when it abstains\. A model that commits to an answer while naming the assumption behind it is arguably doing something different from one that commits silently, so it is worth asking how much of the gap survives if the former is credited too\. We sorted every RS\-incomparable response into four kinds: an explicit abstention, a completion whose lexicographic rule is stated as an assumption, a silent lexicographic completion, and a non\-lexicographic answer\.

Table[11](https://arxiv.org/html/2608.18631#A8.T11)reports the strict scoring \(abstention only\) against the lenient scoring \(abstention or a flagged assumption\)\. The lenient scoring raises accuracy by at most 0\.17, and every model stays far below its accuracy of roughly 1\.00 on the matched determined comparisons\. Flagged assumptions are rare, at most 0\.17 of responses, while silent lexicographic completion accounts for 0\.70 to 1\.00\. It is this silent completion, rather than flagging that goes uncredited, that the epistemic results measure\.

Additionally, we test the bundle comparison tasks on two more schemes\. Firstly, we increase the size of bundles to be compared\. We randomly generate one bundle, and substitute several items within it with both more preferred and less preferred items, this creates a pair of equal\-sized bundles that are RS\-incomparable\. Secondly, we create bundle pairs with unequal sizes\. We select a single item that ranked relatively highly to form a one\-item bundle, and then select multiple items less preferred to it to form the second bundle, with varying size up to half of the preference list \(over 20 items\)\. In both cases, models keep the lexicographic bias when asked to select the preferred bundle\. Results are in Table[12](https://arxiv.org/html/2608.18631#A8.T12)\.

Table 10:Bundle comparison accuracy \(n=50n=50\)\. For RS\-comparable pairs \(a definite answer exists\), accuracy is reported\. For RS\-incomparable pairs \(no determinate answer exists\), the main value is the fraction of responses that correctly select “can’t decide,” with the fraction applying lexicographic ordering by highest\-ranked element in parentheses\.Strict \+ completeStrict \+ incompleteComplete with tiesModelRS\-comp\.RS\-incomp\.RS\-comp\.RS\-incomp\.RS\-comp\.RS\-incomp\.Gemini\-2\.5\-P1\.000\.00 \(1\.00\)1\.000\.00 \(1\.00\)1\.000\.20 \(0\.80\)OSS\-120B1\.000\.00 \(1\.00\)0\.850\.00 \(1\.00\)1\.000\.00 \(1\.00\)Claude\-4\.5\-S1\.000\.00 \(0\.90\)1\.000\.00 \(0\.90\)1\.000\.10 \(0\.90\)GPT\-5\.21\.000\.17 \(0\.83\)1\.000\.07 \(0\.93\)1\.000\.10 \(0\.90\)Table 11:Bundle comparison scoring for RS\-incomparable pairs\. In the strict scoring, only “can’t decide” is accepted\. In the lenient scoring, returning a lexicographically preferred bundle while explicitly stating the rule as an “assumption” is allowedscoringGemini\-2\.5\-POSS\-120BClaude\-4\.5\-SGPT\-5\.2Abstention only \(strict\)0\.100\.000\.030\.17Plus flagged assumption \(lenient\)0\.230\.000\.200\.20Table 12:Additional results on RS\-incomparable bundles\. The main value is the fraction of responses that correctly indicate the comparison is undetermined \(“can’t decide”\), with the fraction using lexicographic ordering in parentheses\.modelincreased bundle sizeone vs manyGemini\-2\.5\-P0\.00 \(1\.00\)0\.00 \(1\.00\)OSS\-120B0\.00 \(1\.00\)0\.00 \(1\.00\)Claude\-4\.5\-S0\.00 \(0\.80\)0\.00 \(1\.00\)GPT\-5\.20\.00 \(1\.00\)0\.00 \(1\.00\)Top\-kkqueries \(complete preference with ties\): full prompt\-variant results\.A unique problem for preference with ties involves indeterminacy due to tie\-breaking\. We ask whether an item belongs to the top\-kkchoices of the agent\. The answer is determined, when exactlykkchoices can be uniquely selected from the preference list, or when the queried item is not within a tie\. Indeterminacy arises when the ”kkth” position lies within a tie, and the queried item is part of the tie, since there is no definitive way of identifying the “top\-kk” items to judge whether the agent belongs to them\. Table[13](https://arxiv.org/html/2608.18631#A8.T13)shows the way a top\-kkmembership question is asked changes both the answer the model gives and the listing behaviour underneath it\. Prompt 1 asks this directly with “yes / no / uncertain” as the available answers\. Prompt 2 instead asks the model to list the agent’s top\-kkitems without mentioningAA; correctness is then about whether the response breaks the tie to return onlykkitems, or returns the entire tie group\. Prompt 3 combines the two: first asks for the top\-kklist, then asks whetherAAbelongs, with only “yes / no” available\.

Table 13:Top\-kkselection task under preferences with ties\.kkis chosen so that thekkth position falls within a tie group, and itemAAis a member of that tie\. Prompt 1 directly asks whetherAAis in the top\-kk; Prompt 2 asks for the top\-kklist only; Prompt 3 asks for the list and then asks whetherAAbelongs\.Prompt 1Prompt 2Prompt 3Modeluncertainyes/nokeeps tiebreaks tieyesnoGemini\-2\.5\-P0\.000\.90/0\.100\.001\.001\.000\.00OSS\-120B0\.300\.70/0\.000\.100\.900\.900\.10Claude\-4\.5\-S0\.400\.60/0\.000\.500\.501\.000\.00GPT\-5\.20\.630\.37/0\.000\.600\.400\.900\.10Two contrasts in the table are worth surfacing\. First, the Prompt 1 “uncertain” column is the only place the data set offers a calibrated abstention rate when the response options include “uncertain”: Gemini never picks it \(consistent with its over\-commitment in other tasks\), whereas GPT\-5\.2 picks it 63% of the time\. Removing the uncertain option in Prompt 3 does not redistribute these uncertainties evenly between yes and no; almost all are absorbed into yes\. Second, the Prompt 2 “keeps tie” column shows a wide spread across models \(0% for Gemini, 60% for GPT\) when no specific item is mentioned, which then collapses to 90–100% across the board in Prompt 3 once a specific item is named\. Both contrasts point to the same underlying observation: surface phrasing reshapes the model’s response on a fixed underlying ambiguity\. Whether this should be read as a calibration failure \(the model has no stable answer to give\) or as a context\-sensitivity feature \(the model adapts to the apparent intent of the prompt\) depends on the deployment context; we report the data without taking a position\.

### H\.4Partial\-order pairwise comparison: detailed results

Partial\-order queries on comparable pairs\.Table[14](https://arxiv.org/html/2608.18631#A8.T14)reports the per\-model breakdown of accuracy on comparable partial\-order pairs along both complexity dimensions: edge count varied at fixed chain length 9, and chain length varied at fixed 150 edges\. Gemini\-2\.5\-P and Claude\-4\.5\-S handle long chains in dense graphs reliably; OSS\-120B and GPT\-5\.2 degrade in both dimensions, sometimes failing to find chains they had earlier identified at lower density\.

Table 14:Accuracy on comparable item pairs in partial orders \(n=100n=100items\)\. Left block: chain length fixed at 9, edge count varied\. Right block: edge count fixed at 150, chain length varied\.Chain length = 9Edges = 150Model50 edges80 edges150 edgeschain of 7chain of 5chain of 3Gemini\-2\.5\-P1\.001\.001\.001\.001\.001\.00OSS\-120B1\.001\.000\.230\.500\.731\.00Claude\-4\.5\-S1\.001\.001\.001\.001\.001\.00GPT\-5\.21\.000\.930\.170\.470\.801\.00Incomparable pairs: free\-flow vs\. MCQ across graph densities\.Table[15](https://arxiv.org/html/2608.18631#A8.T15)gives the per\-density performance of undetermined partial order queries\. The dominant pattern: GPT\-5\.2 and OSS\-120B acknowledge incomparability reliably even under free\-flow; Gemini\-2\.5\-P declines as density grows; Claude\-4\.5\-S almost never acknowledges incomparability under free\-flow, collapsing to 0% at 150 edges\. Switching to MCQ recovers near\-perfect accuracy across all four models\.

Table 15:Accuracy on incomparable item pairs in partial orders \(n=100n=100items\), across graph densities and prompt formats\.Free\-flowMCQModel50 edges80 edges150 edges50 edges80 edges150 edgesGemini\-2\.5\-P0\.800\.630\.501\.001\.001\.00OSS\-120B1\.001\.001\.001\.001\.001\.00Claude\-4\.5\-S0\.130\.070\.001\.001\.001\.00GPT\-5\.21\.000\.970\.971\.001\.001\.00When Claude\-4\.5\-S and Gemini\-2\.5\-P fail to acknowledge incomparability under free\-flow, inspection of the reasoning traces reveals consistent patterns: assuming the user has made a typographical error in specifying the input and constructing an artificial chain to make the items comparable; selecting the item that appears anywhere in the input when the other does not; and inferring preference from the relative number of items each one dominates or is dominated by\. These are structured assumptions of the same kind documented for bundle comparisons and aggregation\. A breakdown of the assumptions is listed in Table[16](https://arxiv.org/html/2608.18631#A8.T16)\.

Table 16:Distribution of assumptions that models make to give a definite answer to the unanswerable partial order comparison task under free\-flow prompt\.ModelGemini\-2\.5\-PClaude\-4\.5\-SDetermining via relative preference0\.300\.87Assuming typo in query or conditions0\.300\.00Acknowledging lack of chain yet still committing a choice0\.400\.13Comparable pairs under MCQ: the cost of an explicit “unknown” option\.Table[17](https://arxiv.org/html/2608.18631#A8.T17)reports the effect of MCQ prompt on determined partial order query, evaluated at chain length 9 with 150 edges over 100 nodes\. On these inputs a chain in the input determines the answer, so the correct response is to identify the preferred item rather than abstain\. Adding the MCQ “not enough information to decide” option leaves Gemini unaffected \(1\.00 in both formats\) but degrades the other three models\. Claude shows the largest drop, from 100% under free\-flow to 33% under MCQ; OSS and GPT decline further from already\-weak free\-flow baselines\. Together with Table[15](https://arxiv.org/html/2608.18631#A8.T15), the result is that the MCQ option moves models in opposite directions on the two question types: where Claude was over\-committing \(incomparable pairs\), it is pulled back toward abstention; where it was answering correctly \(comparable pairs\), it is pulled away from a definite answer\.

Discussion on the effect of prompt formatsThe determined partial order query is the only preference reasoning task where we observe the model falsely indicating indeterminacy for a determined task, potentially due to the complexity of partial order reasoning\. In reasoning with total order profiles, models almost always commit to a determined response, either correct or incorrect, even tending to commit when the problem is logically undetermined\. As we implement alternative prompt formats such as MCQ to them, the performance does not change significantly for most determined tasks \(Figure[8](https://arxiv.org/html/2608.18631#A8.F8)\), while free\-flow with "if\-known" prompt and MCQ lead the models to acknowledge indeterminacy more often overall in the undetermined tasks, as we demonstrated in the main text \(Figure[2](https://arxiv.org/html/2608.18631#S3.F2)\)\.

Table 17:Accuracy on comparable item pairs in partial\-order preferences \(n=100n=100items, 150 edges, target chain length 9\), under free\-flow and MCQ formats\.ModelFree\-flowMCQGemini\-2\.5\-P1\.001\.00OSS\-120B0\.230\.10Claude\-4\.5\-S1\.000\.33GPT\-5\.20\.170\.10Alternative partial\-order representation \(Format 2\)\.Table[18](https://arxiv.org/html/2608.18631#A8.T18)reports results on a query\-answer representation of partial orders, where each input data point specifies a subset of items and the most preferred item within that subset \(rather than a pairwise comparison\)\. This representation is informationally equivalent to a partial order but requires an inference step to recover the underlying pairwise structure\. The same qualitative pattern as Format 1 holds: free\-flow performance varies sharply across models, with Claude\-4\.5\-S collapsing on incomparable pairs; MCQ recovers near\-perfect accuracy across all models\. The replication across representations supports the MCQ\-recovers\-abstention pattern not being an artifact of the input format\.

Table 18:Accuracy on incomparable item pairs in partial\-order preferences using the query\-answer representation \(n=30n=30items\), across graph densities and formats\.Free\-flowMCQModel30 edges50 edges30 edges50 edgesGemini\-2\.5\-P0\.500\.201\.001\.00OSS\-120B1\.001\.001\.001\.00Claude\-4\.5\-S0\.200\.001\.001\.00GPT\-5\.21\.001\.001\.001\.00
### H\.5Alternative preference presentation: natural language rendering

To verify whether the model biases on undetermined queries are an artifact of the symbolic lists we use to represent preference profiles by default, we re\-ran the same queries under three levels of natural\-language rendering of the profile\. To make the task as easy as possible, each prompt was also cut down to the queried agent’s list alone, which is the only preference information the question needs\.

- •Level 1 is the original symbolic list, for example \["C9", "C33", …\] given for agent A38\.
- •Level 2 states the same ranking in words, for example "A38 most prefers C9, then C33, and so on"\.
- •Level 3 renders the items as real\-world objects and narrates a person choosing a meal, for example "They like pizza the most, then sushi, then …", with the question rewritten as "Which bundle does the person prefer between \{sushi, tiramisu\} and \{burgers, jambalaya\}?"\.

Alongside the bundle task we include an undetermined atomic query, asking about preference of an item absent from the preference list\.

We generated 60 undetermined bundle comparisons with the construction rule of[SectionF\.1](https://arxiv.org/html/2608.18631#A6.SS1), together with 60 matched determined comparisons in which one bundle clearly dominates, and ran both on GPT\-5\.2 and OSS\-120B\.

As shown in Table[19](https://arxiv.org/html/2608.18631#A8.T19), correct abstention on the bundle task is at or near 0\.00 at all three levels for both models, while the matched determined comparisons are answered correctly in every case\. The near\-zero abstention is therefore a genuine failure to recognize incomparability, not low ability on the task, and natural\-language rendering does not recover the correct “can’t decide”\.

What the models do recognize depends on the source of the indeterminacy\. They almost never flag that two bundles of ranked items are formally incomparable, but they flag an unknown answer far more often when the queried item was never ranked\. The natural\-language levels do not change either behaviour, so the lexicographic default is not an artifact of how the list is written\.

Table 19:Accuracy on undetermined problems, with different levels of natural language representation of preferences\. Level 1: original symbolic list \("A38": \["C9", …\]\)\. Level 2: same items, natural sentences\. Level 3: items replaced by real dishes, narrated as a person choosing a meal\. Each cell is the fraction of 60 responses that correctly indicate indeterminacy\. The last row is the matched determined control, where one bundle dominates and a definite answer exists\.TaskModelLevel 1Level 2Level 3RS\-incomparable bundleGPT\-5\.20\.000\.000\.00RS\-incomparable bundleOSS\-120B0\.000\.000\.02unranked itemGPT\-5\.20\.480\.500\.42unranked itemOSS\-120B0\.500\.530\.33determined bundle \(control\)both1\.001\.001\.00

## Appendix IAdditional Results: Algorithmic Reasoning over Preferences

### I\.1Performance Differs Across Solution Concepts

![Refer to caption](https://arxiv.org/html/2608.18631v1/all_both_strict_complete_4.png)Figure 9:Performance of LLMs in terms of achieving specific notions across all three domains under strict and complete preferences, for instance sizes Small and Modest\. Each cell is the fraction of instances where the model’s output satisfies the target notion\.As shown in[Figure9](https://arxiv.org/html/2608.18631#A9.F9), all models achieve higher and more consistent accuracy on notions computed by canonical algorithms \(core/TTC, PO/SD, stability/DA\) than on non\-canonical ones \(UW, EW, RM\)\. Atn=30n=30, most models continue to perform well on canonical notions, while accuracy on UW and RM falls sharply, approaching zero for all models except GPT\-5\.2\. EW occupies an intermediate position, with GPT\-5\.2 and Gemini\-2\.5\-P maintaining reasonable accuracy on house allocation but all models failing in stable matching\. The model hierarchy, unlike in[Section3](https://arxiv.org/html/2608.18631#S3), is consistent: GPT\-5\.2 performs best overall, Gemini\-2\.5\-P and OSS\-120B show mixed relative performance across domains and notions, and Claude\-4\.5\-S performs worst\.

### I\.2Robustness to Preference Structure

Performance is robust to incompleteness\.

Figure 10:Performance on house allocation under strict and complete vs\. strict and incomplete preferences\.For notions evaluated under both strict and incomplete preferences, performance does not decrease when preference lists are truncated \([Figure10](https://arxiv.org/html/2608.18631#A9.F10)\)\. In some cases it is marginally better, likely because shorter lists reduce the number of reasoning steps required\. Models also handle MCPO allocations \(a notion specific to the incomplete setting\) reasonably well, though with a sharper size\-induced decline than for the core\.101010When a max\-cardinality matching is infeasible, models consistently assign unranked items to agents rather than leaving them unmatched, revealing an implicit assumption that receiving any item is preferable to receiving none\.

Performance is robust to ties, when the same algorithm works\.

![Refer to caption](https://arxiv.org/html/2608.18631v1/abs_strict_vs_ties_thin_separators.png)Figure 11:Difference in LLMs’ performance in computing various types of solutions with strict preferences \(S\) and preferences having ties \(T\)\.The introduction of ties likewise does not significantly affect performance on notions whose underlying algorithm is unchanged relative to the strict setting, such as the weak core, UW, EW, and RM\. The one case where performance does drop is Pareto\-optimality in house allocation: TTC guarantees a PO outcome under strict preferences but not under ties, so models that correctly apply TTC continue to succeed on the core yet fail to achieve PO in the same instances\.

### I\.3Generation without a Specific Objective

Figure 12:Fraction of responses where LLMsintendto use the canonical algorithm \(hatched\) and where theyachievethe corresponding solution \(solid\), across domains and preference types, forn=10n=10andn=30n=30\.When asked to compute a solution without specifying a target notion, all models default to the canonical algorithm for the relevant domain across all preference types \([Figure12](https://arxiv.org/html/2608.18631#A9.F12)\)\. The gap between hatched and solid bars reveals that models often correctly identify the canonical algorithm yet fail to execute it, particularly atn=30n=30\.111111We identify the algorithm the model attempts to use, using the method described in[AppendixP](https://arxiv.org/html/2608.18631#A16)\.An exception arises in object allocation atn=10n=10, where some models attempt to compute a solution satisfying stronger notions such as UW rather than simply applying SD; this tendency largely disappears atn=30n=30, consistent with models falling back to the simpler SD procedure as more demanding computations exceed their reasoning budget\.

### I\.4Failures in Infeasibility Detection

Models rely on heuristic search, which fails at scale\.

Table 20:Hard notions: accuracy by model, notion, instance size, and treatment\. Each cell shows the fraction of correct responses\. ForErows, the value in brackets is the fraction where the model returned an invalid solution—i\.e\., a response that is neither a timeout nor a valid one\-to\-one allocation\. ForNErows with the\{\}instruction, a response is correct only if the model returned\{\}\. ForNErows without the instruction, a response is correct if it is neither a timeout nor a valid one\-to\-one allocation\. A superscript∗indicates that at least one response timed out and was counted as incorrect; timeout counts are given in the note below\.Claude\-4\.5\-SOSS\-120BGemini\-2\.5\-PGPT\-5\.2Notionnnwith \{\}without \{\}with \{\}without \{\}with \{\}without \{\}with \{\}without \{\}StrictCore10E0%10%3%3%17%17%100%77%NE0%0%0%0%3%0%80%20%30E0% \[3%\]0%0% \[17%\]0%0% \[3%\]3%10%7%NE0%0%13%0%0%0%0%0%StronglyStable10E0%7%23% \[67%\]37% \[20%\]70% \[10%\]90%97% \[3%\]90%∗NE0%0%87%63%70%0%63%∗73%∗30E0%0%0% \[97%\]0% \[27%\]0% \[7%\]0% \[7%\]23% \[40%\]∗40%∗NE0%0%97%23%7%7%57%∗30%∗SuperStable10E0% \[13%\]0%3% \[80%\]10% \[67%\]23% \[60%\]33%87% \[3%\]80%∗NE7%0%87%87%73%0%65%∗50%∗30E0% \[43%\]0%0% \[100%\]0% \[100%\]0% \[20%\]0%0% \[93%\]∗3%∗\[70%\]NE53%0%97%100%40%0%97%83%∗

Timeouts \(out of 30\)\.GPT\-5\.2 with\{\}:Strongly Stablen=10n\{=\}10,NE: 9; Strongly Stablen=30n\{=\}30,E: 3,NE: 4; Super Stablen=10n\{=\}10,E: 3,NE: 9; Super Stablen=30n\{=\}30,E: 1\.GPT\-5\.2 without\{\}:Strongly Stablen=10n\{=\}10,E: 2,NE: 7; Strongly Stablen=30n\{=\}30,E: 5,NE: 15; Super Stablen=10n\{=\}10,E: 6,NE: 15; Super Stablen=30n\{=\}30,E: 4,NE: 2\. All timeouts are counted as incorrect\.

Models largely fail to compute strict core, strong stability, and super stability even atn=10n=10\([Table20](https://arxiv.org/html/2608.18631#A9.T20)\), with performance declining further atn=30n=30\. Where models do succeed atn=10n=10, particularly GPT\-5\.2 and Gemini\-2\.5\-P, inspection of reasoning traces reveals that they rely on heuristic search rather than correct algorithms: they enumerate candidate solutions, verify blocking conditions case by case, or use variants of the correct algorithm that still require heuristic completion \(see Appendix[L](https://arxiv.org/html/2608.18631#A12)\)\. This strategy can succeed for small instances but fails systematically at larger ones, where the search space grows beyond the model’s effective reasoning capacity\.

Models cannot reliably detect infeasibility\.

The pattern on infeasible instances reveals two distinct failure modes\. The first is a*default\-to\-empty bias*: models that achieve high NE accuracy often do so by returning\{\}\\\{\\\}indiscriminately, as evidenced by the simultaneously high invalid\-solution rates \(bracket values\) on feasible instances\. The apparent NE accuracy for these models reflects a bias toward claiming infeasibility rather than genuine detection\. This bias is also sensitive to instance difficulty: some models that return\{\}\\\{\\\}rarely atn=10n=10return it far more often atn=30n=30, when the problem is large enough that the model appears to abandon computation\.

The second failure mode is*prompt\-contingent infeasibility detection*: removing the\{\}\\\{\\\}escape hatch causes NE accuracy to collapse for most models, confirming that their detection depends on the prompt providing an explicit mechanism to express it rather than on genuine reasoning\. GPT\-5\.2 is more robust to this change, though even its NE accuracy degrades atn=30n=30\.

The tendency to claim infeasibility also varies by notion in a consistent ordering across all models: nearly no model returns\{\}\\\{\\\}for the strict core, while high rates are common for strong and super stability\. Atn=10n=10, GPT\-5\.2 largely escapes this pattern because it can genuinely solve these problems; atn=30n=30, where it can no longer do so, its NE rates follow the same difficulty\-ordered pattern as the other models\. This suggests that the propensity to declare infeasibility is driven by perceived problem difficulty rather than correct reasoning about whether a solution exists\.

Overall, infeasibility detection that disappears without an explicit escape hatch, NE accuracy dominated by a default\-to\-empty bias, and a notion ordering tracking difficulty rather than logic all indicate that models lack reliable knowledge of these harder notions and adapt their outputs to whatever the prompt makes available\.

Models cannot reliably identify infeasibility when selecting\.

Figure 13:Selection outcomes for harder notions \(strict core, strong and super stability\), separated by whether a solution exists \(E/NE\) and whether a “None of the Above” \(NOTA\) option was included, atn=10n=10andn=30n=30\.We additionally ask models to identify a specific notion among a set of candidates, a task that should be easier than generation since it only requires solution*verification*rather than executing an algorithm to arrive at a solution\. As shown in[Figure13](https://arxiv.org/html/2608.18631#A9.F13), even this task proves difficult: models frequently select incorrect candidates when a correct option exists\. When NOTA is available, models use it in poorly calibrated ways\. Notably, when no correct option is present, models tend to select whichever candidate satisfies a weaker version of the target notion, such as weak core instead of strict core or a weakly stable matching instead of a strongly stable one\. This connects directly to the pattern observed above: the bias toward weaker notions in preference selection translates into a specific type of error when the target notion does not exist\. While GPT\-5\.2 significantly outperforms other LLMs when the intended solution exists, its performance drops significantly when the solution does not exist \- especially on larger instances, or when the NOTA option is not provided\.

### I\.5Selecting from Options

Figure 14:Share of selections for each solution concept across models, domains, and preference types, atn=10n=10andn=30n=30\. The number on top of each bar represents the percentage of responses where theintendednotion matches theactualnotion, i\.e\. that satisfied by the selected option\.##### Models reveal systematic preference biases when selecting from candidates\.

When presented with a candidate set and asked for their most preferred solution, models reveal preferences that diverge from their generation behaviour \([Figure14](https://arxiv.org/html/2608.18631#A9.F14)\)\. In allocation domains, models select utilitarian welfare\-maximising outcomes far more often than canonical solutions, contrary to their default behaviour in generation\. This recovers and extends the utilitarian bias while generating allocations of resources or tasks observed in previous work\[[32](https://arxiv.org/html/2608.18631#bib.bib15),[69](https://arxiv.org/html/2608.18631#bib.bib37),[20](https://arxiv.org/html/2608.18631#bib.bib8)\], showing that it also surfaces in selection and with a wider set of solution concepts\. In stable matching, models favor weakly stable solutions even when stronger options are present\.

##### Intention\-action Gap\.

[Figure14](https://arxiv.org/html/2608.18631#A9.F14)shows that models often end up selecting a solution that satisfies a property different from the one intended\.121212The notion a model “intended” to satisfy is identified using an LLM judge \(Gemini\-2\.5\-Flash\); the judge prompt is provided in Appendix[P](https://arxiv.org/html/2608.18631#A16)\.This divide is higher under incomplete and tied preferences than under strict and complete preferences\. In the incomplete setting, models tend to prioritize max\-cardinality outcomes regardless of the notion they express an intent to target\.131313This is the one cell where the judges disagree, so we report it as judge\-sensitive rather than pooling it \([SectionP\.3](https://arxiv.org/html/2608.18631#A16.SS3)\)\.Under preferences with ties, models frequently fail to distinguish between weaker and stronger versions of the same notion, for instance selecting a weakly stable matching when a strongly stable one is among the options\.141414From an analysis of the reasoning traces, it is clear that models use the absence of \(weak\) blocking pairs as the primary criterion to evaluate matchings, and compare all matchings that are at least weakly stable in terms of other metrics such as welfare or Pareto\-improvements\.

## Appendix JStatistical analysis of quantitative results

We compute 95% confidence intervals for each individual experiment, and paired tests for comparisons between problems, models and formats\. Intervals are Wilson intervals for a binomial proportion\. Paired comparisons on the same instances use McNemar’s test, and comparisons across instance sizes use Fisher’s exact test\. Every analysis in this appendix runs on the responses already collected, so no additional model queries were needed\. Because each prompt is scored from a single draw, these intervals are the statement of uncertainty over instances;[AppendixG](https://arxiv.org/html/2608.18631#A7)separately shows the results are unchanged at temperature 0 for the two models that expose it\.

### J\.1Indeterminacy gap of preference reasoning tasks

For bundle comparison and ranking tasks, the determined\-vs\-undetermined gap \([Figure2](https://arxiv.org/html/2608.18631#S3.F2)\(a\)\) is robust, with determined queries having accuracy near 1 and undetermined queries at near 0\. The confidence intervals do not overlap for every task and model\. These are the cases where recognizing indeterminacy requires reasoning\. On bundle comparison \([Table10](https://arxiv.org/html/2608.18631#A8.T10)\), determined accuracy is 1\.00 in eleven of the twelve \(model×\\timespreference type\) cells and 0\.85 in the twelfth, while undetermined accuracy never exceeds 0\.20\.

The gap does not have this shape everywhere, and where it does not is informative\. On atomic and aggregative queries the intervals overlap and the gap is model\-dependent, since an unranked item is missing by inspection and recognizing it needs no reasoning step\. On partial\-order queries the pattern is mixed and in two cases reversed\. At 150 edges \([Tables14](https://arxiv.org/html/2608.18631#A8.T14)and[15](https://arxiv.org/html/2608.18631#A8.T15)\), Claude\-4\.5\-S scores 1\.00 on determined pairs against 0\.00 on undetermined ones and Gemini\-2\.5\-P 1\.00 against 0\.50, whereas GPT\-5\.2 scores 0\.17 against 0\.97 and OSS\-120B 0\.23 against 1\.00, because producing a determinate answer on a determined input is itself hard at this graph density \([SectionH\.4](https://arxiv.org/html/2608.18631#A8.SS4)\)\. We therefore state the indeterminacy gap for the comparative tasks where it is clean, and report the other families per cell\.

### J\.2Model differences on hard notions of algorithmic reasoning

For the hard notion problems in[Table20](https://arxiv.org/html/2608.18631#A9.T20), the model differences are significant, with all six pairwise comparisons havingp≤0\.004p\\leq 0\.004on the McNemar’s test\. GPT\-5\.2 is the only model with non\-trivial accuracy on the matched feasible instances\. Table[21](https://arxiv.org/html/2608.18631#A10.T21)reports the per\-pair values\.

Table 21:Hard\-notion generation: pairwise McNemar tests over 360 paired instances\. Per\-model accuracies are given in[Table20](https://arxiv.org/html/2608.18631#A9.T20)\.PairppGPT\-5\.2 vs\. Gemini\-2\.5\-P<0\.001<0\.001GPT\-5\.2 vs\. Claude\-4\.5\-S<0\.001<0\.001GPT\-5\.2 vs\. OSS\-120B<0\.001<0\.001Gemini\-2\.5\-P vs\. Claude\-4\.5\-S<0\.001<0\.001Gemini\-2\.5\-P vs\. OSS\-120B<0\.001<0\.001Claude\-4\.5\-S vs\. OSS\-120B0\.0040\.004
### J\.3Scaling of input size on generation tasks

For the comparison of accuracy on small and modest market sizes in[Figure4\(a\)](https://arxiv.org/html/2608.18631#S4.F4.sf1)\(a\), a majority of comparisons are significant under Fisher’s exact test, in 32 of 53 cells\. The significance holds for models that achieve at least some level of performance on the small market, with room to decline on the modest market size\.

### J\.4Format effect on undetermined preference queries

For the comparison of different formats on undetermined preference queries in[Figure2](https://arxiv.org/html/2608.18631#S3.F2), the comparison is significant on approximately half of the cases, and the effect is strongly task\-dependent \(Table[22](https://arxiv.org/html/2608.18631#A10.T22)\), which is why we report it per cell rather than as a single average\.

Table 22:Format effect \(free\-flow vs\. MCQ\) on undetermined preference queries: cells with non\-overlapping 95% intervals\.ModelSignificant cellsGemini\-2\.5\-P11 of 20GPT\-5\.210 of 20Claude\-4\.5\-S10 of 19OSS\-120B8 of 20
### J\.5Influence of "NOTA" option on hard selection problems

The effect of the provided option in[Figure13](https://arxiv.org/html/2608.18631#A9.F13)is significant and one\-sided\. No model selects NOTA when a solution exists, and on infeasible instances models under\-select it \(Table[23](https://arxiv.org/html/2608.18631#A10.T23)\)\. Offering the option therefore does not induce spurious abstention here; the error is a failure to abstain when abstention is correct\.

Table 23:Selection with a “none of the above” option: fraction of instances on which the model selects NOTA\.ModelFeasible \(NOTA is wrong\)Infeasible \(NOTA is correct\)GPT\-5\.20\.000\.61Gemini\-2\.5\-P0\.000\.59OSS\-120B0\.000\.56Claude\-4\.5\-S0\.000\.03

## Appendix KPrompt Templates

### K\.1Preference reasoning tasks\.

All preference\-reasoning prompts share a common template:

> You are an intelligent agent who is an expert in algorithms\. Consider the following instance of the object allocation problem, where\[n\]alternatives have to be allocated to\[n\]agents\. Given below are the preferences agents have over the alternatives\. <preferences\> \[preferences\_json\] </preferences\> \[task\_string\] \[format\_string\]

Task strings and format strings for each query type are listed in Table[24](https://arxiv.org/html/2608.18631#A11.T24)\. In addition to the base free\-flow prompt, for undetermined queries, additional wording is appended to permit an “unknown” or “can’t decide” response\. We refer to this as free\-flow \+ “if known”\. Additionally, for each problem we design MCQ \(multiple\-choice problem\) prompts for each task, with the option being potential answers, plus an option of "There is insufficient information to decide\."

Table 24:Preference reasoning prompts: task and formatting instructions\. The base free\-flow prompt is shown, while the wordings initalicsare added for free\-flow \+ "if known" format\.Task stringFormat stringWhat position is \[choice\] at in \[agent\]’s preference list?Return<answer\>X</answer\>, where X is the number indicating the position,if known\.What is \[agent\]’s \[k\]th most preferred choice?Return<answer\>X</answer\>, where X is the name of the choice,if known\.Which alternative does \[agent\] prefer between \[choice 1\] and \[choice 2\]?Return<answer\>X</answer\>, where X is the name of the choice,if known\.Rank \[4 choices\] according to \[agent\]’s preference\.Return the solution in the following format: <answer\>ranking</answer\>, withonly rankedchoice names in descending order connected by ’\>’ sign\.How many agents prefer \[choice 1\] over \[choice 2\]?Return <answer\>X</answer\>, where X is the number of agents\.Which bundle does \[agent\] prefer between \{\[choice 1\], \[choice 2\]\} and \{\[choice 3\], \[choice 4\]\}?Return the solution in the following format: <answer\>\{A, B\}</answer\>, where \{A, B\} is the preferred bundle\.If there is no preference, return <answer\>Can’t decide</answer\>\.If \[agent\] selects its top\-\[k\] alternatives, does \[choice\] belong to this list?Return <answer\>solution</answer\>with solution being yes, noor uncertain\.What are the top\-\[k\] choices of \[agent\]?Return <answer\>solution</answer\>with choice names in a list format\.Select the top\-\[k\] choices of \[agent\]\. Does \[choice\] belong to this list?Return the solution in the following format: <answer\>solution</answer\>\.\(Partial order\) Between \[choice 1\] and \[choice 2\], which is preferred,if known?Return the answer in a single word in the following format: <answer\>word</answer\>\.
### K\.2Algorithmic reasoning tasks\.

##### Generation tasks\.

> You are an intelligent agent who is an expert in algorithms\. Consider the following instance of the\[domain\]problem, where\[n\]alternatives have to be allocated to\[n\]agents\. Given below are the preferences agents have over the alternatives\. <preferences\> \[preferences\_json\] </preferences\> <endowment\>\(Shapley\-Scarf market only\) \[endowment\_json\] </endowment\> Your task is to compute a\[notion\]allocation for the given preferences\. \[notion\_definition\] Return the solution in the following format: <answer\>\{"A1": "assigned alternative", …\}</answer\> If there is no\[notion\]solution, return <answer\>\{\}</answer\>\.

##### Selection tasks\.

> You are an intelligent agent who is an expert in algorithms\. Consider the following instance of the\[domain\]problem, where\[n\]alternatives have to be allocated to\[n\]agents\. Given below are the preferences agents have over the alternatives\. <preferences\> \[preferences\_json\] </preferences\> <endowment\>\(Shapley\-Scarf market only\) \[endowment\_json\] </endowment\> Your task is to select the\[notion\]allocation among the given options: A:\[allocation\_json\] B:\[allocation\_json\] … \[K\]: None of the above\(NOTA condition only\) \[notion\_definition\] Return only the letter of your chosen option inside <answer\> </answer\> tags, e\.g\., <answer\>A</answer\>\.

##### Preference encoding\.

Preferences are passed to the model as JSON, with one entry per agent listing alternatives in decreasing order of preference\. In Shapley\-Scarf market tasks, the preferences are one\-sided \(agents over objects\) and the endowment block lists each agent’s initial holding\.

> <preferences\> \{ "A1": \["O3", "O1", "O2"\], "A2": \["O1", "O2", "O3"\], "A3": \["O2", "O3", "O1"\] \} </preferences\> <endowment\> \{"A1": "O1", "A2": "O2", "A3": "O3"\} </endowment\>

In matching market tasks, preferences are two\-sided: each side has its own preference dictionary over the other side, and no endowment block is included\.

> <preferences\> \{ "A": \{ "A1": \["B2", "B1", "B3"\], "A2": \["B1", "B3", "B2"\], "A3": \["B3", "B2", "B1"\] \}, "B": \{ "B1": \["A2", "A1", "A3"\], "B2": \["A1", "A3", "A2"\], "B3": \["A3", "A2", "A1"\] \} \} </preferences\>

When preferences include ties, items at the same indifference level are grouped in nested lists, e\.g\.\["O1", \["O2", "O3"\], "O4"\]representsO1≻\{O2∼O3\}≻O4O\_\{1\}\\succ\\\{O\_\{2\}\\sim O\_\{3\}\\\}\\succ O\_\{4\}\. Incomplete preferences omit the unranked alternatives entirely\.

Here’s a draft paragraph for the generation\-prompt subsection:

##### Reasoning trace elicitation\.

GPT\-5\.2 and OSS\-120B do not expose their internal reasoning traces by default, unlike Gemini\-2\.5\-Pro and Claude\-4\.5\-Sonnet, which return a visible chain\-of\-thought alongside the final answer\. To enable an analysis of the strategies being used by these models to solve the given problems, we append the following instruction to the prompt for these two models:

> Briefly explain your approach within <scratchpad\> </scratchpad\> tags after providing the answer in the above format\.

This instruction is appended after the answer\-format specification after the conditional \{\} instruction if included, and otherwise after the answer format instruction\.

##### Notion Definitions Used in Prompts

Tables[25](https://arxiv.org/html/2608.18631#A11.T25)and[26](https://arxiv.org/html/2608.18631#A11.T26)list the exact definitions included verbatim in generation prompts for each solution concept\. Definitions were held constant across all models and instance sizes\.

Table 25:Definitions provided to models for Shapley\-Scarf market and house allocation tasks\. The prompts label this notioncoreunder strict preferences andweak coreunder ties\. Both labels carry the same blocking condition, because the two notions coincide, so we merge the rows here\. The refinement that genuinely differs is the strict core, which blocks when every member of a coalition weakly improves and at least one improves strictly\.NotionDefinitionPareto\-optimalAn allocation is Pareto\-optimal if there is no other feasible allocation that makes at least one agent strictly better off without making any other agent worse off\.MCPOA max\-cardinality Pareto\-optimal \(MCPO\) allocation matches as many agents as possible to alternatives they rank, and among all such maximum\-size matchings it is Pareto\-optimal \(no Pareto\-improving reassignment exists\)\.Core \(weak core\)An allocation is in the core if there is no coalition of agents that can reshuffle their initially endowed houses among themselves so that every coalition member is strictly better off than in the allocation\.Strict coreAn allocation is in the strict core if there is no blocking coalition that can reshuffle endowed houses so that every member weakly improves and at least one member strictly improves\.UW\-maximizingA utilitarian welfare\-maximizing allocation minimizes the total sum of agents’ assigned ranks \(equivalently, maximizes total ordinal utility\)\.EW\-maximizingAn egalitarian welfare\-maximizing allocation minimizes the worst \(largest\) rank any agent receives \(i\.e\., it optimizes the welfare of the worst\-off agent\)\.Rank\-maximalA rank\-maximal allocation maximizes the number of agents receiving a 1st\-choice alternative; subject to that, it maximizes the number receiving a 2nd\-choice; and so on \(lexicographic maximization of the rank\-count vector\)\.Table 26:Definitions provided to models for matching market tasks\.NotionDefinitionWeakly stableA matching is weakly stable if there is no blocking pair where both agents strictly prefer each other to their current partners; ties do not create blocking unless both sides strictly gain\.Strongly stableA matching is strongly stable if there is no blocking pair where both agents weakly prefer each other to their current partners and at least one agent strictly prefers the other\.Super stableA matching is super stable if there is no blocking pair where both agents weakly prefer each other to their current partners; even indifference on both sides can block\.UW\-maximizingA utilitarian welfare\-maximizing matching minimizes the sum of \(ordinal\) partner ranks\.EW\-maximizingAn egalitarian welfare\-maximizing matching minimizes the maximum \(worst\) assigned partner rank\.Rank\-maximalA rank\-maximal matching lexicographically maximizes the rank\-count vector: as many agents as possible get a 1st\-choice partner; subject to that, as many as possible get a 2nd\-choice; and so on\.

## Appendix LReasoning Strategies on Feasible and Infeasible Tasks \(GPT\-5\.2\)

We restrict the qualitative analysis in this appendix to GPT\-5\.2\. Among the four frontier models we evaluated \(Claude Sonnet 4\.5, Gemini 2\.5 Pro, GPT\-OSS 120B, and GPT\-5\.2\), GPT\-5\.2 is the only model to achieve non\-trivial correctness on the three solution concepts that admit both feasible and infeasible instances: the strict core of a Shapley–Scarf housing market, strongly stable matching, and super stable matching\. On the feasible instances of Small size, GPT\-5\.2’s correctness rates are100%100\\%,97%97\\%and87%87\\%respectively, against runner\-up rates of17%17\\%,70%70\\%and23%23\\%for Gemini 2\.5 Pro and at most23%23\\%for the other two models\. Other models do return correct non\-existence claims on the infeasible instances, but they do so mainly by abstaining broadly, since their accuracy on the matched feasible instances is close to zero\. GPT\-5\.2 is the only model that gets both sides right\. We therefore focus on what GPT\-5\.2 actually does and how those reasoning strategies behave as the problem size grows fromn=10n=10\(Small\) ton=30n=30\(Modest\)\.

The analysis below is built on GPT\-5\.2’s own self\-reports of its reasoning\. Every prompt in our benchmark closes with the instruction*“Briefly explain your approach within<scratchpad\> </scratchpad\>tags after providing the answer in the above format”*, and the scratchpads it produces are the input to the qualitative coding here\. To process them at scale, we combine two views: a deterministic verifier that replays canonical algorithms \(Top Trading Cycles with first\-in\-list tie\-breaking, Irving’s strongly\-stable and super\-stable matching algorithms, and a polynomial\-time strict\-core check via blocking\-cycle search on the weakly\-preferred\-endowment digraph\) on each model output, and an LLM\-judge \(DeepSeek V4 Pro\) that extracts six verbatim features per scratchpad: the named algorithm, any explicit trading cycle of length≥3\\geq 3, any pre\-algorithm forced\-pair derivations, the stated tie\-break rule, the verification step \(re\-checks vs\. property\-citation vs\. none\), and the final claim \(allocation/matching produced vs\. no\-solution claim\)\. The exact judge setup, including a representative prompt, is given in Section[L\.4](https://arxiv.org/html/2608.18631#A12.SS4)\.

The data underlying every percentage in this appendix is 720 GPT\-5\.2 trajectories on the generation task,120120per\(notion,feasibility\)\(\\textit\{notion\},\\textit\{feasibility\}\)cell, evenly split between Small and Modest sizes\. Within each\(cell,size\)\(\\text\{cell\},\\text\{size\}\)pair the dataset contains3030instances, with two trajectories per instance drawn from two prompt variants\. The first variant, used for the cross\-model evaluation elsewhere in the paper, explicitly instructs the model that “if no \[strict core / strongly stable / super stable\] solution exists, return<answer\>\{\}</answer\>”; we will refer to it as the*empty\-hint*prompt\. The second variant omits this instruction and is otherwise identical; we will refer to it as the*no\-hint*prompt\. The two variants produce strongly divergent behaviour on infeasible cells, where under the no\-hint prompt GPT\-5\.2*never*returns an explicit no\-solution answer on any of the180180infeasible\-cell trajectories issued under that variant, so we split per\-cell statistics by prompt variant whenever the difference matters\.

### L\.1Strict core in Shapley–Scarf housing markets

##### Feasible instances\.

On feasible strict\-core instances, GPT\-5\.2 invariably runs Top Trading Cycles \(TTC\)\. What varies is the tie\-break rule, and on this dataset the rule chosen determines correctness almost entirely\. The successful pattern is what we call the*constructive chain heuristic*: at each indifference, the model picks the tied alternative that allows a long trading cycle to close, rather than the lexicographically first tied alternative\. The choice is occasionally verbalised, as in this Small\-size trace:

> Approach: 1\) Compute a core candidate via Top Trading Cycles \(TTC\) adapted to ties by selecting one “top” house per agent when indifferent\. Running TTC on the endowment graph and choosingA7A\_\{7\}’s top pointer asC4C\_\{4\}\(rather than keepingC10C\_\{10\}\) yields the allocation above\. 2\) Verify the strict\-core condition by searching for a blocking coalition: any blocking reshuffle decomposes into trading cycles, so it suffices to check whether there is a directed cycle of agentsi1→i2→⋯→ik→i1i\_\{1\}\\to i\_\{2\}\\to\\cdots\\to i\_\{k\}\\to i\_\{1\}in which eachiti\_\{t\}weakly prefers the endowment ofit\+1i\_\{t\+1\}to its assigned house and at least one strictly prefers it\. Building this digraph for the allocation above yields no such cycle, hence no blocking coalition exists\.

We label a trajectory as constructive\-chain if the model’s allocation differs from canonical first\-in\-list TTC*and*lies in the strict core \(the verifier produces the canonical TTC output for each instance\)\. At Small size,3030of6060trajectories \(50%50\\%\) are constructive\-chain, and2929of those3030\(97%97\\%\) land in the strict core\. A residual non\-mechanical bucket \(“arbitrarily but consistently” chosen ties, in the model’s own words\) accounts for another2626trajectories of which2424\(92%92\\%\) are also in the core\. The empty\-hint clause provides a small lift:30/3030/30correct under the empty\-hint prompt versus23/3023/30\(77%77\\%\) under the no\-hint prompt\.

At Modest size the picture inverts\. The constructive\-chain stratum collapses to22of6060\(3%3\\%\), neither correct;3030of6060trajectories \(50%50\\%\) match canonical first\-in\-list TTC exactly, none of which is in the strict core; the residual non\-mechanical bucket falls to55correct of2828\(18%18\\%\)\. GPT\-5\.2 abandons the constructive heuristic in favour of a mechanical rule that the TTC theorem does not justify under weak preferences, and that empirically never recovers the strict core on these instances\.

##### Infeasible instances\.

On infeasible instances, the only correct strategy is to argue that no allocation can satisfy the strict\-core condition\. GPT\-5\.2 does this via what we call*iterative mandatory\-pair enumeration*: a sequence of forced assignments, each justified by exhibiting a coalition that would block any allocation violating it, terminating in a contradiction\. A representative trace:

> Approach: show non\-existence by exhibiting a blocking coalition for every possible allocation\. If an allocationxxgivesA8A\_\{8\}anything other thanC2C\_\{2\}, then coalition\{A8,A5,A9,A10\}\\\{A\_\{8\},A\_\{5\},A\_\{9\},A\_\{10\}\\\}blocksxxviaA8←C2A\_\{8\}\\\!\\leftarrow\\\!C\_\{2\}\(top choice, strict improvement\),A5←C5A\_\{5\}\\\!\\leftarrow\\\!C\_\{5\},A9←C1A\_\{9\}\\\!\\leftarrow\\\!C\_\{1\},A10←C7A\_\{10\}\\\!\\leftarrow\\\!C\_\{7\}\(each weakly improves\)\. So any strict\-core allocation must assignC2C\_\{2\}toA8A\_\{8\}\. If an allocation givesA4A\_\{4\}anything other thanC2C\_\{2\}, coalition\{A4,A5,A9\}\\\{A\_\{4\},A\_\{5\},A\_\{9\}\\\}blocks similarly, so any strict\-core allocation must also assignC2C\_\{2\}toA4A\_\{4\}\. ButC2C\_\{2\}is a single house, so the strict core is empty\.

Whether the model produces this argument at all is controlled almost entirely by the prompt variant\. At Small size under the empty\-hint prompt,2424of3030trajectories \(80%80\\%\) explicitly claim no allocation exists, and all2424are correct; under the no\-hint prompt,00of3030\. The mandatory\-pair argument is in the model’s repertoire, but it surfaces only when the prompt explicitly mentions the empty\-answer option\. At Modest size, the empty\-hint prompt no longer suffices:00of3030trajectories under either variant claim non\-existence\. The forced\-pair chains required atn=30n=30are longer and the blocking coalitions larger, and even with explicit permission to return\{\}\\\{\\\}, the model commits to producing an allocation rather than working through the chain\.

### L\.2Strongly stable matchings

##### Feasible instances\.

The strongly\-stable task is set on a bipartite instance with two sides of agents, denotedAAandBB\. On feasible instances, GPT\-5\.2 pairs deferred acceptance with hand\-coded local repair: it first identifies one or two forced pairs from the preference structure \(for instance, an\(Ai,Bj\)\(A\_\{i\},B\_\{j\}\)where each side is the unique top choice of the other\), runs A\-proposing deferred acceptance on a tie\-refinement to populate the matching, scans the result for strong\-blocking pairs created by the indifferences that the tie\-refinement collapsed, and applies short local swaps until none remain\. A representative trace:

> Approach \(strong stability with ties\): I first constructed a complete matching via an A\-proposing deferred\-acceptance run \(breaking ties arbitrarily just to get a candidate\), then explicitly checked the strong\-stability condition\. The initial DA matching was not strongly stable:B5B\_\{5\}ranksA4A\_\{4\}as its unique top choice, whileA4A\_\{4\}ranksB5B\_\{5\}in its 2nd tier \(tied withB6B\_\{6\}\)\. IfA4A\_\{4\}is not matched toB5B\_\{5\}and not to its strictly\-better optionB8B\_\{8\}, then\(A4,B5\)\(A\_\{4\},B\_\{5\}\)is a strong blocking pair\. This forcesA4−B5A\_\{4\}\-B\_\{5\}\. After enforcingA4−B5A\_\{4\}\-B\_\{5\}, I iteratively repaired the matching to remove remaining strong blocking pairs caused by indifferences\. The final matching is strongly stable\.

At Small size,4545of6060trajectories \(75%75\\%\) produce a strongly stable matching and1111more produce a super\-stable matching \(which strictly implies strong stability\), for a combined56/6056/60\(93%93\\%\)\. Pre\-algorithm forced\-pair reasoning is the most reliable distinguishing feature of correct trajectories\.

The approach itself does not change at Modest size, but its execution quality does\. Strong stability is met by15/6015/60\(25%25\\%\) and super\-stability by4/604/60, for a combined19/6019/60\(32%32\\%\);2525trajectories \(42%42\\%\) produce no parseable matching, and1313produce a matching that is not even weakly stable\. The local repair loop is the bottleneck: as the matching grows, every swap to fix one strong\-blocking pair tends to introduce another\. Notably, the empty\-hint clause*hurts*on this cell at Modest size:7/307/30\(23%23\\%\) correct under the empty\-hint prompt versus12/3012/30\(40%40\\%\) under the no\-hint prompt\. The most plausible reading is that the explicit\{\}\\\{\\\}option, when offered on a feasible instance the model is struggling to solve at scale, occasionally tempts it to retreat to the empty answer rather than persist with the local\-repair loop\.

##### Infeasible instances\.

On infeasible strongly\-stable instances, GPT\-5\.2 produces the matching\-theoretic analogue of the mandatory\-pair impossibility chain, again starting from a forced pair \(typically a mutual top tie\) and deriving subsequent forced assignments that culminate in an unavoidable strong\-blocking pair:

> Approach \(proof of non\-existence by forced blocking pairs\)\.A5A\_\{5\}has a top tie\{B4,B6\}\\\{B\_\{4\},B\_\{6\}\\\}\. IfA5A\_\{5\}is matched toB6B\_\{6\}, then\(A5,B4\)\(A\_\{5\},B\_\{4\}\)blocks:A5A\_\{5\}weakly prefersB4B\_\{4\}toB6B\_\{6\}\(indifferent\), andB4B\_\{4\}ranksA5A\_\{5\}in its top tie \(withA2A\_\{2\}\), soB4B\_\{4\}weakly prefersA5A\_\{5\}to any partner\. To avoid this,B4B\_\{4\}must be matched toA2A\_\{2\}\. But then\(A2,B2\)\(A\_\{2\},B\_\{2\}\)blocks:A2A\_\{2\}strictly prefersB2B\_\{2\}toB4B\_\{4\}, andB2B\_\{2\}ranksA2A\_\{2\}as its top choice\. ThereforeA5A\_\{5\}cannot be matched toB6B\_\{6\}\. … Each branch leads to an unavoidable strong\-blocking pair, so no strongly stable matching exists\.

As with the strict\-core infeasible cell, the rate at which the model produces this argument is controlled by the prompt variant\. Under the empty\-hint prompt:19/3019/30\(63%63\\%\) at Small and17/3017/30\(57%57\\%\) at Modest\. Under the no\-hint prompt:0/300/30at each size\. Across all3636traces that produce an impossibility argument, every single one is correct; the forced\-pair chain is reliable enough that whenever the model commits to it, the conclusion is right\. The size behaviour of the empty\-hint trajectories is also notable: the rate is essentially size\-invariant \(63%→57%63\\%\\to 57\\%\), in contrast to the feasible cell of this same notion \(where Modest correctness drops from93%93\\%to32%32\\%\)\.

### L\.3Super stable matchings

##### Feasible instances\.

On feasible super\-stable instances, GPT\-5\.2 names the Irving–Manlove super\-stable matching algorithm \(often as “Irving SUPER” or “the standard super\-stable SMTI reduction”\) and at Small size applies it convincingly:

> Approach: I applied the standard super\-stable SMTI reduction procedure \(Irving–Manlove style\): repeatedly let freeAA\-agents propose to everyone in their current first \(possibly\-tied\) tier; eachBB\-agent keeps the best \(possibly\-tied\) proposers seen so far and deletes from their list everyone strictly worse than the kept tier; deletions are mirrored on theAA\-side\. If any agent’s list becomes empty, no super\-stable matching exists\. … This pruning forced several pairs \(B2B\_\{2\}can only takeA1A\_\{1\},B5B\_\{5\}onlyA8A\_\{8\},B7B\_\{7\}onlyA2A\_\{2\}\), reducing the instance to a small feasible edge set\. From the remaining edges I constructed a perfect matching and validated super\-stability directly\.

At Small size,4949of6060trajectories \(82%82\\%\) produce a super\-stable matching; the remaining1111produce no parseable matching\. Strikingly, no Small trajectory produces a well\-formed matching that fails super\-stability; the failure mode is exclusively non\-production rather than mis\-production\.

At Modest size, the picture changes qualitatively\. Only1/601/60\(1\.7%1\.7\\%\) produces a super\-stable matching;5252\(87%87\\%\) produce no parseable matching, and77produce a well\-formed matching that fails super\-stability \(44are not even weakly stable,33are strongly stable but not super\-stable\)\. The model continues to invoke Irving–Manlove by name, but the edge\-deletion machinery is rarely executed in detail: the trajectory typically names the procedure and asserts its outcome\.

##### Infeasible instances\.

On infeasible super\-stable instances, GPT\-5\.2 produces either a forced\-pair impossibility chain or an Irving\-style certificate in which it runs the edge\-deletion procedure and reports that some agent’s list became empty\. A typical Irving\-style certificate runs:

> The reductions forceA1−B9A\_\{1\}\-B\_\{9\}\(mutual top\),A9A\_\{9\}must be withB1B\_\{1\}\(deletions eliminate all other feasible partners\), andB10B\_\{10\}ends up only feasibly matchable withA2A\_\{2\}\. But then the pair\(A9,B10\)\(A\_\{9\},B\_\{10\}\)is unavoidable as a blocking pair:A9A\_\{9\}is indifferent betweenB1B\_\{1\}andB10B\_\{10\}, soA9A\_\{9\}weakly prefersB10B\_\{10\}toB1B\_\{1\};B10B\_\{10\}is indifferent betweenA9A\_\{9\}andA2A\_\{2\}, soB10B\_\{10\}weakly prefersA9A\_\{9\}toA2A\_\{2\}\. Therefore the instance admits no super stable matching\.

As on the other infeasible cells, the rate is determined by the prompt variant\. Under the empty\-hint prompt:20/3020/30\(67%67\\%\) at Small and29/3029/30\(97%97\\%\) at Modest, all4949correct\. Under the no\-hint prompt:0/300/30at each size\. This is the only cell on which a reasoning behaviour improves with size: the larger instance carries more structural constraints that make the forced\-pair chain easier to spot, and the empty\-hint prompt gives the model permission to follow it to the impossibility conclusion\.

##### Discussion\.

A consistent picture emerges\. On feasible cells, GPT\-5\.2 succeeds at Small size by deploying non\-mechanical heuristics that exploit instance\-specific structure: the constructive chain heuristic for strict core, deferred acceptance with forced\-pair pre\-processing for strongly stable, and Irving–Manlove edge\-deletion for super stable\. As the instance scales fromn=10n=10ton=30n=30each of these heuristics degrades, and the rate of no\-parseable\-answer outputs rises sharply\. The model does not have a fallback strategy that degrades gracefully: it has only the same heuristics applied with less fidelity, plus an increasing tendency to abandon the question\.

On infeasible cells, the qualitative finding is more prompt\-dependent than capability\-dependent\. GPT\-5\.2 produces correct impossibility arguments on a substantial fraction of infeasible instances under the empty\-hint prompt \(80%80\\%on strict\-core Small,63%/57%63\\%/57\\%on strongly\-stable,67%/97%67\\%/97\\%on super\-stable\), but*zero*non\-existence claims under the no\-hint prompt across all180180infeasible\-cell trajectories issued under that variant\. The forced\-pair impossibility chain is in the model’s repertoire and, when prompted to consider non\-existence, scales with size on the matching cells \(whereas the strict\-core chain collapses at Modest because the chains are longer and the coalitions larger\)\. The practical implication is that infeasibility\-handling rates on benchmarks like ours are largely a function of prompt phrasing rather than of model capability, and care must be taken not to conflate the two\.

### L\.4LLM\-judge setup

The LLM\-judge stage extracts structured features from each scratchpad without itself doing any algorithmic verification\. Its output is then joined to the deterministic verifier’s stratum labels for the per\-cell tables above\. We use DeepSeek V4 Pro as the judge with temperature00and JSON\-mode response formatting\. Each judge call sees: \(i\) the original problem statement that the model was given, \(ii\) the model’s scratchpad, \(iii\) the model’s parsed final answer, \(iv\) a fixed list of per\-cell open probes asking for verbatim quotes of specific trace features, and \(v\) a canonical\-strategy check that asks whether the trace follows a notion\-specific reference strategy \(yes / partial / no\)\. The probe fields and the canonical\-strategy descriptions were defined in advance from a preliminary inspection of∼\\sim50 scratchpads and were held fixed during the full720720\-trajectory run\. The judge is instructed to produce verbatim quotes wherever feasible, to avoid inventing content that is not in the scratchpad, and to returnnullor\[\]for fields with no relevant content\.

The full prompt template, with placeholders shown in\{italic\}, is:

> System\.You are an expert annotator analyzing reasoning traces from a language model solving combinatorial matching and allocation problems \(housing markets / stable matching with ties\)\. For each trace you will answer a set of open\-ended probe questions about objective features of the trace, and then a canonical\-strategy check\. Always output a single JSON object and nothing else\. Use verbatim quotes from the scratchpad where requested\. Do not invent content not present in the scratchpad\. User\. PROBLEM CONTEXT \(the prompt the model was given\): """prompt\_text""" MODEL’S REASONING TRACE \(scratchpad\): """scratchpad""" MODEL’S FINAL ANSWER \(parsed from<answer\>tag\): """answer""" PROBE QUESTIONS: \(1\) FIELDalgorithm\_name: Verbatim name\(s\) of the algorithm the model invokes \(e\.g\. “Top Trading Cycles”, “Gale–Shapley”\)\. If none stated, write null\. Maximum 8 words\. \(2\) FIELDcycles\_shown: List of explicit cycles or rounds shown in the scratchpad, each as a chain string of the form “Ai→Cj→Ak→⋯→AiA\_\{i\}\\to C\_\{j\}\\to A\_\{k\}\\to\\cdots\\to A\_\{i\}”\. If none, write\[\]\. \(3\) FIELDtie\_break\_rule: Verbatim quote of the sentence\(s\) describing how ties within indifference classes are broken\. If unspecified, null\. \(4\) FIELDverification\_text: Verbatim quote of the sentence\(s\) where the model verifies the result beyond a generic property\-citation\. If only a generic property\-citation is present, write the exact stringPROPERTY\_CITATION\_ONLY\. If none, null\. \(5\) FIELDforced\_assignments\_pre\_algorithm: List of any “agent must be assigned house” deductions stated before the main algorithm is run, each with a quoted reason\. If none,\[\]\. \(6\) FIELDfinal\_claim: One ofallocation\_produced,claims\_no\_solution,abstains\_or\_refuses\. Quote the closing sentence of the scratchpad\. CANONICAL STRATEGY CHECK\. Indicate whether the trajectory follows the canonical strategy below: “yes” \(clearly and substantively\), “partial” \(some elements but deviates in others\), or “no”\. Quote 1–2 verbatim sentences as evidence\. If partial or no, briefly note in 1 sentence what differs\. Canonical strategy:strategy\_name\. Description:strategy\_description\. OUTPUT JSON OBJECT WITH EXACTLY THESE FIELDS: \{ "algorithm\_name": <answer\>, "cycles\_shown": <answer\>, "tie\_break\_rule": <answer\>, "verification\_text": <answer\>, "forced\_assignments\_pre\_algorithm": <answer\>, "final\_claim": <answer\>, "canonical\_strategy\_match": "yes" \| "partial" \| "no", "canonical\_strategy\_evidence": "<verbatim quote\(s\)\>", "canonical\_strategy\_deviation": "<one sentence or null\>" \}

The probe questions vary slightly across the six\(notion,feasibility\)\(\\textit\{notion\},\\textit\{feasibility\}\)cells \(for instance, the matching cells substitute “forced pairs” for “trading cycles” in probe \(2\)\), but the system prompt, the output\-schema requirements, and the canonical\-strategy check template are shared across all cells\. The complete cell\-specific probe definitions are released alongside the code\.

## Appendix MPrompt\-level mitigation

If the epistemic failure were a surface prompting artifact, an instruction warning the model about indeterminacy should remove it\. We test this with four levels of prompt mitigation on the bundle comparison problem, run on both RS\-comparable and RS\-incomparable cases\. A genuine fix has to keep accuracy high on both, since a deployed user does not know in advance which kind of query they are issuing\.

- •Level 1 bare, no hint of indeterminacy\.
- •Level 2 multiple choice with an explicit "not enough information" option\.
- •Level 3 caution\. general = source\-agnostic \("preferences may not entail an answer, do not assume one"\)\. specific = names the structure being tested\.
- •Level 4 few\-shot demonstration ending in "cannot be determined"

Table[27](https://arxiv.org/html/2608.18631#A13.T27)shows that no prompt calibrates the model\. Every intervention that raises undetermined accuracy also lowers accuracy on the determined queries: the general caution moves GPT\-5\.2 from1\.00\|0\.001\.00\\mid 0\.00to0\.43\|0\.800\.43\\mid 0\.80and Gemini\-2\.5\-P from1\.00\|0\.001\.00\\mid 0\.00to0\.47\|0\.930\.47\\mid 0\.93\. The error is relocated, not removed\.

Of the prompts tried, no single prompt is safe across models\. The specific caution lifts Claude and Gemini but collapses OSS\-120B to0\.27\|0\.930\.27\\mid 0\.93, and the explicit abstain option is ignored by three of four models, which keep imposing the lexicographic default\.

Few\-shot demonstrations raise undetermined accuracy sharply when they come from the same source of indeterminacy, but the gain does not transfer\. When the demonstrations used for bundle comparison are applied to a different source \(an item the agent never ranked\), Table[28](https://arxiv.org/html/2608.18631#A13.T28)shows they help almost not at all\. The model reproduces the pattern it was shown rather than acquiring a general ability to flag indeterminacy\.

This is why the failure is not a surface prompting artifact\. Prompting moves the model along a trade\-off between over\-commitment and over\-abstention, and a caution aimed at one kind of indeterminacy does not carry over to another\. This matters in practice, because a deployed user does not know in advance whether a query is undetermined, or which kind of indeterminacy it involves, so they cannot supply the matching caution beforehand\. The cross\-setting experiment tests this\. When the demonstrations describe a different source than the query, performance falls back to the baseline, showing the model has not learned a general ability to recognize indeterminacy but only to imitate the case it was shown\.

Table 27:Accuracy on bundle comparison problems, with different levels of prompt mitigation\. Levels: 1 bare, 2 MCQ with an explicit "not enough information" option, 3 caution \(general = source\-agnostic, specific = names the structure\), 4 few\-shot demos\. Each is run on 30 instances, with accuracy reported as determined∣\\midundeterminedModelL1 bareL2 MCQL3 generalL3 specificL4 few\-shotGPT\-5\.21\.00\|0\.001\.00\\mid 0\.000\.97\|0\.000\.97\\mid 0\.000\.43\|0\.800\.43\\mid 0\.800\.73\|0\.270\.73\\mid 0\.270\.93\|0\.100\.93\\mid 0\.10Claude\-4\.5\-S1\.00\|0\.001\.00\\mid 0\.001\.00\|0\.001\.00\\mid 0\.000\.97\|0\.570\.97\\mid 0\.571\.00\|0\.831\.00\\mid 0\.831\.00\|0\.971\.00\\mid 0\.97Gemini\-2\.5\-P1\.00\|0\.001\.00\\mid 0\.001\.00\|0\.001\.00\\mid 0\.000\.47\|0\.930\.47\\mid 0\.930\.97\|0\.500\.97\\mid 0\.501\.00\|0\.901\.00\\mid 0\.90OSS\-120B1\.00\|0\.001\.00\\mid 0\.000\.83\|0\.370\.83\\mid 0\.370\.73\|0\.630\.73\\mid 0\.630\.27\|0\.930\.27\\mid 0\.930\.97\|0\.830\.97\\mid 0\.83Table 28:Accuracy on undetermined atomic query, with different levels of prompt mitigation\. Levels: L1 bare, L4 few\-shot demos \(in\-domain = examples about the tested source of indeterminacy\. cross\-source = examples about the other source\)\. Each is run on 30 instances, with accuracy reported\.ModelL1L4 in\-domainL4 cross\-domainGPT\-5\.20\.000\.100\.13Claude\-4\.5\-S0\.000\.970\.00Gemini\-2\.5\-P0\.000\.900\.00OSS\-120B0\.000\.830\.00
## Appendix NCode\-Assisted Reasoning: Approaches by Model and Size

Table 29:Code\-based task accuracy by domain, problem size, and feasibility \(F = feasible and I = infeasible\)\. Each cell shows the percentage of correct responses out of 10 instances\. Dashes indicate conditions not evaluated\. Timeouts and invalid responses are counted as incorrect\.Shapley\-Scarf MarketMatching MarketSmallModestMediumSmallModestMediumModelFIFIFIFIFIFIGemini\-2\.510%0%10%0%––20%70%0%60%––Claude\-4\.5\-S100%100%0%70%––90%100%30%100%––GPT\-5\.2100%100%90%70%100%30%100%100%90%90%0%10%

The accuracy achieved by LLMs on algorithmic reasoning questions, when using code to solve the problem, are provided in[Table29](https://arxiv.org/html/2608.18631#A14.T29)\.

This section summarises the dominant strategy each model produces in the code\-assisted condition, broken down by notion and instance size\. Three patterns recur\. First, atn=10n=10, GPT\-5\.2 and Claude Sonnet 4\.5 follow a common verify\-then\-fall\-back pattern: the generated code first attempts the textbook algorithm for the notion \(Top Trading Cycles, deferred acceptance, or Irving’s super\-stable algorithm\), checks whether the resulting object satisfies the notion’s condition, and on a failed check falls back to exhaustive enumeration over all candidate allocations or matchings combined with a complete blocking\-coalition or blocking\-pair check\. The fallback is sound atn=10n=10because the search space is small enough to enumerate\. Second, atn=30n=30and above the same models switch to heuristic strategies \(randomised tie\-breaking with verification, backtracking with constraint propagation, exponential\-weight reductions to maximum\-weight matching\), and the soundness of the fallback degrades as size grows\. Third, Gemini 2\.5 Pro is the outlier: it does not use exhaustive enumeration at any size, and its code typically applies a textbook algorithm directly with no verification step\.

### N\.1GPT\-5\.2

GPT\-5\.2’s code shows the cleanest version of the verify\-then\-fall\-back pattern\. On strict core with ties atn=10n=10, it first runs Top Trading Cycles \(TTC\) with first\-in\-list tie\-breaking, verifies the output against a complete blocking\-coalition oracle, and falls back to exhaustive enumeration of alln\!n\!allocations on a verification failure, returning\{\}\\\{\\\}when the enumeration finds no allocation in the strict core\. Atn=30n=30the model switches to randomised TTC: it repeats TTC with random tie\-breaking until verification succeeds\. This is sound on feasible instances and remains correct on alln=50n=50feasible instances we evaluated, but it cannot prove non\-existence, so on infeasiblen=30n=30instances the model occasionally falls back to a MILP encoding of the strict\-core polytope, with mixed soundness\. Atn=50n=50infeasible instances the randomised loop times out before any code completes\. On super\-stable matching, GPT\-5\.2 progresses from exhaustive enumeration atn=10n=10, to backtracking with constraint propagation atn=30n=30, to a faulty implementation of Irving’s algorithmSuperatn=50n=50that omits the step of breaking all engagements of multiply\-engaged agents, and consequently produces false NE claims on everyn=50n=50instance\.

Table 30:GPT\-5\.2: dominant approach in the code\-assisted condition, by task and instance size\. For notions with feasibility variation, E and NE rows are shown separately where approaches differ\.NotionnnE/NEDominant approachCore \(HA, strict\)10–50–Top Trading Cycles \(correct\)Strict Core\(HA, ties\)10E/NETTC attempted; on verification failure, falls back to exhaustive enumeration with complete blocking\-coalition check \(sound\)30ERandomised TTC: repeat with random tie\-breaking until a strict\-core allocation is found and verified30NEHeuristic search failure; MILP in some responses; not always sound50ERandomised TTC; all instances correct50NETimeout \(no result produced\)Rank\-Max\. Alloc\.\(HA, ties\)10–Brute\-force enumeration over all allocations30–50–Exponential\-weight reduction to max\-weight matching \(one\-shot; empirically correct\)Super Stable\(SM, ties\)10E/NEGale\-Shapley variant attempted; on verification failure, falls back to exhaustive enumeration with complete super\-blocking\-pair check \(sound\)30E/NEBacktracking with constraint propagation \(CSP\); mostly correct50E/NEAlgorithmSuperattempted but incorrectly implemented: omits breaking all engagements of multiply\-engaged agents, causing false NE claims on all instancesRank\-Max\. Match\.\(SM, ties\)10–30–Exponential\-weight reduction \(one\-sidedAA\-side only\); misunderstands two\-sided definition
### N\.2Claude Sonnet 4\.5

Claude Sonnet 4\.5 follows the same overall verify\-then\-fall\-back pattern atn=10n=10as GPT\-5\.2 \(exhaustive enumeration of allocations or matchings, with complete blocking checks\), but its heuristic strategies atn=30n=30are more limited\. On strict core with ties atn=30n=30, the generated code searches a random sample of allocations and verifies them against blocking coalitions of size≤5\\leq 5only\. This yields low accuracy on feasible instances but accidentally high accuracy on infeasible ones, since a small blocking coalition is usually found quickly\. On super stable atn=30n=30, the code runs Gale\-Shapley with random tie\-breaking and post\-hoc super\-stability verification, which gives partial accuracy on feasible instances and again finds an obstruction quickly when none exists\. On rank\-maximal matching, Claude’s code \(like GPT\-5\.2’s\) operates on a one\-sided ranking only, indicating that both models misread the two\-sided definition\.

Table 31:Claude\-4\.5\-Sonnet: dominant approach in the code\-assisted condition, by task and instance size\.NotionnnE/NEDominant approachCore \(HA, strict\)10–30–Top Trading Cycles \(correct; minor cycle\-detection bugs fixed in later iterations\)Strict Core\(HA, ties\)10E/NETTC attempted; on verification failure, falls back to exhaustive enumeration with full blocking\-coalition verification \(sound\)30EHeuristic random allocation search with limited coalition\-size checks \(≤5\\leq 5\); low accuracy30NEHeuristic: blocking coalition found quickly; mostly correctRank\-Max\. Alloc\.\(HA, ties\)10–Mixed: some exhaustive enumeration, some greedy rank\-by\-rank30–Greedy rank\-by\-rank fixation \(incorrect;0%0\\%accuracy\)Super Stable\(SM, ties\)10E/NEGale\-Shapley variant attempted; on verification failure, falls back to exhaustive enumeration of all matchings with super\-blocking\-pair check \(sound\)30ERandom Gale\-Shapley tie\-breaking with post\-hoc verification \(heuristic; partial accuracy\)30NEHeuristic failure after many random trials; often correctRank\-Max\. Match\.\(SM, ties\)10–30–Iterative rank addition with one\-sided matching; misunderstands two\-sided definition
### N\.3Gemini 2\.5 Pro

Gemini 2\.5 Pro does not use exhaustive enumeration at any size, and its code typically lacks an explicit verification step\. On strict core with ties, it runs TTC with an arbitrary tie\-breaking rule and treats the output as the answer regardless of whether it lies in the strict core, which means it never identifies infeasible instances\. On super stable, the code is an ad\-hoc modification of Gale\-Shapley with no super\-stability check, and atn=30n=30Gemini has a high rate of false NE claims regardless of ground\-truth feasibility\. On rank\-maximal matching atn=30n=30, Gemini’s code is a greedy per\-rank algorithm that achieves0%0\\%accuracy\. The textbook algorithm for the simplest notion in this study \(Core in strict\-preference housing markets\) is correctly implemented, with two cycle\-detection bugs atn=30n=30\.

Table 32:Gemini\-2\.5: dominant approach in the code\-assisted condition, by task and instance size\.NotionnnE/NEDominant approachCore \(HA, strict\)10–30–Top Trading Cycles \(correct; two failures atn=30n=30due to cycle\-detection bugs\)Strict Core\(HA, ties\)10–30–TTC with arbitrary tie\-breaking and no verification step \(incorrect; never identifies infeasible instances\)Rank\-Max\. Alloc\.\(HA, ties\)10–30–Greedy sequential maximum matching per rank \(incorrect heuristic; near\-zero accuracy atn=30n=30\)Super Stable\(SM, ties\)10ECustom iterative elimination or modified Gale\-Shapley variants10NEHeuristic failure or custom elimination; partially correct30E/NEAd\-hoc Gale\-Shapley modifications; high rate of false NE claims regardless of ground truthRank\-Max\. Match\.\(SM, ties\)10–Exponential\-weight Hungarian \(one\-sided; misunderstands two\-sided definition\)30–Greedy iterative per\-rank matching \(incorrect heuristic;0%0\\%accuracy\)

## Appendix ORefinement Experiment Details

##### Setup\.

The refinement experiment tests whether LLMs can correct their answers when given verification\-based feedback\. We focus on two solution notions that require generating valid allocations or matchings:

- •Strict core\(Shapley–Scarf housing market\): agents own one house each and can trade\. A valid strict core allocation has no group of agents \(coalition\) that could redistribute their endowed houses among themselves so that every member weakly improves and at least one strictly improves\.
- •Super stable matching\(bipartite matching market\): agents on two sides are matched one\-to\-one\. A super stable matching has no blocking pair—a pair of agents who both weakly prefer each other to their current partners\.

For each notion, we include 30 feasible instances \(a valid solution exists\) and 30 infeasible instances \(no valid solution exists\), for a total of 60 instances per model per notion\. We evaluate two models: OSS\-120B on Small instances \(n=10n=10\) and GPT\-5\.2 on Modest instances \(n=30n=30\)\. All instances use the Generation task format, where the model must produce a JSON allocation or matching \(or\{\}if no solution exists\)\.

##### Interaction protocol\.

Each instance is evaluated using a multi\-turn conversation with up to three attempts:

1. 1\.Attempt 1: The model receives the original task prompt and produces an answer\.
2. 2\.Attempt 2\(if Attempt 1 is wrong\): The model receives feedback explaining why its answer is incorrect, then produces a new answer\. The full conversation history is preserved\.
3. 3\.Attempt 3\(if Attempt 2 is also wrong\): The model receives another round of feedback and makes a final attempt, again with full history\.

If any attempt produces a correct answer, the instance is marked as a success and no further attempts are made\. If any attempt times out or produces an error, the remaining attempts are skipped\.

##### Feedback design\.

The feedback message is constructed automatically by running the same programmatic verifier used to score the initial experiments\. The content of the feedback depends on what the model got wrong\.

When the model returns\{\}on a feasible instance\(incorrectly claiming no solution exists\):

> “Your answer is incorrect\. A valid \[notion\] solution does exist for this instance, but you returned an empty allocation\. You have \[N\] attempts remaining\. Please try again carefully and return your answer enclosed in<answer\></answer\>tags\.”

This tells the model that a solution exists without revealing what it is\.

When the model returns a wrong allocation for strict core:

The verifier computes all blocking coalitions and reports them\. For example:

> “Your answer is incorrect\. Your allocation has 2 blocking coalitions under the strict core\. Here are the blocking coalitions:\{A2, A10, A5, A8, A3, A9, A7\};\{A2, A10, A5, A9, A7\}\. Each coalition can reshuffle their endowed items among themselves so that every member weakly improves and at least one strictly improves\. You have \[N\] attempts remaining\.”

The feedback includes:

- •The total number of blocking coalitions\.
- •The members of each coalition \(up to 3 coalitions are shown; if there are more, a note indicates the total\)\.
- •A plain\-language explanation of what a blocking coalition means\.

When the model returns a wrong matching for super stable:

The verifier computes all blocking pairs and reports them\. For example:

> “Your answer is incorrect\. Your matching has 5 blocking pairs under super stability\. Here are the blocking pairs: \(A1, B10\), \(A3, B10\), \(A4, B10\), \(A4, B9\), \(A8, B9\)\. In each pair, both agents weakly prefer each other to their current partners\. You have \[N\] attempts remaining\.”

The feedback includes:

- •The total number of blocking pairs\.
- •The specific pairs \(up to 5 are shown; if there are more, a note indicates the total\)\.
- •A plain\-language explanation of the blocking condition\.

When the model’s response cannot be parsed as valid JSON:

> “Your answer could not be parsed as a valid JSON allocation\. Make sure you return a JSON object mapping each agent to an assigned alternative, enclosed in<answer\></answer\>tags\. You have \[N\] attempts remaining\.”

##### Key design choices\.

- •Conversation history is preserved\.Each attempt is sent as a new message in the same multi\-turn conversation\. The model sees its own prior responses and the feedback it received, without needing to re\-read the original problem description\.
- •Feedback is informative but not prescriptive\.The feedback identifies specific violations \(which coalitions block, which pairs block\) but does not suggest how to fix the answer\. The model must figure out the repair strategy on its own\.
- •Verification is programmatic\.Correctness is determined by the same algorithmic verifiers used in the main experiments—not by string matching or LLM\-based judging\. For strict core, the verifier exhaustively checks all possible coalitions\. For super stability, it checks all agent pairs for the weak blocking condition\.
- •Feasibility feedback is asymmetric\.When an instance is feasible but the model returns\{\}, the feedback reveals that a solution exists\. When an instance is infeasible and the model returns a wrong allocation, the feedback shows the blocking coalitions or pairs—which may indirectly signal that no valid solution exists \(e\.g\., seeing hundreds of blocking coalitions suggests infeasibility\)\. However, the feedback never explicitly states that no solution exists\.

## Appendix PLLM\-Judge Analysis Details

We use a separate LLM\-as\-judge pass to label the reasoning portion of each response, i\.e\., which algorithm or solution concept the responding model appears to have invoked, independently of whether the final allocation is correct\. We run this in two settings\. Thegenerationsetting classifies the algorithm a model used to produce a solution when no specific target notion is provided\. Theselectionsetting classifies the criterion a model prioritized when picking among several candidate solutions\. The two settings share the same judge model, prompt scaffolding, and answer format; they differ in the option set and in how “intended” and “achieved” are scored\.

Judge configuration\.All judging is done with Gemini\-2\.5\-Flash through thegoogle\-genaiPython client, using the client’s default sampling parameters \(no temperature, top\-pp, or other generation arguments are set\)\. The judge is shown two pieces of context: the original prompt that was given to the model under study, and that model’s full response\. It is asked to select a single option from a closed list and return its choice in the format`<answer\>X</answer\>`\. The judge is explicitly instructed*not*to verify the algorithm or criterion by computing solutions itself; its label must be based only on explicit textual mentions or descriptions in the response\. If no listed option matches, it must return the catch\-all “no algorithm mentioned”/“some other notion” option\. Each judge call is wrapped in a three\-attempt retry to absorb transient API failures, and the parsed letter is post\-processed by stripping the`<answer\>\.\.\.</answer\>`tags; we additionally fall back to extracting the letter inside`\\boxed\{\.\.\.\}`when the judge returns its answer in LaTeX form\.

Coverage and aggregation\.Both settings sweep over the cross\-product of model, instance size∈\{10,30\}\\in\\\{10,30\\\}, domain∈\{\\in\\\{House Allocation, Shapley\-Scarf Markets, Matching Markets\}\\\}, and preference type∈\{\\in\\\{strict and complete, strict and incomplete, with ties and complete\}\\\}, restricted to the relevant subset of each model’s responses \(the underspecified\-instance subset for the generation setting and the selection\-task subset for the selection setting\)\.

### P\.1Generation Setting

In the generation setting, the judge classifies the algorithm the model used to produce a single solution to an underspecified instance\. The option set is restricted to algorithmic procedures: Top Trading Cycles, the Hungarian min\-cost algorithm, Hopcroft–Karp matching, exhaustive search, Gale–Shapley deferred acceptance, Irving’s strong\-stable and super\-stable matching algorithms, serial dictatorship, “some other algorithm”, and “no algorithm mentioned/described”\. A response is counted as having*intended*the canonical algorithm for its domain when the judge’s choice matches a fixed mapping: house allocation↔\\leftrightarrowTop Trading Cycles, object allocation↔\\leftrightarrowserial dictatorship, and stable matching↔\\leftrightarrowGale–Shapley\. The*achieved*count is computed independently from the model’s allocation: for instances with complete preferences, we use the binary correctness label produced by our standard verifier; for instances with incomplete preferences, we recompute the core allocation and compare it against the model’s allocation, restricted to the agents that the reference solution actually matches\.

A representative judge prompt for this setting is shown in[Figure15](https://arxiv.org/html/2608.18631#A16.F15)\. The placeholders⟨original prompt⟩and⟨model response⟩are filled in from the row being judged\.

Previously I asked another LLM the following question:
“⟨original prompt⟩”
Here is its response:
`"""`
⟨model response⟩
`"""`
Your task is to identify the approach or algorithm that the model has used to answer the question\. Among the following options, select the most appropriate option for the model’s response:
A: Top Trading Cycles \(TTC\)
B: Hungarian Min\-cost Algorithm
C: Hopcroft–Karp Maximum Matching Algorithm
D: Searching through all possibilities
E: Deferred Acceptance \(Gale–Shapley\)
F: Strong stable matching algorithm \(Irving\)
G: Super stable matching algorithm \(Irving\)
H: Serial Dictatorship
I: Some other algorithm
J: No algorithm mentioned/described
DO NOT try to verify the algorithm that the LLM has used by computing solutions yourself\. Only rely on explicit mentions or descriptions of the algorithms in options A–I\. If no algorithm is explicitly mentioned or described, select option J\. Return your answer in the following format:`<answer\>option</answer\>`\. For example, if the correct option were option X, you would have to return`<answer\>X</answer\>`\.Figure 15:Judge prompt used in the generation setting\.
### P\.2Selection Setting

In the selection setting, the responding model is presented with a set of candidate solutions to an instance, each pre\-labeled with the solution concept it satisfies, and is asked to choose one\. The judge then classifies which solution concept or criterion the model prioritized in its written justification\. The option set covers eleven concepts: \(weak\) core, utilitarian welfare, egalitarian welfare, rank\-maximality, strict core, \(weak\) stability, strong stability, super stability, Pareto\-optimality, maximum\-cardinality Pareto\-optimal matching, and a catch\-all “some other notion or criterion”\. When a response references multiple concepts, the judge is instructed to select the one the model treats as the first priority\.

For each row we record three quantities\.*Intended*is the concept identified by the judge from the model’s reasoning\.*Actual*is the concept satisfied by the candidate the model ultimately picked, recovered by mapping each candidate’s pre\-assigned label onto the same eleven\-option set\.*Achieved*is an indicator equal to one if and only if the intended and actual concepts agree—i\.e\., the model’s chosen solution in fact satisfies the concept its reasoning claims to prioritize\. The mapping from candidate labels to option letters is fixed and deterministic; in particular, candidates labeled either “Core” \(under strict preferences\) or “Weak core” \(under preferences with ties\) are both mapped to the \(weak\) core option\.

A representative judge prompt for this setting is shown in[Figure16](https://arxiv.org/html/2608.18631#A16.F16)\.

Previously I asked another LLM the following question:
“⟨original prompt⟩”
Here is its response:
`"""`
⟨model response⟩
`"""`
Your task is to identify the solution concept or criterion that the model prioritizes while answering the question\. Among the following options, select the most appropriate option for the model’s response:
A: Core: the solution is in the core \(if preferences are strict\), or in the weak core \(if preferences have ties\)\.
B: Utilitarian welfare: the solution minimizes the sum of ranks of matched agents compared to all other options\.
C: Egalitarian welfare: the solution has the smallest “worst” rank among all options\.
D: Rank\-maximality: the solution maximizes the number of agents matched to their first preference; conditional on that, it maximizes the number matched to their second preference, and so on\.
E: Strict core: there is no coalition of agents who can re\-assign their endowments such that every agent in the coalition is weakly better off and at least one agent is strictly better off\.
F: \(Weak\) stability: the solution has no weakly blocking pair, i\.e\., no pair of unmatched agents that strictly prefer each other to their matched partners\.
G: Strong stability: the solution has no strongly blocking pair, i\.e\., no pair of unmatched agents in which one agent weakly prefers the other to its current match and the other strictly prefers the first to its current match\.
H: Super stability: the solution has no super blocking pair, i\.e\., no pair of unmatched agents that weakly prefer each other to their matched partners\.
I: Pareto\-optimality: there is no other solution in which some agent strictly improves without making another agent worse off\.
J: Maximum\-cardinality Pareto\-optimal: the solution maximizes the number of agents matched to a ranked alternative and is Pareto\-optimal\.
K: Some other notion or criterion\.
DO NOT try to verify the property that the model claims to prioritize by computing solutions yourself\. Only rely on explicit textual mentions or descriptions of the criteria in options A–J\. If multiple criteria are mentioned, use your discretion to identify which one is given the first priority by the model\. If no criterion is explicitly mentioned or described, select option K\. Return your answer in the following format:`<answer\>option</answer\>`\. For example, if the correct option were option X, you would have to return`<answer\>X</answer\>`\.Figure 16:Judge prompt used in the selection setting\.
### P\.3Additional judges and human validation

Two judge pipelines are used in this paper\. The generation\-side judge identifies the algorithm or concept a model targets when it computes a solution, and supports both[SectionI\.3](https://arxiv.org/html/2608.18631#A9.SS3)and[AppendixL](https://arxiv.org/html/2608.18631#A12)\. The selection\-side judge supports the intention\-action analysis behind[Figure14](https://arxiv.org/html/2608.18631#A9.F14)\. The lexicographic\-completion and premature\-termination findings of[Figure3](https://arxiv.org/html/2608.18631#S3.F3)are detected by a deterministic script and use no judge\.

Independent judges\.Each pipeline is rerun with two additional models \(GPT\-5\.6\-Luna and Gemini\-3\.5\-Flash\) on a stratified subset\. Three\-judge Fleiss’κ\\kappais 0\.64 for the reasoning\-strategy judge and 0\.82 for the intention\-action judge\. The lower agreement on the reasoning\-strategy judgements comes from the “strongly stable” cell, where the boundary is genuinely ambiguous because the model sometimes gives a valid argument that is not the textbook one, and the judges score these borderline cases inconsistently\. Pooling hides where the disagreement sits, so we report this per notion: all three judges agree on 0\.95 of the strict\-core traces and 0\.94 of the super\-stable traces, against 0\.43 for strongly stable\.

Human validation\.Human annotation is also used to validate the judge responses\. For 36 responses, one author independently chose which concept the model prioritized, using the same options and instructions the judge saw\. Against the paper’s judge, Gemini\-2\.5\-Flash, human\-vs\-judge Cohen’s kappa is 0\.86, in line with the inter\-judge agreement\. The alternate judges agree a little less, 0\.72 and 0\.76, mostly on the incomplete house\-allocation cell, where the original judge and the human read an implicit assign\-everyone justification as max\-cardinality intent while the other two judges do not\. The human therefore agrees most with the exact judge behind the reported numbers, and the one divergent cell is the one we flag as judge\-sensitive in[SectionI\.5](https://arxiv.org/html/2608.18631#A9.SS5)rather than pool with the rest\.

Feasibility oracle\.Correctness is decided by deterministic checker functions that verify every model output against the target solution concept\. Because these checkers are our own implementation, we cross\-checked them with an independent brute\-force solver that enumerates all allocations and matchings for small instances and decides existence directly from each concept’s definition\. Across 1,800 random instances \(strict core, super\-stable, and strongly\-stable, with n up to 5\), the oracle’s existence verdicts, the solutions it returns, and the blocking\-pair verifier agree with the brute\-force solver in every case\. We release this validation harness alongside the code\.