论文标题
授权的随机探测
Delegated Stochastic Probing
论文作者
论文摘要
代表团涵盖了一系列问题，在这些问题中，委托人没有自己完成任务所需的资源或专业知识，因此他们将任务委派给了其利益可能不与自己的利益保持一致的代理商。随机探测描述了我们的任务是通过“探测”已知分布的可接受解决方案，以受到某些约束的方式来最大程度地提高预期效用。在这项工作中，我们将委托和随机探测的概念结合到一个单个机制设计框架中，我们称其为随机探测。我们研究了本金通过将随机探测问题授权而损失的，与他们在非较高溶液中的效用相比。我们的模型和结果受到了克莱恩伯格和克莱恩伯格在“授权搜索近似有效搜索”中的工作的重大启发。在他们的工作的基础上，我们表明，有委托的随机探测与普遍的先知不平等之间存在联系，这为我们提供了恒定的因素确定性机制，用于大量授权的随机探测问题。我们还以简单的授权探测设置探索随机机制，并表明它们在某些情况下优于确定性机制，但在最坏情况下却不优于确定性机制。
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.
