Algorithmic Contract Design

Contract design captures situations where a principal delegates the execution of a costly task to an agent. To complete the task, the agent chooses an action from a set of costly actions. The principal can only observe the outcome, which is stochastically determined by the chosen action. The principal incentivizes the desired action through a contract, that specifies payments based on the observed outcome. In this talk, I will survey several papers on combinatorial contracts, which highlight different sources of complexity that arise in contract design. The first (FOCS’21,SODA’24) is where the agent can choose any subset of a given set of actions; the second (STOC’23) is where the principal motivates a team of agents. We provide (approximation) algorithms and hardness results for the optimal contract problem in these scenarios.

Based on joint work with Paul Duetting, Tomer Ezra, Yoav Gal Tzur and Thomas Kesselheim.

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.