EUVIMEDEUVIMED entdecken
Crossref

A Reduction from Multi-Parameter to Single-Parameter Bayesian Contract Design

Matteo Castiglion, Junjie Chen, Minming Li, Haifeng Xu, Song Zuo

SIAM Journal on Computing · 31.12.2026 · 55 (6) · 1312-1362

DOI: 10.1137/25m1748299 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 17.11.2026. Verfasst von Matteo Castiglion und 4 weiteren Autor:innen. Die Arbeit nennt 50 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The problem of contract design addresses the challenge of moral hazard in principal-agent setups. The agent exerts costly efforts that produce a random outcome with an associated reward for the principal. Moral hazard refers to the tension that the principal cannot observe the agent’s effort level and hence needs to incentivize the agent only through rewarding the realized effort outcome, i.e., the contract. Bayesian contract design studies the principal’s design problem of an optimal contract when facing an unknown agent characterized by a private Bayesian type. In its most general form, the agent’s type is inherently “multi-parameter” and can arbitrarily affect both the agent’s productivity and effort costs. In contrast, a natural single-parameter setting of much recent interest simplifies the agent’s type to a single value that describes the agent’s cost per unit of effort, whereas agents’ efforts are assumed to be equally productive. The main result of this paper is an almost approximation-preserving polynomial-time reduction from the most general multi-parameter Bayesian contract design (BCD) to single-parameter BCD. That is, for any multi-parameter BCD instance [Formula: see text], we construct a single-parameter instance [Formula: see text] such that any [Formula: see text]-approximate contract (resp., menu of contracts) of [Formula: see text] can in turn be converted to a [Formula: see text]-approximate contract (resp., menu of contracts) of [Formula: see text]. The reduction is in time polynomial in the input size and [Formula: see text]; moreover, when [Formula: see text] (i.e., the given single-parameter solution is exactly optimal), the dependence on [Formula: see text] can be removed, leading to a polynomial-time exact reduction. This efficient reduction is somewhat surprising because in the closely related problem of Bayesian mechanism design, a polynomial-time reduction from multi-parameter to single-parameter setting is believed to not exist. Our result demonstrates the intrinsic difficulty of addressing moral hazard in BCD, regardless of being single-parameter or multi-parameter. As byproducts, our reduction answers two open questions in recent literature of algorithmic contract design: (a) it implies that optimal contract design in single-parameter BCD is not in APX unless P = NP even when the agent’s type distribution is regular, answering the open question of [T. Alon, P. Dütting, and I. Talgam-Cohen, Proceedings of the 22 nd ACM Conference on Economics and Computation, 2021, pp. 52–69] in the negative; (b) it implies that the principal’s (orderwise) tight utility gap between using a menu of contracts and a single contract is [Formula: see text], where [Formula: see text] is the number of actions, answering the major open question of [G. Guruganesh, J. Schneider, and J. R. Wang, Proceedings of the 22 nd ACM Conference on Economics and Computation, 2021, pp. 563–582] for the single-parameter case.

Zitieren

APA

Castiglion, M., Chen, J., Li, M., Xu, H., & Zuo, S. (2026). A Reduction from Multi-Parameter to Single-Parameter Bayesian Contract Design. SIAM Journal on Computing, 55(6), 1312-1362. https://doi.org/10.1137/25m1748299

Vancouver

Castiglion M, Chen J, Li M, Xu H, Zuo S. A Reduction from Multi-Parameter to Single-Parameter Bayesian Contract Design. SIAM Journal on Computing. 2026;55(6):1312-1362. doi:10.1137/25m1748299

BibTeX
@article{Castiglion2026,
  author = {Castiglion, Matteo and Chen, Junjie and Li, Minming and Xu, Haifeng and Zuo, Song},
  title = {A Reduction from Multi-Parameter to Single-Parameter Bayesian Contract Design},
  journal = {SIAM Journal on Computing},
  year = {2026},
  volume = {55},
  number = {6},
  pages = {1312--1362},
  doi = {10.1137/25m1748299}
}
Kostenlos starten →