Theoretical Economics, Volume 13, Number 2 (May 2018)

Theoretical Economics 13 (2018), 553–578


Computational principal agent problems

Pablo D. Azar, Silvio Micali

Abstract


Collecting and processing large amounts of data is becoming increasingly crucial in our society. We model this task as evaluating a function f over a large vector x = (x1, . . . , xn), which is unknown, but drawn from a publicly known distribution X. In our model learning each component of the input x is costly, but computing the output f(x) has zero cost once x is known. We consider the problem of a principal who wishes to delegate the evaluation of f to an agent, whose cost of learning any number of components of x is always lower than the corresponding cost of the principal. We prove that, for every continuous function f and every ε > 0, the principal can— by learning a single component x1 of x—incentivize the agent to report the correct value f(x) with accuracy ε.

Keywords: Principal agent problems, computational complexity

JEL classification: D82,D86

Full Text:  PRINT  VIEW