  In the classical principal-agent problem, a principal must design a contract
to incentivize an agent to perform an action on behalf of the principal. We
study the classical principal-agent problem in a setting where the agent can be
of one of several types (affecting the outcome of actions they might take).
This combines the contract theory phenomena of "moral hazard" (incomplete
information about actions) with that of "adverse selection" (incomplete
information about types).
  We examine this problem through the computational lens. We show that in this
setting it is APX-hard to compute either the profit-maximizing single contract
or the profit-maximizing menu of contracts (as opposed to in the absence of
types, where one can efficiently compute the optimal contract). We then show
that the performance of the best linear contract scales especially well in the
number of types: if agent has $n$ available actions and $T$ possible types, the
best linear contract achieves an $O(n\log T)$ approximation of the best
possible profit. Finally, we apply our framework to prove tight worst-case
approximation bounds between a variety of benchmarks of mechanisms for the
principal.
