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).