关键词拍卖和广义二阶拍卖(Internet Advertising and the Generalized Second-Price Auction译文)...

转载自：关键词拍卖和广义二阶拍卖(Internet Advertising and the Generalized Second-Price Auction译文)  

有些公式，懒得用Word敲了，虽然Word 2007也有一些类似Latex的功能了，但还是无法和Latex相比，这篇论文引用数1000，属于少见的好论文，它在工程上没有什么指导意义，但它解释了很多非常关键的东西。

今天初校了一遍，pdf下载地址：http://koalaquwei.ucoz.com/_ld/0/76_GSP.pdf

 

 

本文将讨论一种新的拍卖机制，我们称它为Generalized Second-Price拍卖，或是GSP。GSP是为在线广告这个特定的环境而设计的。
我们对GSP的兴趣来源于它所取得的巨大的商业成功。Google 2005年总收入是$61.4亿元。超过98%的收入来自于GSP拍卖。
Yahoo!在2005年的总收入是$52.6亿，超过一半的收入来自于GSP拍卖。到2006年6月，GSP的市场价值超过$1500亿。

下面简单描述一下拍卖是如果进行的。当一个搜索引擎用户在搜索引擎中输入一个关键词(查询词)，
他会得到一页返回结果，页面中包含与这个关键词最相关的网页信息和一些赞助链接，比如：付费广告。
这些广告与真正的搜索结果有明显的区别，搜索不同的关键词会得到不同的赞助链接：
广告主会针对搜索关键词投放广告。比如，如果一个旅行社购买了关键词"Hawii"，那么每次有用户搜索"Hawii"这个关键词，
结果页面就会显示这个旅行社的链接。当一个用户点击这个赞助链接，就会跳转到广告主的页面。
每一次点击，广告主就需要向搜索引擎公司为这次点击付费，所以这种收费模式的名字是"Pay-per-click"收费。

一个页面上所能展示的广告个数是有限的，页面上不同的展示位置会有对广告主有不同的吸引力：
在页面顶部的广告比页面底部的广告更可能被点击。所以搜索引擎需要一个系统来为这些广告分配展示位置，
那么拍卖就是一个很自然的选择了。现在搜索引擎所使用的拍卖机制大多基于GSP。

在最简单的GSP拍卖中，对于一个特定的关键词，广告主给出他对一次点击的最高出价。
当用户输入一个关键词，用户会得到搜索结果和赞助链接，赞助链接是以广告的出价降序展示的。
出价最高的广告展示在最顶部，出价次高的展示在第二个广告位，以此类推。
如果一个用户点击了位置$i$上的广告，广告主需要付下一个广告的出价，就是位置$i+1$上的广告出价。
如果一个搜索引擎只展示一个广告，那GSP机制就与标准的Second-Price或是Vickrey-Clarke-Groves(VCG)没有区别。
当有多个广告位时，在GSP机制下，每个广告主对每次点击付费为下一名的出价。我们将会解释，
这种多个广告位的GSP拍卖与VCG不等价，并缺乏一些VCG的一些好的特性。
特别是，不同于VCG机制，GSP一般在占优策略中没有一个均衡点。

 

 

Internet广告的一些相互影响的特性使得它很独特。首先，每次的出价是可变的。
一个广告者对一个特定的关键词的出价，在他没有改变广告出价或让广告下线之前，每次搜索引擎的扣费都是针对这个出价的。
比如，在某一时刻，一个广告者在一个关键词上的出价是第二名，那么这时用户搜索这个关键词时，它的赞助链接会在这一时刻排到第二名。
但是，下一次用户再搜索这个关键词时，这个广告可能会排到别的位置，因为广告主可能会改变这个广告的出价。

其次，搜索引擎能有效地销售一些有时限的广告服务，广告主可以对广告投放时间进行限制。
如果在某一时期没有人对特定的关键词投广告，那这部分关键词就不能带来收入。

最后，Internet广告通常不能清晰地衡量它的销售，对参与者们来说Internet广告没有一个很自然的单位。
从广告主的角度来讲，单位应该是平均花费了多少钱吸引一个用户。它对应的模式是：只有当用户完成购买后才付费，即Pay-per-Sale付费模式。
从搜索引擎的角度来讲，单位应该是平均每次展示，自己的收入是多少。
它对应的模式是：每次展示广告就需要付费，即Pay-per-Impression。而Per-per-Click是介于这两个模式之间的一种模式，
广告者在用户点击广告时需要付费。这三种模式在Internet使用很广泛。在我们的研究中，我们发现Internet广告中的关键词拍卖，
所用的模式都趋向于采用pay-per-click模式。

GSP中每个广告主对每个关键词只能给出一个出价——尽管可能是不同的商品出售(在不同的广告位)。
GSP的不寻常出价要求在下面的场景中是合理的：每个广告位的价值区别在于每个广告位所能带来的点击量不同，
一个广告在较高的位置的好处在于这个广告得到的点击更多，但是在不同的广告位上广告的一次点击对广告主的价值是相同的
(比如，相同的购买机率)。结果就是，尽管GSP是一个多元素的环境中，购买者的估价却可以用单无素充分表达。
对一些广告主来讲，每个关键词一个出价，可能无法充分表达他们的意向。
比如，单一出价忽略了点击第5个广告位与点击第2个广告位用户的不同性，等等。
不管怎么讲，这些限制显然不足以成为让竞价变复杂的理由。
Nico Brooks(2004)发现在不同的广告位展示的广告对影响用户购买机率只有很小的差别。

我们还忽略了一个重要的因素，就是点击率，比如，在同一个广告位，两个不同的广告有着不同的点击率。
(这个在业界被称为"click-though-rates", 或CTR)。不同的引擎对点击率的态度不同。
Yahoo!直接忽略点击率，仅按用户的出价的降序对广告进行排序，并按下一名广告主的出价扣费。
Google将用户的出价乘上广告的质量得分("Quality Score")，质量得分的计算基于CTR和其它因素，
质量得分被用于广告排序，每次点击付费为下一名的出价加上一个很小的值。

subsection{Evolution of Market Institutions}

关键词拍卖的历史是分析市场对各种模型所做出的反应。最近许多新的模型从零开始设计，并代替历史上出现过的模型：
以及其它。但是搜索广告拍卖也是一步步地进步的，有缺点的模型逐步被更好的设计代替，
值得注意的是Internet广告增长速度很快。这可能是因为模型设计者身上的压力比较大，并且模型实验的开销也比较小。

我们以时间顺序简单地回顾一下关键词拍卖机制。

早期的Internet广告. 早在1994年，Internet广告主要是以展示次数方式计费的。
广告者按固定的展示次数收费(常见的是按每一千次计费)。合同都是基于一个个广告来的，
最小的合同所要支付的费用都不少(通常是几千美元一个月)，入帐很慢。

广义一阶拍卖，在1997年，Overture(后来的GoTo, 现在是Yahoo!的一部分)引入一个全新的Internet广告销售模型。
在早期的Overture拍卖设计中，对于一个关键词，广告者提交一个出价，表示他愿为每次点击所出的价格。
广告主现在可以定向他们的广告：不同于以前的模幅广告，每个浏览者在一个网页上都会看到，
而是广告者可以指定与他们产品相关的关键词，并可以指定每个关键词的价格(或者，更准确地说，
一个用户在搜索关键词之后才会点击广告)，这对广告主们更有利。同样广告不再以每千次展示的方式计费，
而是按每次点击的方式计费。每次一个用户点击一下赞助链接，广告主的帐户就会自动地按广告主最后的出价扣费。
广告者的广告链接是以出价的逆序排列的，使得出价最高的广告放在最显著的位置上。
由于它的易用性，交易费用很低，并且机制对广告者透明，这些因素使得Overture成为一个成功的搜索广告平台，
并且成为了包括Yahoo!和MSN在内的大搜索引擎的广告提供商。但是它成功底下的拍卖机制却远非完美。
特别是，Overture和广告者们很快发现了这种拍卖机制是不稳定的，因为出价可以很频繁地改动。

例子，假设一个页面上有两个广告位，且有三个广告主。第一个广告位每小时可以获得200次点击，
第二个广告位可以获得100个点击。广告主1，2和3对每个点击的估价分别是$10, $4, $2。
假设广告者2出价$2.01，以保证他可以得到一个广告位。那么，在这种情况下广告主1的出价不会高于$2.02。
因为他不需要花更多的钱来得到第一个广告位。
但如果广告主2想更改出价为$2.03，以获得第一个广告位，那么广告主1就会抬高出价到$2.04，以此类推。
显然，在这个博弈中没有一个纯粹的平衡点，所以广告主们都会根据对方的动作做出最佳的反应，
结果就是他们会趋向于频繁地改动出价。

一些广告主使用了自动竞价程序，它会使搜索引擎的收入变少。David McAdams和Schwarz(2006)指出，
广告主在搜索广告上的博弈费用会直接转嫁到搜索引擎上，并且即使是广告主对关键词的估价很高，
但是由于自动竞价程序能快速更改出价，也会使得引擎引入很低。比如，在上面的例子中，
假设广告主1有自动竞价程序，广告主2和3都是手动竞价，最多一天更改一次出价。
那么情况就是只要广告主3不提交高于他估价的出价，那么引擎一次点击最多收入$2.02，
假设广告主3出价$2.00，如果广告主2出价$2.01，他会得到第二个广告位，但如果他出价高于$2.01并且小于他的估价，
他会仍然排到第二个广告位，并且每次点击付更多的费用，这是因为广告主1的自动竞价程序能很快地提交高于广告主2的出价。
即使在广告主1和2对关键词估价很高的情况下，引擎的收入仍然不会有任何变化。

广义二阶拍卖，在广义一价定价拍卖中，能快速改变广告出价的广告主有着巨大的竞争优势。
这种拍卖机制实质上鼓励了广告主们在这个系统中博弈，博弈的结果就是导致出价和配置低效，影响了引擎的引入。
Google在2002年它提出自己的pay-per-click系统Adwords Select时指出了这个问题，
Google还指出了在广告位$i$的广告主只愿意比$i+1$广告位的广告主多出一点，
Google将这个现象融合进了它新设计的GSP拍卖机制中，在最简单的GSP拍卖中，
在第$i$个广告位的广告每次点击所付的费用，等于第$i+1$个广告位的广告出价加上一个很小的值(一般是$0.01)。
这种二价定价方式使用广告主之间更友好，并更少地受到博弈的影响。

认识到这种优势，Yahoo!/Overture也换用了GSP。下面描述一下它实现的GSP版本。
每个广告主提交一个出价，广告是以广告主们出价的逆序顺序展示在页面上的。
排在第一个广告位上的广告被点击后所付的费用是第二个广告主的出价加上一个小的值，
第二个广告主是付第三个广告主的出价加上一个小的值。以此类推。

例子。让我们考虑一下先前例子中使用GSP的情况。如果所有广告者都诚实的出价，那么出价就是$10
$4，$2。在GSP中付费金额是$4和$2。在这个例子中诚实的出价的确是一个平衡点，
因为没有广告主可以通过改变他的出价获利。注意广告主1和2所付的费用分别是$800和$200。

广义二价拍卖和VCG拍卖。GSP看起来像是Vickrey-Clarke-Groves机制，
因为两种机制中，广告主的付费都是基于广告位和其它广告主的出价的，而不是基于广告主自己的出价。
事实上，Google的广告材料中明确地引用了Vickrey并写到Google的"独特的拍卖模型使用了诺贝尔经济学奖得主的理论以来消除...
你付费太多的感觉"。但是GSP不是VCG。特别是，不同于VCG拍卖，GSP没有纳什均衡点，并且诚实出价在GSP中不是一个均衡策略。
在只有一个广告位的情况下，VCG和GSP是一致的。有多少广告位时，两者就不同了。
GSP中第$i$位的广告主是的计费是按第$i+1$位的广告主出价，而在VCG中，广告主$i$的出价是按他占用了第$i$个广告位所带来的影响来定价的，
即如果$i$没有出现可以给其它广告主带来的点击收益之和。注意在第$j$($j < i$)个广告位上的广告主不受$i$的影响，
然而当$j>i$时，如果$i$没有出现，那么$j$就会排到$j-1$名，那么$i$对$j$的影响就是$j$对每次点击的估价乘以广告位$i$和$j-1$点击数的差别。

例子，让我们计算一下上面例子中使用VCG的付费情况，第二个广告主如上例一样付费$200。但是第一个广告主的付费总额是$600，
$200为是因为他影响了广告主3(使广告主3得不到第二个广告位)，$400是因为它对广告主2的影响(使广告主2从第1个广告位掉到第2个广告位，
使它每小时损失(200-100)=100次点击)。注意，在这个例子中，VCG机制下的收益不如GSP。
如我们稍后将展示的，如果广告主们在两种机制下都诚实出价，那GSP总是能取得更高的收益。

subsection{Assessing the Market's Development}

上节以时间顺序介绍了关键词拍卖的三个时代。第一个时代，广告以手工方式出售，很慢，一次大量销售，并按每次展示的方式出售。
第二个时代，Overture实现了关键词定向的点击销售方式，并成为广告销售的主流方式，并且有着自助的竞价接口，
但它使用了非常的不稳定的一价竞价机制。最后，Google实现了GSP，并最终被Overture(Yahoo!)接受。

有趣的是，Google和Yahoo!仍然使用GSP，而不是VCG，尽管VCG会减少广告主们博弈的动机，并会使他们工作更轻松点。
我们来看几个可能的原因。首先，VCG的的扣费规则很难向一般用户解释。第二，切换到VCG也许会引起巨大的转换代价：
在相同的出价的情况下，VCG的收入不如GSP，并且广告主们会延长逐步降低他们出价的过程。
第三，转换到VCG上的收入结果是不可知的。并且简单地实现和测试一个新系统可能会昂贵——
它增加了广告主和搜索引擎转换的成本。

section{The Rules of GSP}

让我们现在形式化地表达关键词拍卖。对于一个指定关键词，有$N$个广告位，和$K$个广告主。
在第$i$个广告位上的广告一定时间的点击次数是$alpha_i$。每次点击对广告主$k$的价值是$s_k$。
广告主是风险中性的，广告主$k$在广告位上的收益是$alpha_i s_i$减去他要向搜索引擎所付的费用。
注意这里的假设暗含了广告的点击量不依靠于广告位的位置。不失一般性，广告位是以出价降序排序：
对于任意$i<j$，有$alpha_i>alpha_j$。

我们下面对GSP进行建模。假设在某一时刻$t$，一个搜索引擎用户搜索了一个特定关键词，
对于每个广告主$k$，设他在$t$之前的最后出价是$b_k$，如果广告主$k$没有出价，我们设$b_k=0$。
令$b^{(j)}$和$g(j)$表示第$j$个广告主和广告主本身。然后GSP会把最上面的广告位分配给出价最高的
广告主$g(1)$，第二个广告位分配给$g(2)$，以此类推，直到$min{N,K}$，注意每个广告主最多得到一个广告位。
如果一个用户点击了一个广告主的链接，广告主的付费是下一名的出价。所以对于$iin{1,...,min{N,K}}$，$g(i)$的总付费$p^{(i)}$是
$alpha_ib^{(i+1)}$，并且他的收益是$alpha_i(s_{g(i)}-b^{(i+1)})$。
如果广告主个数多于广告位$Ngeq K$，那么最后一个广告主的付费$p^{(K)}$等于0.

用这些符号来表示VCG机制，VCG的排序规则是与GSP相同的：第$i$个广告位分配给出价$b^{(i)}$，第$i$高的广告主$g(i)$。
但是所付的费用是不同的。每个广告主的所付的费用是它给其它广告主造成的负面影响，假设广告主的出价等于他的真实估价。
最后一个得到广告位的广告主所付的费用是一样的，如果$Ngeq K$为0，否则为$alpha_N b^{(N+1)}$。
对于其它$i<min、{N,K、}$，在VCG下的付费$p^V$不同于GSP下的付费。$p^{V,(i)}=(alpha_i-alpha_{i+1})b^{(i+1)}+p^{V,(i+1)}$。

在下二节中，我们将考虑两种方式来完成这个模型：其一为有全部信息的同时改动博弈，
模拟密封二阶定价拍卖，其二为扩展的有着不完全信息的博弈，模拟英式拍卖。在讨论这些模型之前，
让我们再讨论一下GSP和VCG的特性。

REMARK 1: 如果所有的广告主在两种机制下出价都是一样的，那么在GSP机制下的收入不小于和VCG机制下。

很容易用归纳的方法来得到这个结论，从最后一个广告位的广告主开始。
对于$i=min{K,N}$，$p^{(i)}=p^{V,(i)}=alpha_i b^{(i+1)}$。
对于任意$i<min{K,N}$，$p^{V,(i+1)}-p^{V,(i+1)}=(alpha_i-alpha_{i+1})b^{i+1}leqalpha_i b^{(i+1)}-alpha_{i+1}b^{b+2}=p^{(i)}-p^{i+1}$。

REMARK 2: 在VCG下，诚实出价是一个占优策略。

这是VCG机制一个重要特性，不解释。

REMARK 3: 在GSP下，诚实出价不是一个占优策略。

比如，考虑将第一节中稍做改动的一个例子。仍然是三个广告主，两个广告位，对点击的估价分别是$10，$4，$2。
但是这两个广告位带来的点击率差不多：第一个广告位每小时200次点击，第二个广告位199次点击。
如果所有的广告主都诚实的出价，那么广告主1的收益是($10-$4)*200=$1200。如果，
相反，它减少它的出价到$3，那么他会得到第二个广告位，他的收益等于($10-$2)*199=$1592 > $1200。

section{GSP and Locally Envy-Free Equilibria}

在Yahoo!和Google上的广告主可以频繁地改变他们的出价，所它我们可以视关键词拍卖为一个连续或不断进行的博弈，
在这个博弈中，广告主最初只有他们自己的估价信息，但渐渐地他们掌握了其它人的估价信息，并可以不断地修改他们的出价。
原则上，这个不断博弈的平衡点集合会很大。然后，要支持这种平衡的策略通常很复杂，并要准确了解环境和小心的实现。
在理论上，广告可以通过自动竞价程序来实现这种策略，但在实践不太可行，，因搜索引擎不会授权给自动竞价程序，
而且也不太可能允许这种广告主串通，会导致自身收入减少的策略。

我们先关注一些简单策略，并了解竞价过程中的其它因素：如果出价的向量是趋向稳定的，那么在什么出价时会稳定呢？
我们先提出一些假设和限制条件。第一，我们假设所有估价都是公开的：即随着时间，广告主可能会掌握互相之间的所有相关信息。
稳定时的广告主们的出价值必须对他们相互都是一个最优策略——否则，一个广告的出价不是最优策略，他就有动机去改变出价，
就会把稳定打破。所以，我们假设所有出价形成的平衡点是在一个有着完整信息的同时出价的一次性博弈。
第三，一个广告主在知道其它广告主的出价时，用什么样的简单策略可以增加它的收入呢？

一个明显的策略是将自己前一名的广告主挤下去。假设位置$i$的广告主$k$的出价是$b_k$，
位置$i-11$的广告主$k'$的出价是$b_{k'}$，$b_{k'}>b_k$。注意如果$k$稍增加一点他的出价，
它自己的收益不会改变，但他上一名的广告主的收益会减少。当然，广告主$k'$可以报复，
他最多能做到的就是把自己的出价降到刚好比$k$的出价低一点，使两个广告的位置交换。
如果$k$在这种报复下能得到更好的收益，那么他的确是想排在$k'$前面，
那种这个出价的向量就会改变。所以，如果这个向量收敛到一个静态的点时，
在位置$i$的广告主不会想要与位置$(i-1)$交换位置。我们称这种出价的向量为"locally envy-free"。

DEFINITION 1：在GSP下的同时出价博弈中的平衡点是locally envy free，
locally envy-free是指一个广告主无法通过得到前一个位置来取得更好的收益。
更形式化地，在一个locally envy-free平衡点中，对于任意$ileq min{N+1, K}$，

$$alpha_i s_{g(i)}-p^{(i)}geq alpha_{i-1}s_{g(i)}-p^{(i-1)}$$

当然，出价会随着时间改变是可能的，因为出价依赖着广告主的策略和信息结构。
但是在GSP下的同时出价博弈中竞价一旦收敛到一个出价向量，那么这个出价向量就对应一个"locally envy-free"平衡点$Gamma$。
所以，我们视一个locally envy-free平衡点$Gamma$为一个趋向稳定的出价向量中的一个稳定点。
在本节中，我们将研究locally envy-free平衡点。

考虑每个广告位都是一个代理商，这个代理商在找一个匹配的广告主。一个广告位-广告主$(i,k)$的估价是$alpha_i s_k$。
我们称这为分配博弈A。广告主通过付费$p_{ik}$得到这个广告位，
广告主的收益就是$alpha_i s_k - p_{ik}$。下面的两个引理会指出GSP的locally envy-free平衡点集合与稳定的配置有着一个自然的关系。所有的证明都可以在附录中找到。

引理1：拍卖$Gamma$的任何locally envy-free平衡点的结果都是一个稳定的分配。

引理2：如果广告主的数量大于现有的广告位，那么任何稳定的分配都是一个locally envy-free结果。

我们现在构造博弈$Gamma$的一个特定的locally envy-free的平衡点。这个平衡点有两个重要的特性。
首先，在这个平衡中广告主所付的费用恰与VCG中的占优策略中的付费一致。第二，
这个平衡点是对于搜索引擎最差的locally envy-free平衡点，但对于广告主是最佳的locally envy-free平衡点。
所以，搜索引擎在任何GSP下的locally envy-free平衡点的收入都会至少VCG中的占优策略中的一样。

考虑下面的策略$B^*$。不失一般性，假设广告主是以他们的估价逆序排列的，比如，如果$j<k$，那么$s_jgeq s_k$。
对于每个广告主$jin{2,...,min{N+1, K}}$，出价$b_j^*$等于$p^{V,(j-1)}/alpha_{j-1}$，
其中$p^{V,(j-1)}$是$j-1$个广告主的付费，它是在其它广告主都诚实出价的VCG中的一个占优策略。
出价$b_1^*$等于$s_1$。

定理 1：策略$B^*$是博弈$Gamma$的一个locally envy-free平衡点。在这个平衡点中，
每个广告主的位置和费用都与VCG中的最优策略一致。那么在博弈$Gamma$中的任何locally envy-free平衡点的收入都至少和$B^*$一样。

要证明定理1，我们首先要注意在策略$B^*$中的费用与VCG中的一样，
并且要验证$B^*$的确是一个locally envy-free平衡点。因为在构造时，我们已经让广告主不关心是否保持广告位还是与上一个广告位交换。
接下来，通过引理1我们知道每个locally envy-free平衡点都对应一个稳定分配。
稳定分配集合的"coreelongation"属性意味着在集合中存在一个"对广告主最优"的分配，
即在集合中的其它分配广告主所付的费用至少与A相同。更一步，Leonard and Demange et al.
在分配博弈中，对广告主最优策略分配中广告主的收益与VCG中的相同。
那么这已经足已完成证明了。我们下面给出一个我们这个特定环境的独立的证明。

在这个模型中，我们假设所有的广告主除了对每次广告的估值不同，在其它方面都是相同的。
在点击率上也是相同的。但即使广告主有着不同的点击率，分析也是基本一致的。
如果任意广告主$k$在广告位上有$alpha_i beta_k$次点击，
其中$alpha_i$是一个位置相关的因子，$beta_k$是一个广告主相关的因子。
我们下面将Yahoo!和Google的GSP版本分别进行分析。

在Yahoo!的系统中，广告主仍然是按出价的高低进行排序的，每个广告主按下一个广告主的出价收费。
对任意$i$和$j$达到locally envy-free平衡点时满足$alpha_ibeta_{g(i)}(s_{g(i)}-b^{(i+1)})geqalpha_jbeta_{g(i)}(s_{g(i)}-b^{(j+1)})$。
两边同除$beta_{(g(i))}$，我们得到$alpha_i(s_{g(i)}-b^{(i+1)})geqalpha_j(s_{g(i)}-b^{(j+1)})$，
那么在Yahoo!版本下的GSP，平衡点不受$beta$的影响。

在Google的系统中，每个主都被赋予一个排序值。这个排序值是广告主的出价和质量得分$gamma_k$的乘积。
所以在Google系统中，$g(1)$是排序值最高的广告主，$g(2)$是排序值次高的广告主，以此类推。
广告主所付的费用为$x^{(i)}=gamma_{(g(i+1))}b_{i+1}/gamma_{g(i)}$。
对任意$i$和$j$达到locally envy-free平衡点时，$alpha_ibeta_{g(i)}(s_{g(i)}-gamma_{g(i+1)}b_{g(i+1)}/gamma_{g(i)})geqalpha_jbeta_{g(i)}(s_{g(i)}-gamma_{g(j+1)}b_{g(j+1)}/gamma_{g(i)})$。
两边同除$beta_{g(i)}$，然后同乘$gamma_{g(i)}$，我们得到$alpha_i(gamma_{g(i)}s_{g(i)}-gamma_{g(i+1)}b_{g(i+1)})geqalpha_j(gamma_{g(i)}s_{g(i)}-gamma_{g(j+1)}b_{g(j+1)})$。
所以，在Goolge版本中的GSP的locally envy-free平衡点是与位置因子${alpha_i}$，广告主质量得分$gamma_k$，和点击估价$s_k$相关的。

section{Main Result: GSP and Generalized English Auction}

在上一节中，我们假设用户在长时间的竞价过程中掌握了彼此的估价，并最终收敛到一个平衡点，并没有动机再去改变出价。
但是他们如何收敛到这样一个平衡点的呢？在这本节中， 我们引入广义英式拍卖，它类似于标准英式拍卖，并用它来帮助我们回答这个问题。

Sorry，翻译不下去了。

 

end{CJK}
end{document}