【科研点子】Price of Anachy in Delegation

发表于 2023-10-21 更新于 2023-12-27 分类于科研点子

经过这段时间的学习，我已经对标题所述的这个科研点子有了比较系统的想法。

代理问题的无政府代价涉及哪些空间？

空间，即全体分布集族的空间；
空间，即全体pincipal效益函数的空间；
空间，即全体agent效益函数的空间；
空间，即全体principal可采取的策略的空间。

（注意，全体会张成一个空间，但任意的一个本身也是一个空间）

四个空间的选取定义了一个确切的代理问题和其解决过程，记为，全体构成总空间。

作为例子的一个子空间

如果不设条件，那么上面提到的这四个空间都非常非常庞大，组合起来就更大了。

出于这个领域的研究惯例和实际意义，我们对这些空间要做出缩限。

这里给出一个极简的例子：
令缩限到仅含有一个联合分布，；

令，，也就是俩人的效益刚好“相反”；

令缩限到。

那么此时，我们其实只是要遍历空间。

即。

S’上的两类无政府代价

将策略下principal和agent总效益的期望记为，

令使得principal期望收益最大化的策略为，

按照传统的无政府代价定义，我们有

我们考虑无信息情形，也就是principal不知道：

注意，我们现在有两点可能存在的困惑——

此时（在principal的角度）其实是无法计算出究竟是什么的，因为是未知的。根据相关研究，principal只能确定地给出能够保证常数级别delegation gap（接下来简记为dg）的方案。
代表“有政府”的的真正含义是有待商榷的。它可以有两个程度——一是有个开天眼的人看到了两个人的效益函数，然后强行把设定成了最有利于整体的那个，agent仍然按照来自己行动，在下最大化自己的效益函数，这个比较符合delegation的设定，但是由于agent仍在追逐私利所以看起来好像不够“有政府”；二是principal和agent完全联合，制定策略来最大化全体的利益。这固然够“政府”，但此时作为联合体的两人仍停留在就是一件很奇怪的事了，更好的策略显然是把所有元素sample完然后选择对整体最好的那个，这并不是所能涵盖的策略，我们得换一个记号了。暂且地，我们将基于第一个程度计算的“有政府”期望收益记为，第二个程度记为。

对于第一点，我们修改定义：令principal角度下delegation gap最优化的策略为。

比方说，我们可以很容易地给出一个 dg的阈值策略。 dg的策略是一般性的下的最优策略（也就是新定义下的）。但是我们此处考虑的只是一个特殊的分布，因此可以做的更好。

考虑dg就要考虑最差的情形，它是什么呢？事实上就是agent的效益函数和principal刚好“相反”。（而恰好我们这个例子里agent的效益函数也确实是这样的）此时，在进行两次sample后，agent总会挑选符合阈值规则的元素里（principal视角下）最差的那个。

首先给出一个引理，设，则

。

设阈值为，最差情形下，有收益期望如下：

求导，

令导数为，得正根

此时能保证最差情形下期望收益为

则有

还不错。

而此时的总期望收益为：

而显然

（因为最大化和最大化是一致的）

故

让我们来考虑一下这两个结果：

对于第一个结果，它事实上给出了一个能导致最好的实例。

我们还能再给出很多这样的实例，比方说推广为，其中。

其实显然，上述构造就是在保证与只差一个正常数倍数的关系。

那么现在就有一个非常值得一问的问题，的充要条件是什么？或者能否至少给出一些更一般的例子？我在此给出一个猜想，当区间内的实数按照与的值分别构造的序关系相同时，。（这在我看来是一个具有根本意义的数学问题，那就是，对于某个优化模式，哪些函数是等价的）

对于第二个结果，看起来还蛮不错的，这个代价虽然不为，但也很小。类似的，我们要问在一定问题空间内的上下界是什么，导致这些上下界的实例或充要条件是什么？

该问题还有一个技术难点，那就是可行的函数空间是纷繁复杂的，这导致在很多时候难以计算。而令人兴奋的是，陆品燕最近关于“PoA in First Price Auction”的研究给出了一个新路径，那就是从均衡反推分布。这个问题也很有可能可以使用这项技术。

一个能导致最差PoA的伪实例

Delegation问题里，如果不对问题空间做特别限制，是可以无穷差的，而且例子非常平凡。

把里的和扩充到一般函数，其他保持不变，考虑下面这两个函数：

（这里给右边添个主要是为了让agent有个明确点的占优策略）

当时，有

为。

（这里省略了很多系数之类的东西，懂就好）

则

弥补PoA的第三方方案和零知识方案

在我们的问题设定里，principal和agent存在一种不信任关系。在原始论文中，所有策略都不基于任何双方关于彼此效益函数的先验知识。

现在的问题是，如果存在一个可信的第三方（能够保密等），在什么情形下双方愿意把自己的信息交给第三方去处理？或者对于彼此的先验知识到达什么程度才能使双方产生这种意愿？

另一方面，如果不存在这样的第三方，是否还有（零知识）机制在不降低双方期望收益的情况下改良？

（研究中）