Algorithmic Contract Design

Abstract: We explore the framework of contract design through a computational perspective. Contract design is a fundamental pillar of microeconomics, addressing the essential question of how to incentivize people to work. The significance of contract design was acknowledged by the Nobel Prize awarded to Hart and Holmström, and it applies to various real-life scenarios, such as determining bonuses for employees, setting commission structures for sales representatives, and designing payment schemes for influencers promoting products. While contract design has been extensively studied from an economic perspective, this talk will examine it from a computational viewpoint. Specifically, we introduce combinatorial extensions of classic contract design models, where a principal delegates tasks to one or multiple agents. The agents have sets of potential actions they can take to complete the task, and the chosen actions by the agents stochastically determine the success of the task. We analyze the structure and computational aspects of these models, and present algorithms that provide (approximately) optimal guarantees.