【讲座评述】Settling the Efficiency of First Price Auction

发表于 更新于 分类于

讲座：一价拍卖的效率——陆品燕

文献：Jin Y, Lu P. First Price Auction is 1-1/e^ 2 Efficient[J]. arXiv preprint arXiv:2207.01761, 2022.

（为了方便叙述，本文以该研究的作者的视角，即第一人称来写）

一价拍卖

即把物品卖给出价最高的人，且卖出的价格为这个出价最高的人的报价。

我们在网上常常看到的一堆人坐在台下不停叫价，台上有个拍卖师拱火的那种拍卖就属于一价拍卖。

但有时候，竞拍者可能不想到达现场或不想让别人知道自己的出价，这个时候就有密封一价拍卖。也就是每个竞拍者秘密地把自己的报价发送给拍卖师，然后拍卖师检查报价，宣布最高报价者并把东西以最高报价卖给他。本文研究的也是这种密封的一价拍卖。

一价拍卖虽然形式上非常简单和自然，但是它其实很“差”。因为它的纳什均衡在即使看起来非常简单的一些初始设置下也非常复杂。它也并不是DSIC的机制。

一价拍卖的形式化

我们形式化地定义一价拍卖。

竞拍者关于商品的价值（value）为，产生自一个独立的分布；

对于是私人信息，而则是公共信息；

的出价记为，那么可以定义策略，令；

给定，那么它可以在上诱导出；

的期望效用（utility），

其中，也就是在报价时获胜的概率。

（这里，是一个分布函数）

贝叶斯纳什均衡

在上述的一价拍卖定义下，我们可以进一步定义其贝叶斯纳什均衡：

竞拍者的策略组合为一个贝叶斯纳什均衡，当且仅当

（两边都是数学期望，这里没有显式地写出来）

注意，在贝叶斯纳什均衡中，每个竞拍者的策略都是对其他人的最佳回应。

“贝叶斯”意味着这不是对别人的报价的最佳回应，而是对他们的分布和策略的最佳回应。

非福利最大化情形

假设，

可得

是一个贝叶斯纳什均衡。

然而，当时，，

这也就意味着，商品在该实例中最后被卖给了价值更低的号竞拍者，导致了更小的社会福利。

效率/无政府代价

上面这样的例子让我们去思考如何衡量均衡的效率（也就是指“多大程度能实现社会福利”）。

我们使用博弈论中常用的Price of Anachy：

也就是代表一价拍卖，代表最优情形（即把商品分配给最大的）。

但是，对于里面的那一层下界，有些学者更倾向于使用上界，此时称为Price of Stability（PoS）：

即只考虑最好的那一个均衡。

显然

若 ，那说明均衡的选择是关键的。

先前的工作

Syrgkanis和Tardos证明了的至少为；

Hoy等人证明了一个更高的的下界；

Hartline等人给出了一个实例，证明了一个的上界。

先前的技术

由于纳什均衡非常难算（通常连解析解都没有），所以如何对其做出量化的研究是很困难的。

在先前的研究中，主要使用的是Tardos和Roughgarden提出的Smoothness technique，这个技术大致来讲就是拿着纳什均衡的定义推推推，推出一些不等式。由于避开了对均衡解的直接计算，问题会变得简单。

然而，这个技术在被提出的时候是用在一般的一些博弈里的，对于拍卖问题中的独立分布等条件，这项技术难以利用。

事实上，如果允许竞拍者的价值分布是不独立的，那么是一个紧确界。

我们的工作

一价拍卖的

我们的技术

尽管从算出多个再映到多个很困难，但是我们发现，从一个映回一个是简单的。这也是本文最重要的一个视角转换。

backandforth

具体的映射是这样构造的：

令，我们有

也就是简单的求个导。

这样，我们就把原来“刻画最差的价值分布”的任务转化成了“刻画最差的报价分布”的任务。

报价分布的合法性

上述的技术导致了一个新的问题，那就是合法的报价分布空间是什么？

在之前value的视角下，我们考虑的是所有价值分布，当然所有的分布也就都是合法的，bid是继而被诱导出来的，自然也是合法的。

现在我们从bid出发，就要首先考虑，哪些报价分布是合法的。

这项工作比较困难，大致来讲，最重要的是需要是单调连续的。

这给我们带来的视角的进一步转换，那就是比起关注报价的分布，事实上关注报价到价值的映射是一个更好的选择。由于它单调连续，我们很容易在坐标纸上绘出、把玩这些函数。

最差的（伪）实例

根据Hartline等人工作的经验，我们构造出了最差的实例：

有个竞拍者，一个竞拍者有固定的为的价值，其余个都是价值低于的竞拍者。

这个低价值的竞拍者中的最高价值，由下面这个参数方程定义：

支撑集为。

（其他更低的价值如何是没有影响的，他们主要用来贡献人数）

我们有

（没有严格使用这些符号，理解就行）

因此能够达到这个极限的实例是实际不存在的，但为了数学上的方便，我们把的情况也纳入，称为伪实例（pseudo instance）。

报价分布的递降变换

尽管我们声称上述实例是最差的，该怎么证明呢？

对于任意给定的，我们构造下面这样一个序列：

其中每个都是合法的，且

，

为最差实例。

离散化

为了方便构造上面的这种有限的递降归约（也因为我们可能不太擅长连续数学），我们希望对该问题中的某些要素进行离散化。

首先，我们不能离散化报价分布，否则报价分布就不合法了。

我们或许可以离散化，但是伴随的就很难处理，非离散情形解出已经很难了，对的离散化就更加棘手（它必须保持自己是均衡），甚至在离散后，相应的一些会直接消失。

最好的办法就是离散化，离散为分段常数函数（像台阶一样）。

Discretize

压缩高报价者

最后我们希望把原来的几个函数变成什么样呢？其实就是伪实例里说的，有一个恒等于的平着的函数，还有一堆小函数。

这个地方比较technical，涉及到对不同形态的函数的不同处理。

jump

大致来讲，就是通过各种手段找到能够使得降低的段落然后加以剪切与压缩，最后就能变换到最差的伪实例。

PoS的紧确界

前面提到，对于效率还有一种乐观度量，叫做，那么在这一度量下效率的下界又是多少呢？

我们的研究证明了，，和一样！

但是使获得最低值的情形不能直接套用在上，事实上，原情形中最好的均衡是full efficiency的。

但只要对原情形中恒为1的那个bid改为有的概率为，就可以把所有好的均衡消除，只剩一个坏均衡。还是比较巧妙的。

再聊聊

这项工作的技术还可以用在更多类型的拍卖的效率分析中，甚至为广泛的问题都带来启发。

另外，这个效率是假设竞拍者处于贝叶斯纳什均衡的效率，但是现实是我们连贝叶斯纳什均衡都不咋算的出来，竞拍者的报价呈现出的往往是一种近似解，那么，在给定竞拍者一定程度的计算资源（比如说要求有解析解、要求计算复杂性低于某个程度等等），我们能够达到的效率是多少？（这个思路显然也可以推广到一大堆问题）。