2024/04/04 by Matteo Castiglioni, Castiglioni, Matteo, Junjie Chen +7 · 3 citations
Economics, Econometrics and Finance · #Law, Economics, and Judicial Systems #Insurance and Financial Risk Management
paper · pdf · doi:10.48550/arxiv.2404.03476
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 IM, we construct a single-parameter instance IS such that any β-approximate contract (resp. menu of contracts) of IS can in turn be converted to a (β-ε)-approximate contract (resp. menu of contracts) of IM. The reduction is in time polynomial in the input size and log(\frac1ε); moreover, when β= 1 (i.e., the given single-parameter solution is exactly optimal), the dependence on \frac1ε 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 Bayesian contract design, 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 [Alon et al. 2021] in the negative; (b) it implies that the principal's (order-wise) tight utility gap between using a menu of contracts and a single contract is Θ(n) where n is the number of actions, answering the major open question of [Guruganesh et al. 2021] for the single-parameter case.