Multi-Project Contracts
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912417214103552 |
|---|---|
| author | Alon, Tal Castiglioni, Matteo Chen, Junjie Ezra, Tomer Li, Yingkai Talgam-Cohen, Inbal |
| author_facet | Alon, Tal Castiglioni, Matteo Chen, Junjie Ezra, Tomer Li, Yingkai Talgam-Cohen, Inbal |
| contents | We study a new class of contract design problems where a principal delegates the execution of multiple projects to a set of agents. The principal's expected reward from each project is a combinatorial function of the agents working on it. Each agent has limited capacity and can work on at most one project, and the agents are heterogeneous, with different costs and contributions for participating in different projects. The main challenge of the principal is to decide how to allocate the agents to projects when the number of projects grows in scale.
We analyze this problem under different assumptions on the structure of the expected reward functions. As our main result, for XOS functions we show how to derive a constant approximation to the optimal multi-project contract in polynomial time, given access to value and demand oracles. Along the way (and of possible independent interest), we develop approximate demand queries for \emph{capped} subadditive functions, by reducing to demand queries for the original functions. Our work paves the way to combinatorial contract design in richer settings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_05705 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Multi-Project Contracts Alon, Tal Castiglioni, Matteo Chen, Junjie Ezra, Tomer Li, Yingkai Talgam-Cohen, Inbal Computer Science and Game Theory We study a new class of contract design problems where a principal delegates the execution of multiple projects to a set of agents. The principal's expected reward from each project is a combinatorial function of the agents working on it. Each agent has limited capacity and can work on at most one project, and the agents are heterogeneous, with different costs and contributions for participating in different projects. The main challenge of the principal is to decide how to allocate the agents to projects when the number of projects grows in scale. We analyze this problem under different assumptions on the structure of the expected reward functions. As our main result, for XOS functions we show how to derive a constant approximation to the optimal multi-project contract in polynomial time, given access to value and demand oracles. Along the way (and of possible independent interest), we develop approximate demand queries for \emph{capped} subadditive functions, by reducing to demand queries for the original functions. Our work paves the way to combinatorial contract design in richer settings. |
| title | Multi-Project Contracts |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2506.05705 |