The paper focuses on principal-agent settings with succinctly described outcome space (exponentially large). The goal of the principal is to design a contract that maximizes its expected payoff. The authors show that for n > 2 actions this problem turns out to be NP-hard. For settings with a constant number of actions, the authors present a fully polynomial-time approximation scheme (FPTAS) for the separation oracle of the dual of the problem of minimizing the principal's payment to the agent, and use this subroutine to efficiently compute a delta-incentive-compatible (delta-IC) contract whose expected payoff matches or surpasses that of the optimal IC contract.
With an arbitrary number of actions, the authors prove that the problem is hard to approximate within any constant c. This inapproximability result holds even for delta-IC contracts where delta is a sufficiently rapidly-decaying function of c. On the positive side, the authors show that simple linear delta-IC contracts with constant delta are sufficient to achieve a constant-factor approximation of the "first-best" (full-welfare-extracting) solution, and that such a contract can be computed in polynomial time.
Here is the link to the paper : https://arxiv.org/abs/2002.12034
