Delegation covers a broad class of problems in which a principal doesn't have the resources or expertise necessary to complete a task by themselves, so they delegate the task to an agent whose interests may not be aligned with their own. Stochastic probing describes problems in which we are tasked with maximizing expected utility by "probing" known distributions for acceptable solutions subject to certain constraints. In this work, we combine the concepts of delegation and stochastic probing into a single mechanism design framework which we term delegated stochastic probing. We study how much a principal loses by delegating a stochastic probing problem, compared to their utility in the non-delegated solution. Our model and results are heavily inspired by the work of Kleinberg and Kleinberg in "Delegated Search Approximates Efficient Search." Building on their work, we show that there exists a connection between delegated stochastic probing and generalized prophet inequalities, which provides us with constant-factor deterministic mechanisms for a large class of delegated stochastic probing problems. We also explore randomized mechanisms in a simple delegated probing setting, and show that they outperform deterministic mechanisms in some instances but not in the worst case.


翻译:代表团涉及广泛的问题, 委托人没有完成某项任务所必需的资源或专门知识, 因此他们将这项任务委托给一个其利益可能与其自身利益不相符的代理人。 斯托克调查描述了我们的任务是通过“ 探究”已知分配办法, 最大限度地发挥预期效用的问题。 在这项工作中, 我们把授权和随机调查的概念合并成一个单一的机制设计框架, 我们用“ 随机调查” 来称呼它, 我们用我们所说的“ 随机调查” 来形容。 我们的研究, 将委托人调查的问题委托给一个可能与自身利益不符的代理人, 从而损失了多少。 我们的模型和结果在很大程度上受到克莱因伯格和克莱因伯格在“ 缩小搜索范围, 提高搜索效率” 中的工作的启发。 在他们的工作基础上, 我们显示, 授权的随机调查与普遍的先知不平等之间存在联系, 为我们提供了一个固定的确定机制, 用于处理大量委托调查的问题。 我们还在最差的验证机制中探索了一些随机机制, 而不是在最差的检验机制中进行随机性研究。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
最新《联邦学习Federated Learning》报告,Federated Learning
专知会员服务
88+阅读 · 2020年12月2日
最新《序列预测问题导论》教程,212页ppt
专知会员服务
84+阅读 · 2020年8月22日
【清华大学】图随机神经网络,Graph Random Neural Networks
专知会员服务
155+阅读 · 2020年5月26日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【论文笔记】通俗理解少样本文本分类 (Few-Shot Text Classification) (1)
深度学习自然语言处理
7+阅读 · 2020年4月8日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
已删除
将门创投
5+阅读 · 2018年3月21日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2021年2月4日
VIP会员
相关资讯
【论文笔记】通俗理解少样本文本分类 (Few-Shot Text Classification) (1)
深度学习自然语言处理
7+阅读 · 2020年4月8日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
已删除
将门创投
5+阅读 · 2018年3月21日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员