EUVIMEDEUVIMED entdecken
Crossref

Multi-Agent Contracts

Paul Dütting, Tomer Ezra, Michal Feldman, Thomas Kesselheim

Journal of the ACM · 30.04.2026 · 73 (2) · 1-37

DOI: 10.1145/3801154 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of the ACM, online erschienen am 22.04.2026. Verfasst von Paul Dütting und 3 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 54 Literaturangaben. Gefördert von: HORIZON EUROPE European Research Council, Israeli Science Foundation Breakthrough Program, NSF-BSF.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study a natural combinatorial single-principal multi-agent contract design problem, in which a principal motivates a team of agents to exert effort toward a given task. At the heart of our model is a reward function , which maps the agent efforts to an expected reward of the principal. We seek to design computationally efficient algorithms for finding optimal (or near-optimal) linear contracts for reward functions that belong to the complement-free hierarchy. Our first main result gives constant-factor approximation algorithms for submodular and XOS reward functions, with value oracles for submodular reward functions and value and demand oracles for XOS reward functions. It relies on an unconventional use of “prices” and (approximate) demand queries for selecting the set of agents that the principal should contract with, and exploits a novel scaling property of XOS functions and their marginals, which may be of independent interest. As our second main result, we show that constant approximation is the best we can get for submodular reward functions, even with both value and demand oracles. For the larger class of subadditive reward functions, we establish an \(\Omega (\sqrt {n})\) impossibility for settings with n agents. A striking feature of this impossibility is that it applies to subadditive functions that are constant-factor close to submodular. This rapid degradation presents a surprising departure from previous literature, e.g., on combinatorial auctions, where approximation guarantees tend to deteriorate more gracefully.

Förderung

  • HORIZON EUROPE European Research Council
  • Israeli Science Foundation Breakthrough Program
  • NSF-BSF
  • Amazon Research Awards

Zitieren

APA

Dütting, P., Ezra, T., Feldman, M., & Kesselheim, T. (2026). Multi-Agent Contracts. Journal of the ACM, 73(2), 1-37. https://doi.org/10.1145/3801154

Vancouver

Dütting P, Ezra T, Feldman M, Kesselheim T. Multi-Agent Contracts. Journal of the ACM. 2026;73(2):1-37. doi:10.1145/3801154

BibTeX
@article{Dtting2026,
  author = {Dütting, Paul and Ezra, Tomer and Feldman, Michal and Kesselheim, Thomas},
  title = {Multi-Agent Contracts},
  journal = {Journal of the ACM},
  year = {2026},
  volume = {73},
  number = {2},
  pages = {1--37},
  doi = {10.1145/3801154}
}
Kostenlos starten →