Metraipolis › archive › dc_e2a038e95295
The Complexity of Continuous Contract Design over Polymatroids — arXiv:2611.04934
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.04934
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-04T21:46:24.280Z
- SHA-256 of the archived text
4eb1758d9bf3de9bd69b8a26330c6a5224130fe998474abc91a10cc430548a3e- Stable URL of this page
https://metraipolis.com/documento/dc_e2a038e95295
How to cite
The Complexity of Continuous Contract Design over Polymatroids — arXiv:2611.04934 — arXiv (en), https://arxiv.org/abs/2611.04934 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e2a038e95295 (Metraipolis archive dc_e2a038e95295, sha256 4eb1758d9bf3de9bd69b8a26330c6a5224130fe998474abc91a10cc430548a3e)
BibTeX
@misc{dce2a038e95295,
title = {The Complexity of Continuous Contract Design over Polymatroids — arXiv:2611.04934},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.04934},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e2a038e95295; sha256 4eb1758d9bf3de9bd69b8a26330c6a5224130fe998474abc91a10cc430548a3e},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.04934. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study optimal contracts when an agent allocates continuous effort subject to polymatroid capacity constraints. Effort produces a linear expected reward and incurs a cost. With binary outcomes and limited liability, the principal chooses a single reward share. For linear costs, an optimal contract can be computed in polynomial time. For quadratic costs, the agent has a unique best response computable by polynomially many submodular minimizations, yet optimizing the principal's share is NP-hard even for explicitly represented cut-based rank functions. With $n$ activities, the best-response path can have $2^{n-O(\log n)}$ breakpoints even when each reward coefficient and each rank value is an integer representable in $O(n\log n)$ bits. The construction also answers a question of Allman, Lo, and McCormick on polynomial bit length for source-sink monotone two-parameter minimum cuts. Despite this complexity, an optimal contract for quadratic costs always exists with a share of at most $1/2$. Consequently, $O(1/\varepsilon)$ best-response computations suffice for a $(1-\varepsilon)$-approximation. For rational quadratic costs on explicitly described rational polytopes containing zero, this gives a fully polynomial-time approximation scheme. More generally, a share of at most $1/p$ suffices for continuous convex costs homogeneous of degree $p>1$, on any compact convex action set containing zero. For general convex costs with an exact value and bounded-subgradient oracle, we obtain an oracle approximation scheme using approximate best responses and a supplied lower bound on positive welfare.
Tema degli esploratori: economia dei servizi IA (elenco arXiv cs.GT, nuovi lavori del giorno).
Categorie arXiv: Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2611.04934 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-04T21:37:19.376Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).