Delegated Search Approximates Efficient Search

被引:27
作者
Kleinberg, Jon [1 ]
Kleinberg, Robert [1 ]
机构
[1] Cornell Univ, Ithaca, NY 14853 USA
来源
ACM EC'18: PROCEEDINGS OF THE 2018 ACM CONFERENCE ON ECONOMICS AND COMPUTATION | 2018年
关键词
Delegated search; prophet inequalities; SUPREMUM EXPECTATIONS; STOP RULE;
D O I
10.1145/3219166.3219205
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
There are many settings in which a principal performs a task by delegating it to an agent, who searches over possible solutions and proposes one to the principal. This describes many aspects of the workflow within organizations, as well as many of the activities undertaken by regulatory bodies, who often obtain relevant information from the parties being regulated through a process of delegation. A fundamental tension underlying delegation is the fact that the agent's interests will typically differ - potentially significantly - from the interests of the principal, and as a result the agent may propose solutions based on their own incentives that are inefficient for the principal. A basic problem, therefore, is to design mechanisms by which the principal can constrain the set of proposals they are willing to accept from the agent, to ensure a certain level of quality for the principal from the proposed solution. In this work, we investigate how much the principal loses - quantitatively, in terms of the objective they are trying to optimize - when they delegate to an agent. We develop a methodology for bounding this loss of efficiency, and show that in a very general model of delegation, there is a family of mechanisms achieving a universal bound on the ratio between the quality of the solution obtained through delegation and the quality the principal could obtain in an idealized benchmark where they searched for a solution themself. Moreover, it is possible to achieve such bounds through mechanisms with a natural threshold structure, which are thus structurally simpler than the optimal mechanisms typically considered in the literature on delegation. At the heart of our framework is an unexpected connection between delegation and the analysis of prophet inequalities, which we leverage to provide bounds on the behavior of our delegation mechanisms.
引用
收藏
页码:287 / 302
页数:16
相关论文
共 22 条
[1]   Beating 1-1/e for Ordered Prophets [J].
Abolhassani, Melika ;
Ehsani, Soheil ;
Esfandiari, Hossein ;
HajiAghayi, MohammadTaghi ;
Kleinberg, Robert ;
Lucier, Brendan .
STOC'17: PROCEEDINGS OF THE 49TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2017, :61-71
[2]   Formal and real authority in organizations [J].
Aghion, P ;
Tirole, J .
JOURNAL OF POLITICAL ECONOMY, 1997, 105 (01) :1-29
[3]   Optimal delegation [J].
Alonso, Ricardo ;
Matouschek, Niko .
REVIEW OF ECONOMIC STUDIES, 2008, 75 (01) :259-293
[4]   The Theory of Optimal Delegation With an Application to Tariff Caps [J].
Amador, Manuel ;
Bagwell, Kyle .
ECONOMETRICA, 2013, 81 (04) :1541-1599
[5]   Delegation and nonmonetary incentives [J].
Ambrus, Attila ;
Egorov, Georgy .
JOURNAL OF ECONOMIC THEORY, 2017, 171 :101-135
[6]   A Model of Delegated Project Choice [J].
Armstrong, Mark ;
Vickers, John .
ECONOMETRICA, 2010, 78 (01) :213-244
[7]   Maximizing Stochastic Monotone Submodular Functions [J].
Asadpour, Arash ;
Nazerzadeh, Hamid .
MANAGEMENT SCIENCE, 2016, 62 (08) :2374-2391
[8]   Collusion and price rigidity [J].
Athey, S ;
Bagwell, K ;
Sanchirico, C .
REVIEW OF ECONOMIC STUDIES, 2004, 71 (02) :317-349
[9]   Posted Price Mechanisms for a Random Stream of Customers [J].
Correa, Jose ;
Foncea, Patricio ;
Hoeksma, Ruben ;
Oosterwijk, Tim ;
Vredeveld, Tjark .
EC'17: PROCEEDINGS OF THE 2017 ACM CONFERENCE ON ECONOMICS AND COMPUTATION, 2017, :169-186
[10]  
Ehsani S, 2018, SODA'18: PROCEEDINGS OF THE TWENTY-NINTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P700