Algorithmic Contract Theory: A Survey
By Paul Dütting, Google Research, Switzerland, duetting@google.com | Michal Feldman, Tel Aviv University, Israel, mfeldman@tauex.tau.ac.il | Inbal Talgam-Cohen, Tel Aviv University, Israel and Technion—Israel Institute of Technology, Israel, italgam@tauex.tau.ac.il
Abstract
A contract is an economic tool used by a principal to incentivize one or more agents to exert effort on her behalf, by defining payments based on observable performance measures. A key challenge addressed by contracts — known in economics as moral hazard — is that, absent a properly set up contract, agents might engage in actions that are not in the principal’s best interest. Another common feature of contracts is limited liability, which means that payments can go only from the principal — who has the deep pocket — to the agents.
With classic applications of contract theory moving online, growing in scale, and becoming more data-driven, tools from contract theory become increasingly important for incentiveaware algorithm design. At the same time, algorithm design offers a whole new toolbox for reasoning about contracts, ranging from additional tools for studying the tradeoff between simple and optimal contracts, through a language for discussing the computational complexity of contracts in combinatorial settings, to a formalism for analyzing data-driven contracts.
This survey aims to provide a computer science-friendly introduction to the basic concepts of contract theory.We give an overview of the emerging field of “algorithmic contract theory” and highlight work that showcases the potential for interaction between the two areas. We also discuss avenues for future research.
Algorithmic Contract Theory: A Survey
A contract is an economic tool used by a principal to incentivize one or more agents to exert effort on her behalf, by defining payments based on observable performance measures. A key challenge addressed by contracts, known in economics as moral hazard, is that, absent a properly set up contract, agents might engage in actions that are not in the principal’s best interest. Another common feature of contracts is limited liability, which means that payments can go only from the principal - who has the deep pocket - to the agents. With classic applications of contract theory moving online, growing in scale, and becoming more data-driven, tools from contract theory become increasingly important for incentive-aware algorithm design. At the same time, algorithm design offers a whole new toolbox for reasoning about contracts, ranging from additional tools for studying the tradeoff between simple and optimal contracts, through a language for discussing the computational complexity of contracts in combinatorial settings, to a formalism for analyzing data-driven contracts.
This monograph provides a computer science-friendly introduction to the basic concepts of contract theory. An overview of the emerging field of “algorithmic contract theory” are presented, and work that showcases the potential for interaction between the two areas are highlighted. Future research is also discussed.
The monograph is written for students, researchers, and professionals who work in the contract theory domain of Computer Science, but it also has a wider appeal.
