Poorman's SE VCG | 从零开始 Haskell 实现搜索引擎 VCG

VCG 即 Vickrey–Clarke–Groves 机制，是一种具有很多优秀性质的拍卖机制。包括完美匹配、市场出清、在所有可能的清仓价格中总价格最低、总收益达到社会最优、买家按真实估值出价是出价均衡而且是最优策略等等。

搜索引擎广告位拍卖是一种特殊的拍卖形式。详细分析见《网络、群体与市场》第 15 章。（英文预印本可在官方网站合法下载。）假设广告位 $i$ 的点击率 $r_i$ ，广告商 $j$ 对单点击的估值为 $b_j$ 。那么广告商 $j$ 对广告位 $i$ 的总估值 $v_{ij} = r_i b_j$ 。

注意到同一个广告位的点击率对所有广告商相同，因此对单点击估值最高者获得点击率最高广告位，依此类推。这就为搜索引擎中的 VCG 计算带来的简化的空间。

每个广告商所支付的价格等于假设它不出现时，其他广告商所能获得的总福利增加。（也就相当于它出现给其他所有人带来的总损失。）

不妨将广告从点击率高到低排列，广告商按估值从高到低排列。那么估值最高者所支付价格等于第二高的广告商如果取得第一高的广告位能增加的福利（ $(r_1 - r_2) b_2$ ），加上第三高的广告商取得第二高的广告位能增加的福利（ $(r_2 - r_3) b_3$ ）等等。也就是估值矩阵（ $v_{ij}$ ）主对角线减次对角线。

这里给出一种超轻量的 Haskell 实现。

首先对原公式进行变形：

$\begin{align} p_j &= \sum^{m}_{i=j+1} b_i(r_{i-1} - r_i) + b_{m+1}r_m \\ &= \sum^{m+1}_{i=j+1} b_i(r_{i-1} - r_i) \end{align}$

其中 $r_{m+1} := 0, b_{m+1}:= \mathbf{if} \ m=n\ \mathbf{then} \ 0 \ \mathbf{else} \ b_{m+1}$

可以将原有的点击率列表和每点击估价列表，通过填充 $0$ ，将边界情况统一成一般情况。

给定某广告位之后的点击率列表和估价列表，计算该广告位价格的方法如下：

price :: [Int] -> [Int] -> Int
price rs bs = sum $ zipWith (*) padbs padrs
  where
    padbs = tail $ bs ++ [0]
    padrs = zipWith (-) rs $ tail rs ++ [0]

首先，padbs 根据上面的推导分别在原有列表尾部添 0 。如果广告商不足（ $m=n$ ），则会使用多余的 0 ；如果已经足够（ $m>n$ ），则添加的 0 会在 zipWith 中被舍弃。

填充之后，padbs 进行了 tail ，这是因为每个广告上的价格是靠其后广告商估值计算得到的。

padrs 负责计算当前广告位点击率和下一个广告位点击率之差。

而主函数部分只是一个简单的向量内积。 price 函数整体上实现了，给定某一广告位开始（包括自己）的点击率列表，和估值列表，可以计算这一广告位的价格。

计算所有广告位的价格的方法如下：

vcg :: [Int] -> [Int] -> [Int]
vcg rates bids = init $ zipWith price (tails rates) (tails bids)

这里利用了 tails :: [a] -> [[a]] 函数，需要 import Data.List (tails) ，其作用是接收一个列表，不断去除首元素，再将结果收集成一个列表。

例如：

λ> tails "abc"
["abc", "bc", "c", ""]

函数首先生成了每个广告位开始（包括自己）的点击率和估值列表，再将其作为参数传给 price 。最后加 init 是因为 tails 函数会将空列表作为最后一个元素。我们将这个价格抛弃。

测试如下：

λ> vcg [5,3,1] [15,8,5]
[26,10,0]
λ> vcg [5,1] [11,7,5,3,2,1]
[33,5]

实现正确。

有效代码只有 4 行，只用了一个简单的库函数。这个例子很好地体现了 Haskell 的简洁和抽象能力。

最后编辑于：2019.04.26 12:31:08