Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2404.03476 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- 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 $I^M$, we construct a single-parameter instance $I^S$ such that any $β$-approximate contract (resp. menu of contracts) of $I^S$ can in turn be converted to a $(β-ε)$-approximate contract (resp. menu of contracts) of $I^M$. The reduction is in time polynomial in the input size and $\log(\frac{1}ε)$; moreover, when $β= 1$ (i.e., the given single-parameter solution is exactly optimal), the dependence on $\frac{1}ε$ 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.