Principal：想要挑选一个或多个Elements，有自己的效用函数，也是我们要最优化的主体。比方说准备雇佣员工的老板，但由于没时间或者没有相关人才等原因，把面试任务委托给了Agent。
Agent：接受委托的机构，帮Principal做事，但也有自己（与Principal不同）的效用函数。它的目标是在Principal许可的范围内最大化自己的效用函数。
Element：每个Element相当于一个应聘者，它们的值往往来自一个已知的分布，且对于Principal和Agent会产生不同的效用。

现在的问题是，Principal要制定怎样的方案才能让Agent做出的决策最有利于最大化效用？

更具体的问题

类似competitive-ratio，delegation领域叫delegation gap：

也就是最差情形下委托出去带来的效益与假如能自己去做带来的效益之比。

Delegated Search Approximates Efficient Search中Kleinberg率先给出了简单的阈值策略保证delegation gap高于常数，同时，并不令人十分意外但又十分重要地，发现朴素的delegation问题可以规约为先知不等式问题。这个联系让Delegation问题既变得更好解决又变得更重要了。

gap

后来

后来基本也是做这两件事：1.联系某种prophet inequality；2.控制delegation gap。

Delegated Stochastic Probing这篇文献证明了Delegated Stochastic Probing等价于generalized prophet inequalities，并且给出了保证常数delegation gap的算法。基本就是对Kleinberg的结果的一般化。

关于Matching

Matching你们已经是专家，不介绍了。

关联成果

开头列出的论文大多数都是将上面三个概念进行了结合。

Information Acquisition in Matching Markets: The Role of Price Discovery这篇文章比较经济学，主要研究的是“院校-学生”这种多对一市场的匹配，而且信息获取是有开销的（比如学生需要花费很多精力甚至金钱了解各个学校的优劣）。最后实现的是一个的匹配算法。里面用到了Pandora’s box的一些技术结论。

Delegated Pandora’s Box把Delegation和Pandora’s Box结合了，也利用了那个等价于generalized prophet inequalities的结果。Principal要挑选几个Element，把探测的任务委托给了Agent，Agent在探测Element的时候有成本，Agent无法说谎，最后Agent要把几个Elements提交给Principal，Principal可以选择接受或拒绝。文献研究了几个模型（standard model、free-agent model、shared-cost model以及这些模型的各种子集和变型），证明了常数级别的Delegation Gap在这些模型里的存在性or不存在。

一些更近的成果

Delegating to Multiple Agents

发表于EC’23

扩展到了多代理系统，也就是Agent有个。

Delegated Online Search

发表于IJCAI-23

我觉得这篇对我们可能重要或者亲切一些。

扩展到了多种在线情形，并得到了许多紧的结果（下面这张表中大部分应该都是紧的）：

online

比方说，在下面这个最简单的在线拓展下：

Elements逐一到来，Agent可以选择接受（并提交给Principal从而结束整个流程），或者等待（该Element将不再可访问）。Principal在收到Agent的proposal后可以选择接受或拒绝，接受则Principal和Agent各获得相应的收益，拒绝则双方收益都为0。

作者证明了，有的时候对某类Element的期望会过大，以至于它倾向一直等下去，直到最后发现自己白等了，从而导致的Delegation Gap，而这也是明确劣于离线版本的。

表格左侧的conscious、semi-oblivious、oblivious的意思分别是：

conscious：在agent提交proposal时，principal知道其产生的、；
semi-oblivious：在agent提交proposal时，principal只知道其产生的，不过principal具有的prior knowledge；（这里可能有点绕，它的意思就是尽管我知道agent的效益函数是什么，但是对于agent给我的proposal，我只能看到对自己的效益，但不能看到（从而不知道））
oblivious：在agent提交proposal时，principal只知道其产生的，连关于的prior knowledge也没有。

另外还有两个很有用的概念：

restricted discrepancy：Principal知道（因为文章发现这是比值是一个关键的影响因素，原因从我们上面那个最简单的例子可以大致看出来）。
misalignment：，一个刻画了和之间分歧的量。

我们可以做什么

目前这些个领域应该还是处在非常活跃的状态，因此有两类角度来继续研究。

已知的未知

首先是可以做这些论文里提到的Open Problems，属于已知的未知。

比如Delegated Stochastic Probing中给出了这几个问题：

opq

再比如Delegated Pandora’s Box里给出了这些问题：

open1

这些问题，通常为改进某些常数、换个模型再分析一遍、证明一些算法的不可能性（比方说上面这篇文献并没有太考察随机的lottery mechanism，于是他问：“Can the principal
do strictly better in any of these models by using a lottery mechanism instead?”）。

我们可以选择其中一些比较值得做问题的试试。

未知的未知

另外就是概念的排列组合，属于未知的未知。（很可惜，Online Delegation和Multiple Agents刚刚被做掉了）

Delegation from Multiple Principals

( Delegation in Bipartite Matching)

(当然也可以再加上Online的约束)

也就是把Principal的数量扩展到个，此时Principal和Elements之间的关系就相当于一张待匹配的Bipartite Graph。（这与多个Agent很明显是不同的，因为不同的Agent可以提名相同的候选者，但是不同的Principal不能雇佣同一个Element）

文献Information Acquisition in Matching Markets: The Role of Price Discovery一定意义上属于这个模型，但经济学者主要考虑的是匹配的稳定性（无后悔、无嫉妒之类的），而且并没有Delegation，因此还有很多可做。特别是，Bipartite Matching本身就已经有好几个不同的模型，因此它们很可能在代理问题中也有不同的表现。

Realworld Motivation：金融领域有一项服务叫“信用评级”，各大金融机构在投资、购置金融商品时，常常会把对金融商品的信用考察委托给信用评级机构。而信用评级机构的数量非常少，事实上，的信用评级服务都被S&P、Moody’s和Fitch Group包揽，这就可以理解为多个Principals，一个Agent，多个Elements的情形。
Price of Anachy in Delegation

显然，Agent和Principal各有自己的私心，先前的文献主要关注Principal的损失（以及如何控制Principal的损失），鲜见对整体福利损失的计算。

Realworld Motivation：首先，研究委托行为会损失多少整体福利本身就是有现实意义的。另外，研究这一损失可以为一些第三方机制的介入提供依据。比方说，有些委托问题可以交给更值得信赖（无利益相关）的第三方来监督，从而达成更高的整体福利，甚至达成能让双方都更优的机制（通常只有达到这个程度，这种监督机制才能为Principal和Agent双方接受），抑或者，我们可以证明这种监督的不可能性。
More ideas…?