Mechanism Design for Large Language Models
Reference: Dütting, Mirrokni, Paes Leme, Xu & Zuo (2023). Mechanism Design for Large Language Models. WWW 2024 (Best Paper). arXiv:2310.10826 (Google Research; University of Chicago). URL.
Summary
This paper opens the field of mechanism design over LLM-generated content. The motivating use case is multi-advertiser ad-creative generation: several advertisers each have preferences over what a stochastic LLM produces for a given query, and the platform must aggregate these preferences into a single piece of content while charging payments in a way that is incentive-compatible. Classical mechanism design assumes each agent has an explicit valuation function over outcomes; here outcomes are token sequences and valuations are encoded as the agents’ own LLMs — there is no compact valuation form to plug into VCG.
Dütting et al. propose a token-level auction that solves this. At each generation step, every agent submits a one-dimensional bid; the platform aggregates the agents’ next-token preferences using their own LLMs together with the bids; the chosen token is the one that maximises the aggregate. Payments are charged on a token-by-token basis using a generalised second-price-like rule. They define two natural incentive properties over distributions of generated content and prove their equivalence to a monotonicity condition on output aggregation — analogous to the Myerson monotonicity / payment characterisation for single-item auctions. This equivalence enables a clean second-price-style payment rule without requiring explicit valuation functions: the LLM-encoded preferences are sufficient.
The construction is supported by demonstrations on a publicly available LLM. The paper is now the canonical reference for “mechanism design where outcomes are LLM outputs and preferences are LLM-encoded” — a building block for the steerable agent markets of Virtual Agent Economies, the information-market substrates of Language Models Can Reduce Asymmetry in Information Markets, and the regret-aware market analyses of Do LLM Agents Have Regret.
Key Ideas
- Problem: auctioning LLM-generated content among multiple advertisers / agents whose preferences are themselves LLMs — no explicit valuation function available.
- Token-by-token auction: at each generation step, single-dimensional bids combine with LLM-encoded preferences to pick the next token.
- Output aggregation: the chosen token aggregates the agents’ next-token preferences weighted by bids — no need for a compact valuation form.
- Two incentive properties: formulated over distributions of generated content; jointly capture natural truthfulness desiderata.
- Monotonicity equivalence: the incentive properties hold iff output aggregation is monotone — a Myerson-style characterisation.
- Second-price design: the equivalence yields a generalised second-price payment rule, even absent explicit valuations.
- Practical demonstrations: validated on a publicly available LLM, suggesting the construction is implementable.
Connections
Conceptual Contribution
- Claim: Mechanism design extends naturally to the regime where outcomes are LLM-generated tokens and agent preferences are themselves LLMs. The classical machinery — Myerson monotonicity, second-price payments, truthfulness — survives, but is parameterised by output-aggregation monotonicity rather than by explicit valuation functions.
- Mechanism: Token-by-token auction; single-dimensional bids per token; output aggregation via agents’ own LLM preferences weighted by bids; two incentive properties shown equivalent to output-aggregation monotonicity; second-price-style payment rule recovered without explicit valuations; LLM demonstrations.
- Concepts introduced/used: LLM Auction, Token-Level Mechanism, Output Aggregation, Monotone Aggregation, Vickrey Auction, Myerson’s Lemma, Incentive Compatibility, Mechanism Design
- Stance: formal mechanism design with implementation
- Relates to: Generalises the Vickrey / Myerson tradition (Counterspeculation Auctions and Competitive Sealed Tenders) to LLM-generated outcomes; provides the formal layer underlying the auction-mechanism discussion in Virtual Agent Economies; foundational dependency for Language Models Can Reduce Asymmetry in Information Markets and the incentive-compatibility analyses behind NDAI Agreements; the agents’ assumed rationality must approximate no-regret for the equilibrium analysis to apply — see Do LLM Agents Have Regret.