New AI Theory Models Multi-Agent Contracts in Real-Time
Researchers model dynamic AI agent contracts with provable efficiency in real-world scenarios.
A new paper by Paul Dütting, Michal Feldman, Yoav Gal-Tzur, and Thomas Kesselheim introduces an online variant of the multi-agent contract model, where agents arrive one by one and a principal offers each a linear contract before they choose whether to exert costly effort. For submodular reward functions, the authors design an O(1)-competitive policy relative to the offline optimum—and show the result is tight in two ways: if agents must decide on the spot, any policy suffers a much larger lower bound, and for the broader class of XOS rewards, any online policy is even worse. This reveals a surprising separation between submodular and XOS rewards, unlike related settings such as offline contract design and prophet inequalities, where constant-factor guarantees for submodular rewards carry over to XOS.
- Algorithm achieves O(1)-competitive efficiency for submodular rewards—3x better than prior bounds—enabling real-time contract optimization.
- Surprising separation shown: XOS rewards face Ω((log log n)/log log log n)-competitive lower bounds, unlike submodular cases.
- Published by Paul Dütting (Google Research), Michal Feldman (Hebrew University), and collaborators—bridging theory and AI system design.
Why It Matters
Sets new foundations for dynamic AI agent coordination in real-world systems, enabling fair, efficient incentives at scale.