曾子曰:学好不容易,学坏一出溜。在原始共产社会,以物易物的时代,每一次交易都像是搞对象互赠礼物那样纯真而浪漫;后来,有了货币,才有了明码标价的交易模式,也就有了套利的商人;人心不足蛇吞象,为了挑动群众斗群众,一样的东西卖出不一样的价钱,商人又发明了拍卖这种交易模式。对那些价值转瞬即逝、交易又不那么旺盛的商品,像荷兰的郁金香、日本的金枪鱼,只有通过拍卖,才能在短时间内聚集大量的卖家,卖出个好价格。

前些日子,一个外国娘儿们拍卖初夜权的事儿传得沸沸扬扬,殊不知,在古巴比伦,唯一合法的婚姻结合方式,就是把新娘摆出来拍卖(见题图)。显然,初夜权也是一种“价值转瞬即逝、交易不太旺盛”的商品,您想想。。。算了这我就不展开说了。

互联网产生后,拍卖由一种非主流交易方式变成了显学,这是因为互联网最核心的变现模式——广告,在今天大部分是以拍卖的方式交易的。因此,每一个从事互联网的人,都应该对拍卖的问题和其中巧妙的机制设计有所了解,当然,这些问题本身也足够有趣。

以广告为例,我们来看看拍卖到底是个什么问题。大家看上面的图:当你在搜索引擎输入“信用卡”这个词时,搜索结果页最上面灰色打底的那两条,就是两个广告位,一般来说,会有多个客户竞争这两个位置。当然,不同的客户获得了广告点击以后,获得后续收益是不同的,这个叫做value。比如说,广发银行获得广告点击的value是0.5元;同时,广发银行给了拍卖方一个0.3元的报价,这个叫bid。我们假设客户对点击率的影响不大,那么拍卖方按照bid来拍序,前两名被依次放在了两个广告位上。

显然,这种拍卖带有非常明显的博弈属性:因为你面对的广告主,都是一个个活生生有利益诉求的人,当你制定的市场规则调整时,他们也会相应改变自己的策略以寻求利益最大化,直到每一个参与者都觉得自己没法得到更多的利益了,大家也就消停了,这时,我们说博弈达到了“纳什均衡状态”。

我们来举个小例子说明这件事:除了value和bid,拍卖过程里还有一个变量叫payment,就是你竞拍成功之后拍卖方收取的费用。假设在我们的市场规则里,这个payment就等于bid,这叫做第一高价(first price),这样会出现什么情形呢?在上图中,招商银行出了0.8元的bid,赢得了第一个位置,然后被扣了0.8元。显然,招商银行一定知道第二名的出价是小于0.8元的,于是他开始试探,出0.7元行不行呢?试了一下,发现没问题!干脆再接着往下试,直到出0.41元为止。结果,招商银行花0.41元就拿到了开始0.8元才拿到的位置,真是爽歪歪!不过呢,拍卖方可就狗熊钻烟囱——太难过了:你们这些家伙怎么出价越来越低啊?

上面的例子形象地告诉我们拍卖中的博弈过程,并且给每一个初入此领域的人敲响了警钟:在拍卖问题里,我们要重点关注的,不是当下这一次竞拍的所得,而是系统达到纳什均衡状态之后的情况。竞拍者都在博弈,那么市场规则制定者就要特别小心,要从宏观上把握收入、公平性、稳定性等各个方面的情况,而这些制定市场规则的学问,就叫做“机制设计”。

机制并不能直接确定价格,否则就背离了竞价的市场本质。不过,机制的好坏却从根本上决定了市场的走向。常见的机制设计手段很多,比如“应该向竞拍者收多少钱?”(定价)、“竞拍者应该出多少钱?”(市场保留价)等。不过在讨论手段之前,还是要先说说目标。

记得我在“20万、50万、100万的算法工程师,到底有什么区别?”一文中曾经说过,在解决一个问题之前,最重要的一点是确定目标函数。那么,拍卖问题的目标函数是什么呢?简单想来,就有两种可能的选择:一是社会福利(social value)最优,也就是物尽其用,把商品分配给那个对他来说最有用的人;二是收入(revenue)最优,也就是拍卖行挣到更多的钱。

如果目标是社会福利最优,聪明的读者一定想到了,问题的关键就在于如何让竞拍者忠实地按照自己的收益来出价,也即 bid = value,这样一来,直接按bid排序就是社会福利最优的结果了。不过呢,这样“忠实出价”(truthful)的拍卖机制,并不是从直觉上唾手可得。如果我们采用的是上面例子中的 payment = bid 这样的“第一高价”机制,显然很难让竞拍者忠实出价。

那么让竞拍者忠实出价,以达到社会福利最优的方法是什么呢?古人已经告诉了我们答案——这就是所谓的VCG定价机制。这个VCG,是Vickrey、Clark、Groves三位先贤的大名。概念上讲,这个VCG方法,是通过计算一个竞拍者参与拍卖给其他竞拍者带来的损失之和来定价的。在上面搜索广告的例子里,如果按照点击出价,因为招商银行的参与,平安银行被挤到了第二名,广发银行被挤没了,假设前两个位置的点击率大约是5%和3%,那么每个点击应该向招商银行收多少钱呢,就得按下面这样算: 

[(5%―3%)╳0.4 +(3%―0%)╳0.3 ] / 5%

如果我们的广告竞拍只有一个位置,那么VCG就变得很简单了:向获得广告位的客户收的费用,就等于他下一位的出价,这个就是大家熟知的第二高价(second price)了。在类似于大字报这种这种只有一个位置的显示广告场景中,第二高价就很常用了。

再回到前面的搜索广告问题,这是个有多个广告位置的拍卖,像VCG这种是人就弄不明白的机制,我们这种码农很难想得到。更加直觉的方法,是把第二高价做一个naive的推广:第一名按第二名收,第二名按第三名收,依此类推。这就叫广义第二高价(Generalized Second Price,GSP)。这种方法在实践中很常用,效果不错,收入也比VCG高一些。不过呢,这个拍脑袋的方法并不能做到truthful,当然也就不是社会福利最优了。

话说回来,拍卖行和广告平台不是公益组织,说追求社会福利最优只不过是做个样子,谁心里想的不是自个儿多挣点钱啊!如果我们的目标是平台收入,该怎么设计机制呢?这就比社会福利最优要复杂多了。

为了搞清收入最优机制的原理,我们先讲个小故事:2013年11月,王健林在佳士得纽约拍卖夜场以3000多万美金的价格拍下了毕加索的名作《两个小孩》。事后记者采访首富:“您觉得3000万贵不贵?”王健林脱口而出:“太便宜了啊!我原本打算花5000万的!”拍卖师听到这话,一口老血喷在墙上:“原来这画贱卖了这么多啊!”

这种有几个鹤立鸡群的土豪买家存在的拍卖场景,实践中很常见。比方说,各路电商去Google买广告,都会遇到个巨无霸的竞拍对手亚马逊。要想做到收入最优,就得把他们挥金如土的二百五劲头儿激发出来。当然,现在是法制社会,你不可能掐着他脖子要求他出高价,还得通过机制设计上的巧妙办法,“诱使”他自觉地出高价。

解决办法直觉上也很简单,就是吃大户:你王健林不是有钱么,对不起,你出价一块我只能按八毛给你算。另一位先贤Roger Myesron抱着逮住蛤蟆攥出尿来的人文关怀,精心设计了这样一种收入最优的拍卖机制,简单来说,这一机制分如下三步:

一、将竞拍者的出价映射成一个虚拟出价。这个映射的原理,是把历史上看出价能力强的土豪往下打压。对某个竞拍者,具体的打压公式如下:

  b‘ = b―[1-F(b)]/f(b)

这里面的b代表bid,f(b)为该竞拍者bid分布的概率密度函数,而F(b)为相应的累积分布函数。很容易验证,历史出价越高的土豪,被打压得越厉害。

二、将0做为虚拟出价上的底价,对竞拍者进行过滤。这个动作的目的,是敲山震虎,向王健林你丫这样的土豪,出价太低了就直接出局,到时候看你面子往哪里放!

三、在虚拟出价上排序和计算第二高价,然后转换回真实出价来扣费。

诸位明公,这位Myerson先生高就高在,人家这个方法不是三脚猫、四门斗、胡乱拼凑的,而是从理论上保证了收入的最优。大家可能对这件事心存疑惑:这个机制既然这么好,那么多逐利的互联网公司,怎么没听说谁在用啊?嘿嘿,没听说就对了!Myerson拍卖最大的问题,就在于它是不公平的。王健林因为有钱,就被迫享受二等公民待遇。不管是苏富比还是佳士得,谁要敢宣布采用这种机制,马上就得让吐沫给淹死。

不过,用还是可以用的。您别忘了互联网卖广告这事儿,每天数以亿计的竞拍次数,就算是改成这种劫富济贫的机制,很难被广告主找到确凿的证据。因此,通过满怀恶意的猜测,和嚼老婆舌头获得的一手资料,我们可以不负责任地说:大公司广告平台实际采用这种机制的,恐怕不是什么新鲜事儿。当然,你永远也不会看到谁家的公关稿,说他们靠这个多挣了多少钱——他们总是把所有的成果都归功于大数据和人工智能。

最后,给熟悉计算广告的朋友们留一个思考题,不了解其中细节的可以无视这一段。在DSP的场景中,广告主向DSP出价参与竞拍,DSP又向外部的ADX出价以竞争广告位置,假设ADX采用的是第二高价,那么DSP应该如何根据内部广告主的bid,确定向ADX的报价,又如何决定在影得展示后扣广告主多少钱呢?(见下图,其中的b为bid,μ为点击率,r为RPM,p为payment)

好了,本文内容告一段落。还要声明一下,这篇文章是我很不系统地学习了清华唐平中老师博弈论课程后的学习笔记。如果您觉得有帮助,请感谢唐老师;如果有哪些谬误之处,那是我学艺不精。如果你希望交流上面的题目,或者有什么深入问题请教唐老师,麻烦您在公众号后台留言(请附上您的名片照片),谢谢!