ACM EC'19 Tutorial
24 June 2019, 8:30am-11:00am
Paul Duetting, London School of Economics
Inbal Talgam-Cohen, Technion
Algorithmic game theory (AGT) has been tremendously successful in bringing a computer science perspective to different fields of economics, with the field of auction and mechanism design a particularly big success. AGT has only been around for two decades, so naturally there remain other rich and well-developed areas of economics that have not yet been studied systematically from a computer science perspective. Contract theory (a.k.a. principal-agent or agency theory) is perhaps the most notable such area, and holds the promise of being the next big application area for AGT. The goal of this tutorial is to offer an introduction to the basic models of contract theory accessible to the broader AGT community, and to outline possible directions in which the CS perspective could advance our understanding of this field.
The tutorial is self-contained and no previous knowledge is required. Its first and foremost goal is to offer an introduction to the basic models and questions of contract theory, accessible to a non-specialist (e.g., the average EC attendee who is probably familiar with auctions, possibly familiar with signalling, but has not yet seriously considered contracts). We anticipate, however, that the tutorial could also be of interest to the seasoned (non-CS) specialist, who will learn about recent computational approaches to the economic theory.
Contract theory captures numerous social and economic interactions (applications range from set- ting up optimal compensation schemes for workers to designing optimal insurances), and it is one of the pillars of economic theory (pioneered by Kenneth Arrow in the 1960s, it was mainly driven by Oliver Hart and Bengt R. Holmström, who received the 2016 Nobel Memorial Prize in Economic Sciences in recognition for their contributions to this field). Research on contracting and delegation is gaining traction in the AGT community over the past few years [Babaioff et al., 2010, 2012; Babaioff and Winter, 2014; Ho et al., 2016; Kleinberg and Kleinberg, 2018; Kleinberg and Raghavan, 2019; Dütting et al., 2019]. There are at least two reasons for this trend: (1) More and more of the classic applications of contract theory are moving to online marketplaces (crowdsourcing platforms, platforms for hiring specialists, health and other insurances, marketing, supply chains, etc.), and so computer scientists have a natural interest in this topic. (2) Contract theory shares some of the “shortcomings” of the “classic” mechanism design and signalling literature such as non-consideration of computational aspects and a focus on optimal but possibly complex designs. It is exactly these shortcomings that have driven the AGT community over the past 15-20 years, and that have lead to a rich theory for addressing these types of questions for auctions and signalling. A natural question is whether such a theory can also be developed for contracts.
The first part of the tutorial will present the basic principal-agent model [Grossman and Hart, 1983; Hart and Holmström, 1986; Caillaud and Hermalin, 2000; Laffont and Martimort, 2002; Bolton and Dewatripont, 2004; Tadelis
and Segal, 2005; Royal Swedish Academy of Sciences, 2016], starting with the 2-action case as a warm-up, and providing many examples. The main question is that of characterizing the optimal contract. The role of mathematical
programming will be explained, together with constraints imposed in the literature to simplify the characterization. The importance of linear contracts will be discussed along with classic explanations for their ubiquity
in practice [Holmstrom and Milgrom, 1987]. Geometric intuition will be given where appropriate. Time allowing we will present central variations of the basic model, like delegation and incomplete contracts.
The second part of the tutorial will bring the attendee up to date on recent cutting-edge research, and present open research directions. In economics, arguably the most notable development in the past few years is the
breakthrough max-min (robustness) approach of Carroll [Carroll, 2015, 2019; Carroll and Meng, 2016b,a], which has interesting implications for other areas of AGT as well. In computer science, several research directions
have been initiated recently: combinatorial agents [Babaioff et al., 2012], contract complexity [Babaioff and Winter, 2014], models with learning [Ho et al., 2016], robustness and near-optimality of simple contracts
[Dütting et al., 2019], and contract design without money [Armstrong and Vickers, 2010; Khodabakhsh et al., 2018; Kleinberg and Kleinberg, 2018; Kleinberg and Raghavan, 2019].
Paul Duetting is an Associate Professor in the Department of Mathematics at London School of Economics. He received his PhD in Computer Science from EPFL Lausanne, advised by Monika Henzinger. After his PhD he was
a Postdoctoral Researcher with Tim Roughgarden at Stanford University and Eva Tardos at Cornell University, an LSE Fellow in Mathematics at London School of Economics, and a Senior Researcher at ETH Zurich. He was awarded
a Marie Curie Fellowship and a SNF Postdoctoral Fellowship, is an alumnus of both the German and the Swiss Academic Foundation, and has won a best paper award at EC’12.
Inbal Talgam-Cohen is an Assistant Professor in the Computer Science Department at the Technion – Israel Institute of Technology. She received her PhD in computer science from Stanford University working with Tim
Roughgarden, and her MSc from the Weizmann Institute advised by Uriel Feige. As a Marie Curie and I-CORE fellow she was hosted by Noam Nisan and Michal Feldman. Inbal’s recognitions include the Best Doctoral Dissertation
Award from ACM SIGecom, a Stanford Interdisciplinary Graduate Fellowship (Hsieh Family Fellow), and the Best Student Paper Award at ACM Conference on Economics and Computation (EC).
Mark Armstrong and John Vickers. 2010. A Model of Delegated Project Choice. Econometrica 78, 1 (2010), 213–244.
Moshe Babaioff, Michal Feldman, and Noam Nisan. 2010. Mixed Strategies in Combinatorial Agency. Journal of Artifficial Intelligence Research 38 (2010), 339–369.
Moshe Babaioff, Michal Feldman, Noam Nisan, and Eyal Winter. 2012. Combinatorial Agency. Journal of Economic Theory 147, 3 (2012), 999–1034.
Moshe Babaioff and Eyal Winter. 2014. Contract Complexity. In Proceedings of the 15th ACM Conference on Economics and Computation (EC’14). 911.
Patrick Bolton and Mathias Dewatripont. 2004. Contract Theory. The MIT Press, Cambridge, MA.
Bernard Caillaud and Benjamin E. Hermalin. 2000. Hidden-Information Agency. Retrieved from: http://faculty.haas.berkeley.edu/hermalin/mechread.pdf.
Gabriel Carroll. 2015. Robustness and Linear Contracts. American Economic Review 105, 2 (2015), 536–563.
Gabriel Carroll and Delong Meng. 2016. Robust Contracting with Additive Noise. Journal of Economic Theory 166 (2016), 586-604.
Gabriel Carroll and Delong Meng. 2016. Locally Robust Contracts for Moral Hazard. Journal of Mathematical Economics 62 (2016), 36-51.
Gabriel Carroll. 2019. Robustness in Mechanism Design and Contracting. Annual Review of Economics (2019). Forthcoming.
Paul Dütting, Tim Roughgarden, Inbal-Talgam Cohen. Simple versus Optimal Contracts. In Proceedings of the 20th ACM Conference on Economics and Computation (EC’19). Forthcoming.
Sanford J. Grossman and Oliver D. Hart. 1983. An Analysis of the Principal-Agent Problem. Econometrica 51, 1 (1983), 7–45.
Oliver Hart and Bengt Holmström. The Theory of Contracts. MIT Working Paper, 1983.
Bengt Holmström and Paul Milgrom. 1987. Aggregation and Linearity in the Provision of Intertemporal Incentives. Econometrica 55, 2 (1987), 303–328.
Chien-Ju Ho, Aleksandrs Slivkins, and Jennifer Wortman Vaughan. 2016. Adaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problems. Journal of Artifficial Intelligence Research 55 (2016), 317–359.
Ali Khodabakhsh, Emmanouil Pountourakis, and Samuel Taggart. 2018. Algorithmic Delegation. Working paper.
Jon Kleinberg and Manish Raghavan. 2019. How Do Classiffiers Induce Agents To Invest Effort Strategically. In Proceedings of the 20th ACM Conference on Economics and Computation (EC’19). Forthcoming.
Jon Kleinberg and Robert Kleinberg. 2018. Delegated Search Approximates E cient Search. In Proceedings of the 19th ACM Conference on Economics and Computation (EC’18). 287–302.
Jean-Jacques Laffont and David Martimort. 2002. The Theory of Incentives. Princeton University Press, Princeton, NJ, USA.
Steve Tadelis and Ilya Segal. 2005. Lectures in Contract Theory. (2005). Retrieved from: http://faculty.haas.berkeley.edu/stadelis/Econ_206_notes_2006.pdf.
The Royal Swedish Academy of Sciences. 2016. Oliver Hart and Bengt Holmström: Contract Theory. (2016). Retrieved from: https://www.nobelprize.org/uploads/2018/06/advanced-economicsciences2016-1.pdf.