Computational principal-agent problems

• 成果类型: Article
• 署名作者: Azar, Pablo D.; Micali, Silvio
• 署名单位: Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
• 刊物名称: THEORETICAL ECONOMICS
• ISSN/ISSBN: 1555-7561
• DOI: 10.3982/TE1815
• 发表日期: 2018-05-01
• 页码: 553-578
• 关键词: Principal agent problems; computational complexity

摘要

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 = (x(1), ..., x(n)), 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 epsilon > 0, the principal can-by learning a single component x(i) of x-incentivize the agent to report the correct value f(x) with accuracy epsilon. complexity.