Decentralized auctions enable teamwork among strategic AI agents
Decentralized LLM Workflows via Sequential Auctions
Computer Science and Game TheoryArtificial IntelligenceMultiagent Systems
Summary
Solving complex tasks with many steps can be hard when lots of independent agents work together. The authors show how using auctions where agents bid in a sequence helps these agents coordinate well, even when they compete imperfectly. They find that if there is too much or too little competition, the system fails. But in between, agents learn to bid smartly to make some profit while still getting the job done well. The authors tested different bidding strategies and auction types and found this middle ground keeps agents motivated and tasks successful.
What this means in practice
- •For distributed ai developers: Coordinate multiple AI agents to complete complex workflows by setting up auctions that balance competition and cooperation effectively.
- •For cloud service operators: Use decentralized auction-based marketplaces to allocate multi-step tasks among self-interested agents, improving system scalability and cost efficiency.
Authors
Ian Gemp, Shubhendu Trivedi, Adam Fisch, Fantine Huot, Michael Kaisers, Mirella Lapata, William W. Cohen, Alekh Agarwal, Kate Larson, Jacob Eisenstein
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.