【论文评述】Delegated Search Approximates Efficient Search

发表于 更新于 分类于

本文研究的是代理搜索问题。

问题

参见【组会准备】Pandora’s Box, Delegation, Matching | Home of Mr. 5的Delegation部分。

问题模型

Distributional Model

有个candidates，它们的值为，是一个概率空间；

Pincipal的效用函数为；

Agent的效用函数为。

Agent只能从个candidates里挑个给Principal。

Principal可以提前框定一个eligible set，Agent挑的candidate必须属于这个set。

这个模型的一个小拓展就是Agent只能probe 个。

Binary Model

上面这个模型只有Agent去探测了以后们才会被实例化，Principal即使在Agent探测了之后也无法知道这些实例化，只能有关于的先验知识和最后看到一个proposal。

然而有的时候，方案其实是已知的几种，只是有的方案比较可行有的不太可行的区别，这就是Binary Model描述的情况。

有个已知的candidate：。

对于每个，有的概率是可行的。只有可行的方案才对双方有正效益，不可行方案对双方的效益都是。唯一能搞清楚到底是可行还是不可行的方法就是Agent花来做Probing。

Principal不晓得Agent花钱probe了哪些candidates。

Principal可以提前框定一个eligible set，Principal只接受属于该set的提案。

类似的，这个模型的一个小拓展就是Agent只能probe 个。

主要结论

  1. 在Distributional Model下，存在机制保证Delegation Gap为（这篇文章里的Delegation Gap是用的形式定义的，也就是越小越好），而且该机制只需要知道和即可。而且该机制是一个简单的阈值策略，也就是当且仅当时，才接受；

  2. 如果是独立的，且没有点质量，则Delegation Gap可以被改进到；

  3. 这两个Model都可以规约为或利用Prophet Inequalities；

交互模型

基本

为了能够数学地研究这个问题，需要把上述的模型的基本交互行为进行建模。

概率空间上有概率测度，；

；

为了刻画Principal没有选择任何方案的可能性，把扩充至，其中；

机制，其中为agent可能发送给principal的信号（究竟信号是什么，要看具体模型，总之是agent想提供给principal的东西），为表征“principal在给定了时究竟会选择哪个solution”的函数；

策略，其中代表上的一个序列，比方说，代表agent在sample到了后会向principal发出的信号；

现在，我们也可以说；

当时，principal和agent分别收益；

为了体现principal没有能力自己寻找solution，我们直接要求在不属于上述集合时，。

综合上述定义，若为一个机制，为一个策略，则它们生成一个interim allocation function：，本质上这就是，输入agent探索的序列，产生principal的选择。

扩展

  1. 当agent进行sample有cost的时候，agent的策略除了外还需要包括一个“顺序策略”，用来在给定了先前已采样得到的序列时下一个要采样的对象是谁。费用在principal和agent的效益上都要扣除（在本论文里），因为作者觉得即使是在principal里agent的搜索也属于一种”waste”；

  2. 除了上面的sampling cost ，有时限制也被表现为sampling budget ，即采样的总个数不能超过；

  3. 可能被扩展为，agent能够在这些不同的测度上独立的采样；

  4. full-information case：principal既知道，又知道，

    或者，

    limited-information case：principal只知道；

  5. 都为任意的非负函数，

    或者，

    是独立随机变量。

单提案机制

我们更仔细的关注一个重要的机制，那就是agent只能提交一个solution，principal可以接受或拒绝。这个机制叫单提案机制（Single Proposal Mechanism）。

Principal有一个可行集，当且仅当提案在中时接受。

形式化的，，，

为什么单提案机制是重要的呢，主要是因为以下引理：
Lemma1：

如果是一个机制，是一个为提供最佳回应（在agent的utility意义上）的策略，则一定存在一个单提案机制和一个最佳回应策略，使得。

Proof：

令为的值域（除去）；

设为以为可行集的单提案机制，令，其中，易得；

现在要证明是一个能提供最佳回应的策略，即要证明，令，对于任意和任意，：

首先注意到，

若，则，；

若，则，而我们注意到，是下的最佳策略，且，因此相当于在下按照行动的收益，而相当于在下按照行动的收益，从而不会更高。

代理搜索与先知不等式之间的联系

现在我们要给出代理搜索和先知不等式之间的联系。这里的先知不等式并非最通常的按的顺序到来的，而是按照连续时间上的离散点到来的。

选择规则

一个选择规则（selection rule）是一个从的有限子集映到 的函数，且对于任意，。

一个停止规则（stopping rule）是一个从中选出且不观察比更靠后的元素的选择规则。形式化地讲，它符合下述条件：对于任意以及任意满足的，都有

（这个建模还是挺漂亮的，用这种“不可区分性”定义了“看不到后面”的在线性）

一个显式停止规则（oblivious stopping rule）是一个带有可行集的停止规则，满足

也就是接受可行的里最早的那个。

一个阈值停止规则（threshold stopping rule）是一个带有阈值的显式停止规则，其可行集的形式为或.

连续时间选择问题与先知不等式

连续时间选择问题（continuous-time selection problem，CTSP）是一个有序对 ，是的有限子集上的一族概率分布，而是一族选择规则。

我们称一个CTSP满足系数的先知不等式，当其满足：

对于任意，存在，使得

，

其中当时，；当时，；。

下面定义一些重要的选择规则集合和分布集合：

  1. 是显式停止规则的集合；

  2. 是阈值停止规则的集合；

  3. 大致可以理解为独立分布的集合。给定一个，给定上的联合分布元组，从这个分布里分别独立采样出一个元素，上述行为定义了一个；

  4. 大致可以理解为元素独立同分布的集合。给定，从一个无原子分布上独立同分布地采样出个元素，与也独立；（无原子指的是不存在这样的集合，的测度为正且其任意真子集的测度都为（就像一个不可分割的原子））

  5. 是全体的的并集。

下面是几个本文要用到的先知不等式：

  1. 满足系数的先知不等式；

  2. 满足系数的先知不等式；

  3. 满足系数的先知不等式，其中，；

阈值停止规则对于连续时间和离散时间是不敏感的，所以前两个定理是可以直接由其离散时间版本得到的。

定理1的阈值是，其为的分布的中位数，即；

定理2的阈值是，其使得；

对于定理3，令满足，令为方程的解，且有初值，属于可行集当且仅当。

代理搜索到先知不等式的归约

这个归约是这篇文章最重要的一个观察了（不过我觉得还好其实（（（这也是为什么我前面建模部分写得这么多（（（

简单来说， 在代理搜索中的地位和在先知不等式中的地位一样。在代理搜索中，agent在可行集内选择能让最大化的solution；在先知不等式中，我们在可行集内选择最小的那个element。我们只要把再映到一个上的递减函数，这俩问题考虑的东西其实就等价了。

具体地，令为从映到的任意连续单调减双射。

考虑映射，，则该映射能将任意上的分布诱导为上的分布。

比方说，从上独立同分布地采样个solution就可以由诱导为。

类似的，代理搜索中的机制和先知不等式中的选择规则之间也可以建立起联系。

设是带可行集的显式停止规则，是可行集为的单提案机制，是一个最佳回复策略，我们有：

也就是说，在机制下选择对于agent最好的、属于的选项，和在下选择时间最早的属于的选项，是等价的。

这样一来我们就完整地建立了代理搜索和先知不等式的完整联系。

于是我们可以直接把先知不等式的结论放到代理搜索（的Distributional Model）里，令为principal自己来完成任务时的收益：

  1. 存在带阈值的单提案机制保证principal的期望收益至少为；

  2. 如果principal和agent的utility是独立的，且都各自产生自一个无原子分布，则存在带阈值的单提案机制保证principal的期望收益至少为；

  3. 如果principal和agent的utility是独立的，且都各自产生自一个无原子分布，且principal知晓agent的utility（因为后面判断是否接受的式子里要用到），则单提案机制，其在满足时才接受（为一恰当选取的函数），保证principal的期望收益至少为。

二值输出

之前还提到了Binary Model，这个模型事实上基本等价于Weitzman’s box problem（也常被叫做Pandora’s box）。那么类似的，我们又可以利用Pandora’s box那边的结论了（部分基础结论见【组会准备】Pandora’s Box, Delegation, Matching | Home of Mr. 5）。

由于我对这个部分没有太多兴趣，所以只做简单介绍。

传统的box问题里，有个类似于“虚拟值”的东西。在无代理的Binary Model下，这个虚拟值就是，在有代理的情况下（也就是agent视角下），就变成了。

在有代理的Binary Model下，principal相当于无法决定box打开的顺序，而只能让agent按顺序开盒。但是principal可以决定有哪些盒子是可开的、哪些应被跳过，也就是设定一个可行集，非可行集的盒子agent不会去开。

令为形如的半无限区间，令,为以为可行集的单提案机制。这就是Binary Model下的阈值机制。

文章证明了，存在阈值策略能够保证的delegation gap，相关的结论同样由先知不等式和Pandora’s box有关的结论和技术证明。