Computational principal agent problems

Pablo Azar and Silvio Micali ()
Additional contact information
Silvio Micali: Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology

Theoretical Economics, 2018, vol. 13, issue 2

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 (search for similar items in EconPapers)
JEL-codes: D82 D86 (search for similar items in EconPapers)
Date: 2018-05-29
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://econtheory.org/ojs/index.php/te/article/viewFile/20180553/20884/614 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:the:publsh:1815

Access Statistics for this article

Theoretical Economics is currently edited by Simon Board, Todd D. Sarver, Juuso Toikka, Rakesh Vohra, Pierre-Olivier Weill

More articles in Theoretical Economics from Econometric Society
Bibliographic data for series maintained by Martin J. Osborne ().