文章基本信息

标题：Computational principal agent problems
本地全文：下载
作者：Azar, Pablo D. ; Micali, Silvio
期刊名称：Theoretical Economics
印刷版ISSN：1555-7561
出版年度：2016
出版社：Econometric Society
摘要：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 $\varepsilon >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 $\varepsilon$.
关键词：Principal agent problems; computational complexity