本课程是北京大学开设的一门在线跨学科选修课程，主要面向信息技术、社会学和经济学等专业的本科生。课程内容涉及用计算思维的方法讨论社会学和经济学的一些经典问题。学习运用计算思维分析社会学、经济学问题的方法，加深对某些生活现象的理解，体会计算与社会科学的互动。 Learn to analyze and reason about problems in social sciences with computational thinking, appreciate interactions between computing and social sciences, as well as gain deeper understanding of some common phenomena in life and society
VCG：次价拍卖方式的优化推广
Loading...
Do curso por Peking University
人群与网络
99 classificações
Na lição
搜索引擎广告位的定价
本章主要讨论基于关键词的广告位销售问题和定价机制。结合前面章节讨论的匹配市场、单品拍卖以及博弈论的思想构建多广告位和多广告主之间的交易规则。采用三种不同的方法进行讨论，匹配市场的基本原则，GSP定价机制——单品次价拍卖直接扩展，VCG定价机制——单品次价拍卖优化扩展。进一步展示了这三种定价机制基于不同的理论和原则，形成广告位和广告主之间的匹配关系和价格各有不同，具有不同的性质和特点，理解它们之间的内在关系和性质有助于更好地理解前面章节涉及到的匹配市场、拍卖、博弈论。
Conheça os instrutores
李晓明 （Li Xiaoming）教授（Professor）
信息科学技术学院（School of Electronics Engineering and Computer Science）
邱泽奇 （Qiu Zeqi）教授 (Professor)
北京大学社会学系 （Department of Sociology）
王卫红（Wang Weihong）lecturer
School of Electronic of Engineering and Computer Science
这一节我们利用拍卖机制来为广告市场中的广告位进行定价。
在通常情况下，如果买家对商品的估值不能公开，
或者是这个商品它本身的一个价值它是一个不确定的，
它会因人因时因地产生一些变化的时候，这种情况下
通常人们会采用拍卖这种市场互动行为， 来进行相应的交易。拍卖有很多不同的
形式，综合来看呢，最基本的拍卖过程就是竞拍者
他以一个相应的出价来的盗被拍品，为此他需要为这个
被拍品支付一定的价格，那么从中他得到的回报应该是
对被拍品的一个估值减去为这个被拍品所支付的价格，拍卖成交的一个前估值
要比这个支付价格要大，所以他这个回报是一个大于0的数，
他才可以进行成交，否则的话，不可能成交。
那么通常呢，第3方或者是卖方制定相应的拍卖规则，
那么买方竞拍者基于这个规则来选择自己的一个最优策略，
基本目的，就是在赢得这个被拍品的同时，能够最大化它的回报。
我们就来看一下在搜索引擎广告市场中，广告主是如何来选择自己的 最优策略。
在搜索引擎广告市场的初期，人们采用了一种基于首价拍卖的
机制，也就是出价最高的广告主得到点击率最高的广告位，
同时他所支付的费用也就是他的出价。 我们知道首价拍卖师没有最优策略的，只有均衡策略，
也就是说竞拍者他会尽可能压低他的出价，
来期望得到更高的回报。那么同样的情况也在搜索引擎广告市场出现，
某个关键词的竟拍过程中，广告主会不断的调整他的
出价，希望以更低的出价来得到相应的广告位，
这样就使得整个拍卖过程非常的动荡和不稳定。
那后来人们就想到可不可以利用一些更优质的拍卖机制，比如说次价拍卖机制
来进行广告位的拍卖呢？ 我们知道单品次价拍卖
机制，它是出价最高的得到这个 拍品，那么他所支付的费用呢事实上是次高的出价，
同时呢，它是具有占优策略的，就是每个人
以他真实的对这个拍品的估值来出价是他的一个最优策略。
那么VCG机制，基于这种单品次价拍卖机制的一种优良推广。
好我们看一下
单品次价拍卖它的一些特点，我们现在有一个拍品， 那么有一些竟拍者，
假定我现在出价是从高到底依次排序，所以v1最高，v2次高，
那么显然最终是第1个竟拍者得到这个拍品，
他所支付的价格应该是v2。
我们来看，如果第1个人不出现，那么显然，第2个人得到这个拍品
所支付的价格是v3, 我们是不是可以这样理解，
如果第1个人不出现，第2的人得到了价值为v2物品，
那么因为第1个人出现了，第2个人
和第3个人以及后面的所有的人没有得到任何东西，
也就是说他们损失了价值为v2的物品。
那么因此，我们可以说， 第1个人他获得这个拍品，
付的这个价格V2可以理解成
因为他的出现，其他人所损失掉的这个价值。
这个2的含义就是补偿给其他人的损失。
好现在我们来看看是不是可以把这种思路推广到
广告市场中来。我们知道在搜索引擎广告市场中，有点击率不同的一些广告位，
那么还有点击出价不同的一些广告主，我们采用单品次价拍卖中的一个分配
原则，也就是说把广告位跟广告主之间进行一个最优的匹配，
我们知道，最优匹配的结果，事实上是把点击率
最高的广告位分配给了点击出价最高的广告主，
这样以此类推。那么这种分配它可以达到一个
最终的一个估值总和最高，它是一个最优分配。我们知道，每个广告主
对相应他所得到的这个广告位他的一个估值事实上就是他的点击出价
乘以这个广告位的一个点击率，这是我们之前讨论过的。现在我们就是要来看
一下，这个广告主得到了某一个广告位，他应该为这个
广告位支付的价格是多少？也就是说，怎么样来衡量，
因为这个广告主的存在，他对其余别人所造成的一个
价值损失是多少呢？ 好现在基于最优分配，
广告主X分到了广告位I，我们来看一下，应该如何计算，
这个广告主X因为得到广告位I而对其余人所造成的一个价值损失。
那么实际上，我们就是要看一下，当X分配到了
广告位I之后，其余人所得到的一个总的价值总和。
那么再来看一下，如果广告主X不存在，
其余人得到一个价值总和又是多少。如果广告主X得到了广告位I，
其余的广告主跟广告位之间再进行一个最优分配， 那么分配的这个结果，
有一个估值总和，我们称这个估值总和为Σ1。我们现在来看，
如果广告主X不存在，其余人再来作一个最优分配，那么这样的话，
点击出价排在广告主X之后的这些广告主，因为X不存在了，就会得到
一个更高点击率的一个广告位。我们知道，每一个广告主他的一个估值
事实上是他的一个点击出价乘以相应的广告位的一个点击率，
这样的话，这些排在X之后的广告主
他相应的估值就有一个提升，X不存在的情况下，
其余所有的广告主跟广告位之间的最优匹配我们说它总的一个估值
也同样有一个提升，我们称这个总估值为Σ2。那么事实上，
X应该为这个广告位所支付的价格就应该是Σ2减去Σ1。
所以我们说，在VCG价格机制中，
每一个广告主为广告位所支付的价格应该是两个价值总和的差。
下面我们通过一个例子来计算VCG价格。
那么有3个广告位a,b,c,点击率分别是10，5，2，
3个广告主x,y,z, 他的出价分别是3，2，1，当然这个出价是点击出价，
那么运用我们之前学过的计算方法，
我们可以计算出每个广告主他的一个估值。
这样呢，算下来就是说是x 对a的估值就是30，
对b的估值是3乘以5，15， 那么对c的估值就是6，最优的匹配就是x
匹配给a，y匹配给b,z匹配给c。我们来算一下他的需要支付的
VCG价格。那么首先我们来计算x需要支付的VCG价格。
那么我们就要看一下这个y和z 的一个价值总和在x存在和x不存在的情况下，它的差是多少。
我们看，如果x出现，那么它得到a,所以这样的话，那么y只能是
跟b匹配，z跟c匹配，
那么它得到的这个价值总和呢是10加2等于12。
这两个，看。
如果x不出现，那么y就可以匹配更高一个点击率的广告
a,z也可以提升一个匹配到b, 它们的得到的这个价值总和呢，就是应该20加上
5是25。 因为x出现，所以我们就可以理解成
对y和z造成的损失就是25减去12是13，
那么这个13就应该是广告主 x需要为广告位a所支付的价格。
当然这是一个单位时间里的价格。那么我们进一步来计算，
y和z的VCG价格，同样我们计算
y出现的时候，其他人得到的这个价值总和和他不出现的时候这个价值总和
这个之差就是应该，y要支付的VCG价格。
如果y出现的话，得到b，那么x得到a，z得到c，
就是x和z总价值是30加上2，
这两部分相加是32，
那如果y不出现，x不变还是匹配给a，z就提高了一个广告位，匹配给b,
这样的话，那么总价值是 30加5，应该是35，所以它们的差就应该是
3，35减32，所以这个3就是应该是
这个广告主y所应该为这个广告位b所支付的价格。因为c出现和不出现都不会影响，它是最后一个。
所以它的价格应该是0,那么这样我们就可以计算出
这x,y,z3个广告主他所应该支付的
价格是13和3, 0.
如果要算到点击价格就是要再除以它的点击率,转换成点击价格.
好,下面我们来给出VCG定价机制的一个一般性描述。
那么第1步，我们需要做一个最优分配，也就是
把广告位跟广告主之间进行一个最优分配。
我们之前也谈到了，那么如果将点击率最高的广告位
分配给点击初值最高的广告主，点击率次高的广告位分配给
点击初值次高的广告主，以此类推，这样的分配结果，它是一个最优分配。
同时，它可以达到所有广告主的估值总和最高。 那么这个估值我们用这个Vsb来表示。
接下来我们再来看每个广告主需要所支付的价格应该如何来定义。
那么假定在这个最优分配中，广告主j分配到了相应的广告位i，
所以他所应该支付的价格呢，我们来用这个符号来表示
除了i跟j，就是在整个的匹配中，不包含i跟j，
其余部分进行最优分配它所得到的一个估值总和。
那么我们再来用这个符号表示，当广告主j 不存在的时候，
其余所有广告位跟广告主之间进行一个最优匹配，所最终所得到的一个估值总和。
这个广告主j需要为广告位i所支付的价格，
就是应该用这个式子来定义，也就是说，他
不存在的时候，其他人所得到的一个价值总和减去
他存在了，并且也匹配到了相应的广告位
i之后，其他人所得到的这个价值总和，他们俩的差，
我们就定义成是这个广告主j
对其他人所造成的一个总的价值损失。接下来我们来看，
VCG定价机制是不是同样具备了单品次价拍卖的一些优质特性呢？ 事实上是肯定的，也就是说，
基于VCG定价机制的这个分配结果，实际上它是一个社会最优
分配，也就是说，它可以达到买方的估值总和为最高。
那么同时，这种定价机制，它是具备一种占优策略，也就是说如果每个
广告主能够按照自己对于点击估值的一个真实的估值进行出价的话，
这实际上是他一个最好的一个出价策略。
所以这里面是，这种机制是鼓励大家真实出价，鼓励大家讲实话的一种
机制。下面我们就来进一步证明，在VCG定价机制中，真实出价
是他的一个最好的策略。要证明真实报价是一个广告主的一个最优策略，
那么我们就需要证明，广告主在真实报价的时候，他所
得到的回报应该高于他虚假报价所得到的回报。
好，现在我们来看一下，在两种情况下，广告主分别得到的回报是多少。
假定广告主j真实报价，得到了一个广告位i， 那么他所得到的回报就应该是，
Vij是广告主j对i的一个真实估值，减去他所支付的一个
VCG价格，如果这个广告主没有真实出价，而是一个虚假报价，
这样的话他有可能会得到一个不同的广告位。假定他得到了一个另外一个广告位h， 那么他所得到的回报
就应该是广告主j对h的一个真实估值，减去他为h所应该支付的价格。
我们来比较一下这两个回报， 如果我们能够证明，左边永远大于等于右边，我们是不是就可以证明，
这个广告主他没有虚假报价的一个动机。
那这个不等式是不是永远都成立呢？
好，我们现在来利用估值矩阵，来分析一下，
某个广告主他得到相应的广告位所得到的回报应该是多少。我们这个
估值矩阵，横向，广告主，是按出价这样从高到低依次排序，那么纵向，不同的广告位，
也是按照点击率从高到低这样依次排序。估值矩阵里面的任何一个元素，
都是某个广告主对相应广告位，他的一个估值。
我们是由这个定义的，它的点击估值乘以相应的
广告位的一个点击率，因此这一列就是广告主j
他对不同的广告位的一个估值。 那么之前我们说了如果将这些广告主和广告位进行一个
最优匹配，那么得到的一个估值总和它是一个最高的，
所以我们用Vsb来表示这个最高的估值总和。
那么如果说，我们看广告主j，如果广告主j他真实报价，他会得到
分配到相应的广告位i，这样的话，他的
所支付的这个价格是由这个等式来定义。那假定
现在j决定虚假报价，他选择了另外一个报价， 这样的话，他就有可能
经过这个最优匹配的结果，会分到另外一个广告位h。
我们来看一下他要为这个h所支付的价格是多少。
同样采用刚才我们给出的定义，我们得到了这个等式。
那么我看看这个价格的第1部分，事实上就是所有的广告位
和不包含j在内的所有的广告主之间进行一个最优匹配，
它的一个最终的匹配结果的一个估值总和。那么第2部分，
事实上是不包含广告主j和广告位h，
其余部分进行最优匹配的一个匹配结果的一个估值总和。 那么从这个等式我们可以看出，
j他需要所支付的这个价格事实上是跟他虚假的这个报价这个值是没有关系的。
也就是说，不管是j经过真实报价，
还是虚假报价，他一旦得到了这个广告位h，他所支付的价格就是由这个等式来
确定，也就是说，如果j选择虚假报价，
对他的影响，只是他可能得到了另外一个不同的广告位， 而他为这个广告位所支付的价格，
跟他虚假报价也好，真实报价也好，是没有关系的，是由其他人的出价而决定的。那么因此，
这两种回报，就是真实报价的回报和虚假报价的回报，
事实上，也跟j的虚假报价这个值是没有关系的，
也是由其他人的出价来决定的。这个是我们
通过这个估值矩阵所分析出来的一个结论。
接下来我们把这两个VCG价格代进来，
两边进行简化，就得到了这个不等式。 好，下面我们来继续证明，这个不等式它的成立。
首先我们看左边。继续利用刚才我们给出的这个估值矩阵。
我们说，如果对广告主跟广告位
进行一个最优匹配，将产生一个最大的一个估值总和。
那么如果j真实报价，经过最优匹配，他将分配到相应的广告主i，这个Vij
是广告主j对i的一个真实估值。那么我们来看第2部分，这一部分
实际上就是说在所有的广告主跟广告位不包含j跟i
的情况下，其余部分进行最优匹配的一个估值总和。
我们说本身i分配到了j，就是一个最优匹配中的一部分，
所以再加上其余部分的一个最优匹配，
整个这部分，事实上这两个估值之和就是一个
整个广告主跟广告位之间的一个最优匹配的一个估值总和。
也就是说他等于我们之前给出的这个最高的一个估值。我们再来看右边，
是在j没有真实出价 的情况下，分配给了另外一个广告主h，
所以Vhj就是j对h的一个真实估值。 那么，第2部分，
实际上就是不包含j和h，
其余的广告主和广告位之间进行最优匹配的一个估值总和。
那事实上，这部分的和我们可以理解成，
在j匹配给了h这个前提之下，其余部分进行
最优匹配的一个估值总和。我们说，
j匹配给h它并不是一个最优匹配中的一部分，
也就是说，整个这一部分，也是一种分配结果。但是这个分配结果，
它并不一定是一个最优的，我们说这个是一个最优分配的一个估值总和，
所以他的估值是最高的。右边实际上是在有一个受限条件，
就是在j已经匹配给了h这个前提下，其余部分的一个估值总和。 因此，
他应该是小于等于没有任何条件下的一个最优匹配的一个估值总和。这样，我们就证明了
这个不等式它是成立的。也就是说，
真实报价的一个回报会永远大于等于他虚假报价所得到的回报。
所以广告主它是没有这个动机再来进行虚假出价的。我们就，就证明了
真实出价，讲真话是每个广告主
他的一个占优策略。下面我们来简单做一下小结。
这一节我们介绍了，在广告市场中，为广告位进行定价的这种VCG定价机制。
那么同时我们分析了这种定价机制它的一些优质特性，也就是说，首先它是一个
社会最优，它的分配结果能够达到所有广告主对广告位的一个估值总和最高，
同时它具有占优策略，也就是说，如果广告主
真实报价，那么他将得到更高的回报，在实际中，
一些搜索引擎公司是采用了另外一种称为GSP的定价机制。
GSP也是次价拍卖机制的一种推广形式。我们说GSP并没有VCG的一些优良特质，
但是因为它的用户友好性以及其他的一些特点，在实际中很多搜索引擎
公司是采用了这种定价机制，我们将在下一节介绍GSP定价机制。
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
