Abstract:

Principal-agent problems model scenarios where a principal aims at incentivizing an agent to take costly, unobservable actions through the provision of payments. Such interactions are ubiquitous in several real-world applications, ranging from blockchain to the delegation of machine learning tasks. In this paper, we initiate the study of hidden-action principal-agent problems under approximate best responses, in which the agent may select any action that is not too much suboptimal given the principal's payment scheme (a.k.a. contract). Our main result is a polynomial-time algorithm to compute an optimal contract under approximate best responses. This is perhaps surprising, as computing an optimal commitment under approximate best responses is known to be computationally intractable in Stackelberg games. We also investigate the learnability of contracts under approximate best responses, by providing a no-regret learning algorithm for a natural application scenario where the principal does not know anything about the environment.

Lay Summary: Contract design provides a powerful framework for capturing the strategic interaction between a principal and an agent, where the principal aims to incentivize the agent to undertake desirable actions. Yet, in many real-world settings, agents may choose actions that are suboptimal—or even deliberately misaligned—with the principal’s objectives, leading to significant consequences for the principal. In this paper, we formalize and characterize such scenarios by allowing the agent to take actions that are suboptimal for them by at most a parameter $\delta > 0$. We provide a polynomial-time algorithm to compute an optimal contract in this setting and a no-regret learning algorithm for cases where the principal has no prior knowledge of the environment.