Catching Misread Design Briefs in LLM-Assisted Mechanism Design

Mechanism design is the craft of writing the rules of an auction, vote, or allocation so that participants do best by reporting truthfully. Automated mechanism design turns this into an optimization problem. Once the participant types, their probabilities, the possible outcomes, and the utilities are written down exactly, a linear program can return the provably optimal truthful randomized mechanism for small, finite settings. The hard step in practice is not the solve. It is the writing-down: someone must turn an informal design brief ("two schools, three student types who can only exaggerate in one direction, maximize matched welfare") into an exact formal specification. This translation is what one would want a large language model (LLM) to do. It is also the kind of task where LLMs fail quietly. They drop a constraint, misread who can misreport as whom, or flip an inequality, and the solver then returns a mechanism that is perfectly optimal for the wrong problem.

We propose a formalize-then-solve pipeline for mechanism design. The LLM only translates a brief into a small executable specification. A fixed compiler and solver produce the mechanism, and an exact checker enforces truthfulness. The new ingredient catches errors that no solver can see. The pipeline automatically derives a family of related briefs from the original, for example by relabeling bidders, rescaling money, tightening a constraint, or collapsing to a special case with a known answer. The LLM formalizes each one independently, and the system then checks relations between the solved optima that economic theory guarantees must hold. A violated relation is a proof that at least one translation is wrong, and it points to which one. The bet is that an LLM's misreadings are surface-dependent, so they rarely survive a change of surface while still agreeing with theory.

Core Claim

Exact solvers verify a mechanism against its specification. They cannot verify the specification against the designer's intent. We claim that theorem-backed consistency checks across automatically varied briefs (metamorphic checks, borrowing the software-testing term for tests that compare outputs across transformed inputs) detect and help repair most LLM specification errors in finite mechanism design problems. They should do so at a higher rate than spending the same budget on repeated sampling and voting, because voting only filters out errors that vary randomly between samples, while metamorphic variation exposes errors that are systematic.

The claim is grounded in two findings from the reasoning literature. Yang et al. show on ConsisEval that models which solve a hard problem often fail an easier variant of the same problem, and that even GPT-4 Turbo reaches only a 92.2% consistency score. That inconsistency is usually treated as a defect to measure. We turn it into a detection signal. Al-Khalili, Howell, and Klakow show that LLM-written programs often reach correct final answers through unsound logic. This means "the code ran and produced a plausible mechanism" is weak evidence that the formalization is correct, and an independent check is needed.

Relation to Prior Work

The closest work is AMD-LLM, which uses an LLM inside an evolutionary loop to write mechanism code. A deterministic "fixing" wrapper then enforces monotonicity and truthful payments. That paper supplies the lesson we build on: the LLM should not be trusted with hard constraints. Its problem setting differs from ours in a way that matters. There the setting is fixed and formal (multi-item redistribution under stated valuation distributions), and the LLM searches over rules. Here the rule search is done exactly by a solver, and the LLM's job, and its failure point, is reading the setting itself.

ASTRA couples an LLM with a linear program for negotiation. In ASTRA the LLM only tunes one weight inside a human-written program, and the authors explicitly name LLM-authored formulations as future work. Our proposal takes up that future work, together with the safeguard ASTRA does not need.

The classical automated mechanism design results supply the solver side and constrain the scope:

  • Conitzer and Sandholm and Sandholm and Conitzer show that optimal randomized mechanisms over finite types are a polynomial linear program, while deterministic ones require integer programming. This is what makes exact ground truth affordable.
  • Zhang and Conitzer give the linear program for finite-horizon dynamic mechanisms and prove hardness as the horizon grows. We therefore stay at small horizons.
  • Zhang, Cheng, and Conitzer treat partial verification, where agents can only make certain misreports. They show deterministic design reduces to a min-cut in a special case, which gives us an independent solver to cross-check against.

Two lines of work on making LLMs reason through decomposition or multiple agents motivate the design without replacing it:

  • Divide-and-Conquer prompting argues that independent sub-problems in separate contexts limit error accumulation. Our variant briefs are formalized in separate contexts for the same reason.
  • Debate methods (Debate4MATH, UMAD) and the Bayesian Decoding Game all document that agents converge on shared falsehoods. That is exactly the correlated-error failure that makes voting insufficient.

Where those methods arbitrate by agreement, we arbitrate by theorems that do not depend on any agent's opinion.

Research Program

The system has four parts.

The specification language. This is a deliberately narrow, typed format. It lists agents, finite type sets, a prior, an outcome set, utility tables or functions, an objective (expected revenue or welfare), the set of permitted misreports (full by default, restricted under partial verification), and flags for individual rationality, dominant-strategy versus Bayesian truthfulness, budget balance, and determinism.

The compiler and checker. A fixed compiler turns any valid specification into the standard linear or integer program. An exact checker enumerates every type and every permitted misreport to confirm that the returned mechanism is truthful and individually rational under that specification.

The relation library. This is a library of transformations of briefs, each paired with a relation between optima that is a theorem rather than a heuristic:

  • Relabeling agents or types leaves the optimal value unchanged.
  • Multiplying all money quantities by a constant multiplies revenue by that constant.
  • Adding a constraint (dominant-strategy instead of Bayesian truthfulness, adding budget balance, requiring determinism) cannot raise the optimum.
  • Enlarging the set of permitted misreports cannot raise the optimum.
  • Adding a zero-probability type changes nothing.
  • Specializing to a single bidder and single item must produce a value achievable by a posted price.
  • Specializing to the identical-preference partial-verification case must match the min-cut answer of Zhang, Cheng, and Conitzer.

The transformed briefs are generated by rewriting the original text with an LLM. We then confirm by hand, on a development set, that the rewrites preserve meaning.

The repair loop. When a relation fails, the system identifies the smallest set of specifications whose re-formalization would restore all relations. It re-queries the LLM on those briefs, showing which relation failed but not what the correct answer is, and stops when all relations hold or the budget runs out.

The benchmark. No existing benchmark tests natural-language-to-mechanism formalization, so we build one: roughly two hundred design briefs with author-written ground-truth specifications. They span six families drawn from the file's settings:

  • single-item auctions with discrete priors;
  • the multi-item redistribution settings of AMD-LLM;
  • classification with partial verification;
  • small-horizon dynamic mechanisms;
  • money-free facility location;
  • small two-sided matching instances in the spirit of Narasimhan, Agarwal, and Parkes.

Briefs come in plain and distractor-laden phrasings, following the ConsisEval perturbations of Yang et al.. The primary metric is end-to-end correctness: the fraction of briefs whose final mechanism is truthful and individually rational under the ground-truth specification and attains the ground-truth optimum within solver tolerance. Secondary metrics are specification-level exact match, the error detection rate of the checks, the false alarm rate, and LLM tokens spent.

Baselines

Direct answer (naive reference). The LLM is asked, with chain-of-thought, to state the optimal mechanism and its value directly. This measures how far unaided reasoning gets. We expect it to be poor on anything beyond textbook cases, consistent with the self-planning failures Cai et al. report on CodeStepsEval, where self-generated plans pushed code quality below the no-plan baseline.

End-to-end program writing. The LLM writes the full optimization program, including enumerating truthfulness constraints, and runs it with a solver. This is the most natural "LLM as formulator" approach and the one ASTRA's authors propose. It tests whether our specification-plus-compiler split matters.

Specification plus compiler without checks. The same pipeline as ours with the relation library removed. This is the key ablation: any gain over it is attributable to the metamorphic checks alone.

Self-consistency voting at matched budget (strongest competitor). We sample as many independent specifications of the original brief as our method spends on variants and repairs, solve each, and return the mechanism with the most common optimal value. It is the strongest competitor because it uses the same solver, the same model, and the same tokens, and repeated sampling with aggregation is the standard, well-tuned remedy for LLM reasoning errors.

Checker-feedback repair without variants. The checker's counterexamples are fed back to the LLM, in the style of counterexample-guided synthesis, but no transformed briefs are used. This isolates whether variation in the brief, rather than feedback per se, does the work.

AMD-LLM on the redistribution family. We run AMD-LLM where it applies, as a reference for rule search with a fixer. On multi-item VCG redistribution that paper reports a score of 0.5838 for evolved code, against 0.4935 for manual baselines and 0.6254 for RegretNet. For instances small enough to enumerate, the exact linear program optimum should be at least as high as any of these by construction, provided the specification is right. No reported result was found on Lacuna for any method on natural-language brief formalization, so our benchmark numbers will be the first.

Fairness protocol. All LLM baselines use the same models (one open model of about 70B parameters and one frontier API model), the same prompts for shared components, the same solver, and token budgets matched to within ten percent. Prompts are tuned on the same development split. Beating the voting baseline means a statistically significant gain in end-to-end correctness on the held-out split at matched tokens, with the largest gain expected on distractor-laden briefs.

Why not just…?

Why not just write the linear program by hand and skip the LLM? For a single fixed setting, an expert writing the specification is the right answer, and our ground truth is exactly that. The proposal targets the regime where briefs are many, informal, and written by non-specialists, and where the cost is expert time per brief. Our measured outcome is whether LLM translation plus checks reaches expert-level correctness. If it does not, the benchmark will say so plainly.

Why not just sample many specifications and take a majority vote? This is the real threat. If LLM errors were independent across samples, voting would match or beat us at equal cost. The debate literature suggests they are not: Zhang and Zang prove that consensus games admit equilibria on false answers, and the same misreading of "can only under-report" will recur across samples of one phrasing. The matched-budget comparison settles this. We also report how correlated errors are across samples. If correlation is low and voting wins, we will conclude that the checks matter only for distractor-heavy briefs, or not at all.

Why not just let the LLM write the mechanism or the whole program directly, as AMD-LLM does? AMD-LLM itself needed an external fixer because the model could not hold the constraints. Al-Khalili et al. report about 25% more unsound programs on harder math even when execution looks fine. The end-to-end baseline measures how much accuracy is lost when constraint enumeration is left to the model rather than the compiler.

Why not just feed the exact checker's counterexamples back to the LLM? The checker certifies truthfulness relative to whatever specification the LLM wrote, so it is blind to a misread brief. The checker-feedback baseline should therefore fix compile-level slips but not semantic ones. Comparing its error profile with ours on semantically seeded errors will show this directly.

Proposed Experiments

Detection test (decisive). We take ground-truth specifications and inject the error types we expect from LLMs: a dropped misreport, a swapped prior, a missing participation constraint, a sign error in utility, and a wrongly assumed determinism. We then measure what fraction the relation library flags. This tests the checks in isolation from LLM behavior. If detection is below about half, the core claim fails, regardless of end-to-end numbers. Because every relation is a theorem, any false alarm on correct specifications indicates a solver-tolerance or rewrite bug, and we report these separately.

Main comparison. We compare end-to-end correctness against all baselines on the held-out benchmark at matched tokens, broken down by family and by plain versus distractor phrasing. The prediction is that our margin over voting grows with distractors and with family complexity (partial verification and dynamic briefs over single-item auctions).

Ablation over relations. We remove one relation class at a time to see which theorems carry the detection. This tells future users which checks are worth building for new domains.

Hard-to-easy probe. We measure how often the model formalizes a complex brief correctly but its simplified variant incorrectly, a mechanism-design analogue of the Yang et al. paradox. This tests whether the inconsistency that powers detection is actually present in this domain.

Scope limits. All instances stay within exact linear or integer program reach, with small type sets and dynamic horizons of a few periods, per the hardness results of Zhang and Conitzer. Extending the checks to parameterized families such as the affine maximizers of Sandholm and Likhodedov, where only local optima are available and relations between optima weaken to relations between bounds, is left as the natural next step.