Leading large language models routinely hallucinate certainty on preference reasoning: they default to ad-hoc tie-breakers and miss infeasible solutions in allocation and matching tasks, with accuracy collapsing as problem size and indeterminacy grow.

Main Finding

Large language models (LLMs) systematically fail to recognize and handle indeterminacy in preference reasoning. Across a hierarchy of tasks—from atomic retrieval to algorithmic construction/verification of solutions in matching and allocation markets—state-of-the-art models (GPT-5.2, Gemini-2.5-Pro, Claude-4.5-S, OSS-120B) habitually substitute unstated assumptions, fail to abstain when answers are not entailed, and break down as instance size or structural complexity grows. These failures are not due to computational hardness (all ground-truth checks/solutions are polynomial-time) but reflect epistemic and structural reasoning deficits with direct implications for agentic and collective decision-making.

Key Points

• Two formal axes of indeterminacy:
  • Epistemic indeterminacy: incomplete, partial, or tied preferences produce queries that are not logically entailed by the input.
  • Structural indeterminacy: given preference structure (e.g., ties) and a solution concept (core, stability, Pareto optimality), a requested solution may provably not exist.
• Taxonomy of tasks (in increasing complexity):
  • Atomic queries: retrieve rank/position from one preference.
  • Comparative queries: entail/refute pairwise or bundle relations.
  • Aggregative queries: aggregate across many agents (counts, majorities).
  • Structural (algorithmic) queries: construct or verify matchings/allocations that satisfy axiomatic solution concepts (core, stability, Pareto).
• Main empirical findings:
  • Large deterministic gap: models perform much worse on undetermined queries than on matched determined ones and often answer determinately instead of reporting "unknown."
  • Systematic substitution rules: when under-specified, models commonly impose specific heuristics (e.g., lexicographic ordering for RS-incomparable bundles) silently and consistently.
  • Poor calibration and abstention: models rarely use explicit indeterminacy/NOTA options even when no valid solution exists; adding explicit abstention choices helps but introduces bias (false declarations of non-existence).
  • Structural failures: models struggle with algorithmic tasks as market size increases and fail to correctly detect infeasible instances; when assisted (feedback or code execution), improvements are driven by brute-force/search heuristics that do not scale.
  • Verification failure: even selection/verification tasks (given candidate solutions) show high error—models pick options that violate the intended solution concept.
• Diagnostic metric: Invalid Rate — frequency with which a model produces a determined answer for an undetermined query (captures speculative completion/hallucinated certainty).

Data & Methods

• Domains evaluated:
  • House/object allocation (Pareto optimality)
  • Shapley–Scarf housing markets (core, weak/strict core under ties)
  • Two-sided matching markets (stability: weak/strong/super under ties)
• Preference expressivity considered: strict complete orders (SO), strict incomplete (SI), complete with ties (TO), ties + incompleteness (TI), and general partial orders.
• Models tested: GPT-5.2, Gemini-2.5-Pro, Claude-4.5-Sonnet, OSS-120B.
• Instance sizes: Small (n=10), Modest (n=30), Medium (n=50), Large (n≥100).
• Prompting and evaluation:
  • Zero-shot, single-turn queries as baseline; prompt variations included free-flow, free-flow + “if known,” and multiple-choice with an explicit “not enough information” option.
  • Assisted settings: iterative refinement with feedback, and code generation + execution to produce/verify solutions.
• Ground truth and scoring:
  • All tasks constructed so ground-truth entailments and feasibility are decidable in polynomial time via standard combinatorial algorithms.
  • Undetermined queries are scored correct only if the model explicitly indicates the answer is not determined; committing to any specific completion counts as incorrect.
  • Analyses include per-task accuracy, Invalid Rate, and qualitative analysis of substituted assumptions (e.g., lexicographic defaults).
• Key experimental observations:
  • Prompt framing affects behavior: MCQ increases explicit indeterminacy reporting but can induce over-abstention in some models.
  • Assisted/code-execution helps but improvements are primarily brute-force or heuristic search and fail to scale to larger markets.

Implications for AI Economics

• Reliability of LLM-based agents in economic settings is fragile:
  • Preference aggregation, recommender systems, and agentic decision-making that rely on LLMs may produce spurious, unjustified decisions when inputs are under-specified or when desired solution concepts are infeasible.
  • Incorrect or non-existent matchings/allocation outputs can violate axiomatic properties (e.g., stability, core, Pareto), producing unfair or manipulable outcomes in marketplaces and platforms.
• Alignment and coordination risks:
  • Models that silently impose assumptions (lexicographic or heuristic tie-breakers) can systematically bias social outcomes without transparency, undermining fairness and accountability in collective decision processes.
  • Poor abstention calibration risks overconfident actions in high-stakes economic settings (automated negotiations, matching platforms, mechanism deployment).
• Practical recommendations for deployments and designers:
  • Explicit indeterminacy signaling: interfaces and prompts should include clear options for “undetermined / insufficient information,” and downstream systems must treat determinate model outputs as provisional unless algorithmically verified.
  • Hybrid architectures: combine LLM reasoning with formal combinatorial solvers or certified algorithms for verification and construction of economic solutions (use LLMs for interpretation/translation but rely on algorithmic backstops for feasibility and axiomatic checks).
  • Uncertainty representation: develop and standardize uncertainty/abstention reporting for preference reasoning (multi-valued logics, calibrated confidence, or explicit provenance of assumptions).
  • Benchmarking and stress-testing: adopt indeterminacy-aware benchmarks (like those in this paper) when validating LLMs for economic applications; include verification tasks and structural infeasibility cases.
• Research directions:
  • Improve models’ internal representations for partial information and ties (reasoning that explicitly models unknowns instead of substituting heuristics).
  • Better integration of symbolic/combinatorial methods with LLMs to ensure correctness and scalability.
  • Explore training and prompting strategies that reduce substitution biases and improve abstention calibration without inducing systematic over-abstention.
• Policy and governance:
  • For platforms using LLMs in allocation/matching or collective decision contexts, require transparent reporting of assumptions and verification checks; when possible, mandate algorithmic audits for properties like stability or Pareto optimality.