Decentralized LLM Workflows via Sequential Auctions

Ian Gemp; Shubhendu Trivedi; Adam Fisch; Fantine Huot; Michael Kaisers; Mirella Lapata; William W. Cohen; Alekh Agarwal

cs.GTOct 15, 2026

Decentralized LLM Workflows via Sequential Auctions

Authors: Ian Gemp, Shubhendu Trivedi, Adam Fisch, Fantine Huot, Michael Kaisers, Mirella Lapata, William W. Cohen, Alekh Agarwal,

Organizations: Google DeepMind · Google Research · University of Waterloo

Abstract

We present a scalable framework for solving multi-step tasks through a decentralized market of self-interested agents. Prior theoretical work demonstrated that agents organized through sequential auctions can converge to a globally optimal policy in a Markov decision process (MDP), but relied on the restrictive assumption of the existence of perfect clones as a model of perfect competition. In reality, exact clones drive agent profit to zero, violating the natural risk-reward incentives of participants. Conversely, we empirically demonstrate that the opposite extreme, absence of competition, also leads to market failure and value extraction collapse. Between these two extremes, we investigate how heterogeneous agents can survive in markets that span the critical middle ground of imperfect competition. To be profitable, agents learn to strategically shade bids to secure positive individual profit margins, while still ensuring that the marketplace functions effectively enough so that collaborative tasks posed by market consumers can still be solved. We formulate and evaluate four bidding algorithms (Mirror Descent, Thompson Sampling, Bayes-Optimal, and PPO) across three auction protocols (1st-Price, 2nd-Price, and Credit-Conserving Vickrey). Across a diverse set of domains, we demonstrate that imperfect competition successfully sustains necessary agent profit margins while maintaining high task success rates at low costs.

Figures & tables

Panel of Figure 1 — Figure 1: Translation Domain Validation: ( 1(a) ) The task graph showing inference costs (black) and learned Vickrey bids (blue, italic; mean $\pm$ std dev). Downstream bids reflect task sampling probabilities (e.g., En $\to$ Ja expects $0.48$ because Task 1 is sampled $2/3$ of the time). The upstream Sp $\to$ En bid ( $0.88$ ) accurately approximates the downstream expected value minus local costs ( $0.48+0.38-0.01=0.85$ ). ( 1(b) ) Success rate increases and stabilizes across all auctions under increasing market density. Competitors are differentiated by cost $c=c_{b}(1+t)$ with $t\sim U(-0.5,0.5)$ and base costs $c_{b}$ listed in the graph. Curves are means over $3$ independent trials and shaded regions span $\pm 1$ standard deviation; both are computed on a trailing $101$ -episode rolling average.

Panel of Figure 2 — Figure 2: Economic Viability on News Market: The decentralized market successfully sustains social welfare while delivering strictly positive cumulative profits to both individual agents and the platform. The per-agent cumulative profit is reported for Mirror Descent. Means and standard deviations are computed over $5$ trials.

Method	Success Rate (%)	Steps / Task	Cost / Task (¢)
ReACT ( Gemini-3.5-flash-lite )	$48.40\pm 2.79$	$3.23\pm 0.04$	$0.0348\pm 0.0004$
ReACT ( Gemini-3.1-pro-preview )	$78.80\pm 1.30$	$4.37\pm 0.12$	$1.0599\pm 0.3679$
Market (PPO, 1st-Price)	$40.00\pm 2.83$	$1.85\pm 0.12$	$0.0525\pm 0.0036$
Market (Mirror Descent, 1st-Price)	$\mathbf{73.40\pm 1.67}$	$\mathbf{3.12\pm 0.11}$	$\mathbf{0.1020\pm 0.0044}$

Table 1: News Market performance and inference cost per task (

1

{=}\

0.01$ ) including the assessor. All market participants use Gemini-3.5-flash-lite . Best market mechanism is shown in bold .

Method	Accuracy (se)	Cost
one-shot	$69.17\penalty\ {(\pm 1.44)}$	$0$
fixed $n=1$	$70.54\penalty\ (\pm 1.42)$	$1$
fixed $n=2$	$71.80\penalty\ (\pm 1.41)$	$2$
prompted	$72.59\penalty\ (\pm 1.39)$	$0.24$
auction	$74.83\penalty\ (\pm 1.36)$	$0.28$

Table 2: Test set performance on Omni-MATH with PPO. Sequential auctions achieve the highest overall accuracy, outperforming a prompted router at comparable cost (measured in number of refinements, which is monotonic in token use).

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 3: Translation Domain Scaling ( $N=4$ ). When the market density is increased to 4 competitors per edge, competitive pressure is sufficiently high that even the Thompson Sampling (TS) and Bayes-Optimal baselines are able to successfully discover profitable shading margins and sustain the market. This contrasts with the $N=2$ regime shown in the main text (Figure 1(b) , right panel), where only PPO and Mirror Descent exhibited the robustness required to stabilize the supply chain.

Panel of Figure 4 — Figure 4: Economic Viability on HotpotQA: The decentralized market successfully sustains social welfare while delivering positive cumulative profits to both individual agents and the platform. The per-agent cumulative profit is reported for Mirror Descent.

Method	Success Rate (%)	Steps / Task	Cost / Task ( $\times\$ 0.01$ )
ReACT ( Gemini-3.5-flash-lite )	$84.80\pm 1.10$	$2.82\pm 0.01$	$0.0418\pm 0.0254$
ReACT ( Gemini-3.1-pro-preview )	$91.20\pm 0.84$	$2.88\pm 0.06$	$1.6774\pm 1.2811$
Market (PPO, 1st-Price)	$58.00\pm 5.61$	$1.65\pm 0.08$	$0.2922\pm 0.0746$
Market (Mirror Descent, 1st-Price)	$\mathbf{85.00\pm 3.16}$	$\mathbf{2.37\pm 0.13}$	$\mathbf{0.3437\pm 0.0184}$

Appendix

Table 3: HotpotQA performance and inference cost per task including the assessor (in units of

\

0.01$ ). All market participants use Gemini-3.5-flash-lite . Best market mechanism is shown in bold .

Domain	Role	Prompt	Corpus
HotpotQA	Extractor	✗	✓
HotpotQA	Answerer	✓	✗
News Market	Publisher	✓	✓
News Market	Sales	✓	✗
Omni-Math	Generator	✓	✗
Omni-Math	Verifier	✓	✗

Appendix

Table 4: Sources of agent heterogeneity across domains. “Prompt” indicates distinct system prompts; “Corpus” indicates assignment to different document partitions.

Component / Corpus	Content & Bridging Entities
User Question	“Regarding the company that was publicly criticized by @TechCritic-0 for its software deployment practices, what is the specific relative risk percentage identified in the technical document that triggered the internal whistleblower investigation?”
Gold Answer	“The relative risk percentage identified in Study-0 (LUMINOS-ENG-772-0) is 22% .”
1. Social Media ( social_media ) Entry Anchor Match	[doc_id: social_luminos_fusion_latency_scandal] “ @TechCritic-0 : It is absolutely horrifying that Marcus Vane knew our safety was at risk just to hit a deployment deadline. I am literally shaking reading the 22% failure rate stat—if the car can’t see the pedestrian in time, the ‘fusion’ is just a fancy way to commit insurance fraud on our lives.” $\hookrightarrow$ Bridging Entity Unlocked: CEO name Marcus Vane .
2. News Media ( news_media ) Intermediate Hop	[doc_id: news_luminos_fusion_latency_scandal] “On August 12, 2024, Luminos-0 CEO Marcus Vane publicly addressed internal whistleblower reports suggesting that the company’s engineering leads were aware of the latency spikes documented in Study-0 since Q1. Despite internal warnings, the company proceeded with the wide-scale deployment of its ‘Fusion-V3’ software update…” $\hookrightarrow$ Bridging Entities Unlocked: Company Luminos-0 and Study-0 .
3. Technical Journal ( medical_journals ) Terminal Evidence Hop	[doc_id: journal_luminos_fusion_latency_scandal] “ Study-0 (Ref: LUMINOS-ENG-772-0 ) investigated the cross-modal temporal alignment of the Luminos-0 fusion stack. Testing under extreme lighting and weather conditions revealed a critical processing bottleneck… This delay correlates directly with a 22% increase in the relative risk of failing to classify dynamic pedestrians during rapid lighting transitions.” $\hookrightarrow$ Target Evidence Extracted: 22% relative risk in Study-0 (LUMINOS-ENG-772-0) .
4. Wikipedia ( wikipedia ) Background Context	[doc_id: wiki_luminos_fusion_latency_scandal] “ Luminos-0 is a Silicon Valley-based technology firm specializing in proprietary multi-modal sensor fusion architectures for Level 4 autonomous driving systems… Controversy emerged in mid-2024 following allegations that the company’s sensor fusion algorithms prioritized high-confidence object detection over real-time environmental updates…”

Appendix

Table 5: Complete document set and multi-hop resolution trace for Scenario

k=0

in the News Market benchmark. Bridging entities discovered at each step are highlighted in bold .

Agentic Workflows

Agentic workflows coordinate AI agents, tools, and humans across multi-step tasks, emphasizing reliable execution, efficiency, and oversight.

See all 218 papers

Markets, Not Planners: Decentralized Orchestration of LLM Agents with Private Information
Aug 24, 2026Xiao Liu, Haoyang Li, Songwei Li +4Multi-Agent Orchestration LLM Agent Orchestration
Knowledge Lab, University of Chicago · University of Virginia · Tsinghua University +2
Price of Anarchy of First-Price Auctions in Agentic Markets
Oct 14, 2026Shubhendu Trivedi, Jacob Eisenstein, Alekh Agarwal +3Price of Anarchy Mechanism Design
Google DeepMind · Google Research
MarketBench: Evaluating AI Agents as Market Participants
Apr 26, 2026Andrey Fradkin, Rohit KrishnanMulti-Agent Coordination LLM Agent Evaluation
Boston University and the MIT Initiative on the Digital Economy. · Independent Researcher.

Aug 24, 2026J/K move · Enter open · S save

Markets, Not Planners: Decentralized Orchestration of LLM Agents with Private Information

Xiao Liu, Haoyang Li, Songwei Li, Hongbo Fang+3

Knowledge Lab, University of Chicago · University of Virginia · Tsinghua University+2

Multi-Agent Orchestration LLM Agent Orchestration Multi-Agent Resource Allocation Mechanism Design

Open paper AskPDF arXiv

As LLM agents proliferate, built by different parties and with different capabilities and costs, orchestrating them is more like assembling labor across the economy than a computer calling a subroutine. Existing orchestration is typically centralized, with a single planner assigning every task, but this creates a bottleneck as agent pools grow, requires private information (e.g., agents' execution costs), and can easily be manipulated, such that a single inserted preference nearly doubles a favored agent's task share under a centralized LLM allocator. We introduce AgentLance, a repeated labor market in which agents bid on tasks using their private costs and self-maintained strategy notes, an allocator selects winners from bids and public reputation records, and a VCG-style payment rule rewards cost-aware bidding. Complex tasks are handled by hierarchical delegation: winning agents can decompose work and subcontract it through the same mechanism. Across mathematical reasoning, code generation, knowledge-intensive QA, and agentic tasks, AgentLance matches agents to their specializations, shifts work toward cheaper agents as cost sensitivity rises, and consistently outperforms single-model, centralized-orchestration, and market baselines. Diagnosing market failures, including inaccurate cost self-estimation and sub-optimal bidding, then correcting them in controlled experiments yields further gains, charting a path toward more efficient agent economies.

Abstract

Agentic Workflows

Explore similar work

Markets, Not Planners: Decentralized Orchestration of LLM Agents with Private Information

Price of Anarchy of First-Price Auctions in Agentic Markets

MarketBench: Evaluating AI Agents as Market Participants