赞助搜索拍卖的 机制设计 作为一个例子，我们在第1章提到了赞助搜索拍卖问题。在本章，我们详细研究这 个问题来说明机制设计的迷人应用。我们首先给出了这个问题的机制设计表达形式。使 用这个表达形式，我们描述了赞助搜索拍卖领域的两个著名机制：一是广义第二价格 （generalizedsecondprice，GSP）拍卖；二是维克瑞-克拉克一格罗夫斯（VCG）拍卖。 然后，我们给出了最优拍卖机制（optimalauctionmechanism，OPT），它是上一章的迈 赞助搜索拍卖的机制设计 尔森最优拍卖的推广。最优拍卖机制（OPT）使得搜索引擎的期望收入最大，这里的约 束条件为贝叶斯激励相容与个体理性。接下来，我们比较了GSP、VCG以及OPT机 制。本章基于参考文献[1]，也基于参考文献[2]中的第3章。 广告赞助网站是网络版图中的一种成功的商业模式。各个行业的广告客户和营销商 在很短的时间内就接受了在互联网上做广告的做法。对于任何搜索引擎公司来说，赞助 搜索或称付费搜索已成为它收人业绩的关键决定因素之一。本章的兴趣在于将基于广告 的赞助搜索作为机制设计问题进行研究。 22.1赞助搜索拍卖 当互联网用户（下文有时简称用户）在搜索引擎中输人一个关键词（即搜索短语） 时，用户就看到了一个网页，这个网页含有与上述关键词最相关的链接，也含有赞助链 接（付费广告）。当用户点击赞助链接时，他就被引导到广告客户（我们有时也简称为 客户）的网页。对此引导结果，广告客户向搜索引擎支付一定的费用。图22一1描述了 我们在谷歌上使用关键词camera（照相机）进行搜索的结果。这个网页有两个不同的

栈，左侧的栈含有与关键词最相关的链接，右侧的栈含有赞助链接。通常，一些赞助链 接被放在搜索结果的上方。这些赞助链接明显和实际搜索结果不同。然而，赞助链接的 醒目程度取决于它在结果网页上的位置（slot）。一般来说，一些广告客户希望他们的广 告与搜索结果并排呈现。然而，用于展示赞助链接的位置有限。因此，对于互联网用户 的每次搜索，搜索引擎面临将广告与位置进行匹配的问题。另外，搜索引擎还需要确定 对每个广告客户收取的费用。广告客户自然偏好醒目程度高的位置。因此，为了配置位 置并且确定相应要价，搜索引擎需要一个系统。由于客户对广告空间的需求不断增加， 大多数搜索引擎使用拍卖机制作为应对之道。这些拍卖称为赞助搜索拍卖（sponsored searchauction）。在典型的赞助搜索拍卖中，广告客户受邀对关键词报价，也就是说， 对于广告的每次点击，客户表达他愿意支付的最大钱数。这通常称为每次点击费用 （cost-per-click，CPC）。根据广告客户对特定关键词递交的报价，搜索引擎（我们有时 称为拍卖商或卖者）选择一组广告以及它们呈现的顺序。搜索引擎的实际要价也取决于 客户递交的报价。 Google camora Wob Maps Asout 1,900;9ot;000 nesits (0.2% secrmes Canera-wikipodia,thefreeoncyclopedia Ads Nikon Next: Digital is a device WWE.UEhEdLCaF Digial camera-Wikinedia.thereeencycopedia CenonCamera Camcorders FreeHomvyExe LowstPris.1YRWay ecoingmgesoanelerricmgesensotMostns soldioayare BuyDigitaCameOeBestPrcesindia:TopRati 31pelBanKaka fic Ang eors & Shoc SamsungDigitalCaeras NkonCanoras-SLR:Cam wtHD Shocting.Check ow lnages forcaumera -Repart inages FuiflmX-Pro1Camera www.fujfemcamras.in/ gaabie ans eaanora Knowmore ioday High Quality Micro Camera 图22一1在谷歌上搜索camera时出现的结果 22.2作为机制设计问题的赞助搜索拍卖 假设某搜索引擎收到了互联网用户的关键词搜索，它立即面临将与该特定关键词相 关联的广告空间拍卖出去的问题。假设： （1）有n个广告客户对这个特定关键词感兴趣，N={1，2，，n）代表这些广告 客户构成的集合。另外，搜索引擎有m个广告位置，M={1，2，"，m）表示这些广 告位构成的集合。 （2）α是当广告客户i在广告位置j时得到互联网用户点击的概率，其中位置1表 示最高位置（最醒目位置）。我们假设α满足下列条件： 1≥ail≥aiz≥“ain≥0,iEN (22.1)

注意，在这里，我们假设点击概率α不取决于其他广告客户分配到了其他什么位置。 我们将这个假设称为客户彼此之间不存在配置外部性（absenceofallocativeexternali- ty)。 （3）每个广告客户准确知道当任何互联网用户点击一次他的广告时，他能得到多少 价值。我们假设这个价值与广告位置无关，而且这个价值仅取决于用户是否点击他的广 告。然而，广告客户i不知道其他客户从互联网用户的一次点击中得到的价值。正式 地，我们假设广告客户i观察到参数或信号0，其中0代表他从用户的每次点击中得到 的价值。参数0称为广告客户i的类型，此人的各种可能类型构成的集合记为。 （4）每个广告客户认为任何其他广告客户的评价抽自某个概率分布。类似地，每个 广告客户知道其他客户认为他的评价抽自某个概率分布。更准确地说，对于广告客户 （i=1，2，，n），存在某个累积分布函数Φ（·），他的评价0抽自（·）。令 p（·）是对应于Φ：（·）的概率密度函数。我们假设0在闭的实区间[0，0］内取 值。也就是说，Φ=[0，0丁。我们还假设各个广告客户的评价在统计上彼此独立。也 就是说，Φ（·）（i=1，2，，n）彼此独立。我们将这个假设称为私人价值的独立性 (independentprivatevaluesassumption)。 （5）每个广告客户i是理性的和智能的，也就是说，他追求效用函数u：X×O→R 的期望值最大，其中X是结果集，我们稍后给出定义。 （6）概率分布函数Φ（·），类型集，“，以及效用函数u（·）都是广告客 户的共同知识。注意，广告客户i的效用函数u：（·）取决于结果x与类型0。尽管类 第 型0：不是共同知识，但我们前面已假设u：（·）是共同知识，这意味着对于任何给定的 真 类型0，拍卖商（在这种情形下，为搜索引擎，也就是卖者）以及每个其他广告客户都 可以估计客户i的效用函数。 赞 助 根据上面的模型假设，赞助搜索拍卖问题可以准确阐述如下。对于任何搜索关键 搜 词，每个感兴趣的广告客户i报价6≥0，这里6仅取决于他的实际类型0。现在，每 索 拍 当搜索引擎收到这个搜索关键词，搜索引擎根据报价组（b，，6）确定：（a）哪些 卖 的 客户获胜以及他们的广告呈现的顺序；（b）（互联网用户点击他们的广告时）每个客户 机 应该支付的钱数。前者称为配置规则，后者称为支付规则。赞助搜索拍卖可以视为一个 制 间接机制μ=（（B;）i∈N，g（·）），其中B;CR+是广告客户i的可能报价集，g（·）是 设 计 配置与支付规则。注意，如果我们假设对于每个客户i，报价集B与类型集：相同， 那么间接机制M=（（B）∈N，g（·））变成了直接机制=（（O）i∈N，f（·）），其中 f（·）变成了配置与支付规则。在本章余下的内容中，我们假设B：=O，Vi=1，， n。因此，根据这个假设，我们可以将赞助搜索拍卖视为一个直接显示机制。 我们将典型的赞助搜索机制设计问题的构成成分列举如下。 口结果集X 赞助搜索拍卖中的一个结果就是一个向量r=（y，p:)iN,jEM，其中y是广告客户 i被分配到位置j的概率，p：是广告客户i向搜索引擎支付的每次点击的费用。于是， 可行结果集

X={(yPi)ieNjemy ∈[0,1] Vi∈N,Vj∈M;y≤1 j∈M, i=1 注意，随机结果也包含在上面的结果集中。这意味着随机机制也是机制空间的一 部分。 口广告客户的效用函数U（·） 给定x=（y，pi）iENjEM，广告客户i的效用函数为 u(x,0;)=（∑yai）(0;-pi) j=1 口社会选择函数f（·）（配置与支付规则） 这种情形的配置与支付规则的一般结构为 f(b)=(y(b)，p:(b))i∈N,j∈M 其中6=（b，，bn）是广告客户的一个报价向量。函数y（·）构成了配置规则，函 数p：（·）构成了支付规则。 口线性环境 博奔论与机制设计 稍微修改一下配置规则、支付规则以及效用函数的定义，我们可以证明赞助搜索拍 卖事实上是线性环境下的直接显示机制（参见19.7节）。为了将潜在环境转化为线性环 境，我们将配置与支付规则重新定义如下： f(b)=(y(b),t;(b))iEN,jEM 其中y(b)=(y（b))i∈N,j∈M,t;(b）=（≥²（b)a）p:(b)。t;(b）这个量可以视为对于 搜索引擎收到的每个关键词搜索，当广告客户的报价向量为b=（b，，6）时，广告 客户预期向搜索引擎支付的费用。 现在，我们可以将效用函数改写为下列形式： u;(f（b),0;)=θ;u;(y(b))-t;(b) 其中;((b)）=（≥（b)α）。;(y（b)）这个量可以视为当搜索引擎收到搜索关键 词且广告客户的报价向量为6=（b1，“，6）时，广告客户i的广告被互联网用户点击 的概率。现在，容易验证这里涉及的环境是线性的。 对于上面的模型，我们将用赞助搜索拍卖的三种基本机制进行说明： ·广义第一价格（generalizedfirstprice，GFP）机制； ●广义第二价格（GSP）机制； ●维克瑞-克拉克-格罗夫斯（VCG）机制。 对于上面的每种机制，我们都将描述它的配置规则y（·）与支付规则p（·）。

22.3广义第一价格（GFP）机制 在广义第一价格（GFP）机制下，配置规则与支付规则如下。3] 口GFP：配置规则 在这种机制下，m个广告位置根据广告客户们的报价高低，按降序配置给他们。令 b表示（b，…，b）中第k大（高）的元素。类似地，令（b-）（表示（b，…， bi-1，bi+1，，bn）中第k大的元素。根据这些定义，我们可以说如果b=（b，，b） 是n个客户的一个报价组，那么位置1分配给报价为6的客户。类似地，位置2分配给 报价为6的客户，以此类推。也就是说，对于所有证N和所有jM， 1:若b;=6) yi(b)= (22.2) 10：其他情形 如果两个广告客户有相同的报价，可用适当规则确定谁获胜。 口GFP：支付规则 每当互联网用户点击赞助链接时，广告客户支付的钱数等于他的报价。也就是说， 如果b=（b，，6）是广告客户们的一个报价组，那么对于所有i∈N， 第 2章 lb:：若客户i的广告被呈现 p;(b)= (22.3) 10：其他情形 赞助搜索拍卖的机制设计 22.4广义第二价格（GSP）机制 使用这种拍卖机制的主要动因源于广义第一价格（GFP）机制的不稳定性。特别 地，Edelman，Ostrovsky，andSchwarz3]已证明，在广义第一价格机制下，如实报价 不是广告客户的均衡报价策略，这个事实导致了系统不稳定，这又导致了广告客户无效 率的投资。广义第一价格机制也导致价格容易变化，这又使得配置无效率。 口GSP：配置规则 GSP：配置规则1 这种规则与广义第一价格（GFP）机制中的配置规则相同，也就是说，广告位置按 照客户们的报价高低以降序分配给他们。 GSP：配置规则2 在这种规则下，位置1的配置规则为：若客户i证N的αab：比其他客户的大（即若 客户i的αab：最大），则位置1分配给他。如果出现了平局，则用适当规则确定谁获胜。 现在，客户集N已不含客户i（因为他已拿到了位置1）；搜索引擎要在剩下的客户中选

择α2b;（其中j∈N{i)）最大的客户，位置2分配给这个客户。其他位置的分配方法 类似。 GSP：配置规则3 在这种规则下，对于每个客户，需要估算他的广告的点击率（click-through-rate， CTR）。点击率是指广告被点击的次数除以广告被呈现的次数。例如，对于某个特定关 键词搜索，如果结果页面上的广告（链接）被看了100次，但只有1次点击，那么点击 率为1%。现在，搜索引擎根据客户的排序分（ranking scores）以降序形式排列客户。其 中客户的排序分是指他的报价乘以估计的点击率。在本章余下的内容中，我们假设点击概 率仅取决于广告位置，与广告客户身份无关。也就是说，αj=αj=…=α=aj，Vj∈M。 我们还假设GSP机制中的配置规则与配置规则2相同，也与配置规则1相同，原因在 于上面指出的广告客户身份无关性假设。 口GSP：支付规则 在这种拍卖机制中，每当互联网用户点击赞助链接时，广告客户支付给搜索引擎的 钱数等于排位仅次于他的客户的报价再加上一个最小增量（minimumincrement）。比 如，假设对于广告位置1，客户10的报价最高，客户1的报价仅次之，那么客户10得 到位置1，客户10为此支付的钱数等于客户1的报价加上一个既定最小增量，比如多少 元钱。对于位置最低的广告位，获胜客户支付的钱数等于落败客户最高报价加上最小增 量；如果没有这样的报价，那么获胜客户支付的钱数为零。如果6=（b，"，6）是n 博奔论与机制设计 个客户的一组报价，那么根据我们前面关于GSP机制配置规则的假设可知，客户i支付 的每次点击价格为 (6(i+1)y(b):若m<n或n≤m但b;≠ 6(m) pi(b)= j=1 ：其他情形 其中6+1是第j十1高的报价，这也是广告被分配到位置为j十1的客户的报价。我们 忽略了最小增量，因为所有未来分析和结果对它都不敏感。 22.5维克瑞-克拉克一格罗夫斯（VCG）机制 表面上，GSP机制似乎是用于拍卖一件不可分割的商品的维克瑞机制的一种推 广。然而，正如Edelman，Ostrovsky，and Schwarz3]已经证明的，GSP机制不是将 维克瑞拍卖推广到拍卖物为一组排序商品的情形，本章后面部分也会说明这一点。在 本节，我们的任务是发展赞助搜索拍卖的克拉克机制。按照惯例，我们将其称为 VCG机制。 口VCG：配置规则 根据定义，VCG机制有配置效率。因此，在赞助搜索拍卖情形下，VCG机制中的

配置规则y*（·）为 y*（·)=argmax b;u;(y（b))=argmax (bai）y（b) (22.4) i=1 （） i=1j=] 在上一节，我们已经看到贪婪配置规则是式（22.4）的一个解。另外，在点击概率与客 户身份无关假设下，配置y*（·）按照降序的客户报价分配广告位置。也就是说，如果 b=（b，，b）是n个客户的一组报价，那么y*（·）必定满足下列条件： 1:若b;=6) y（b)= (22.5) 0：其他情形 根据以上观察，我们给出下面关于广义第一价格（GFP）与广义第二价格（GSP） 机制的有趣结论。 命题22.1如果点击概率仅取决于广告位置而与广告客户的身份无关，那么 （1）GFP机制有配置效率。 （2）如果GSP机制使用配置规则2（这与配置规则3相同），那么GSP有配置 效率。 （3）VCG机制的配置规则式（22.5）有配置效率。而且，这个配置规则正好与 GFP配置规则以及GSP的配置规则3相同。 VCG：支付规则 根据VCG机制的定义，当广告客户的报价组为b=（b，，b）时，客户i的期 望支付t：（b）必须按照下列克拉克支付规则计算： t;(b)=[∑b;u;(y(b）)]-[∑b;u;(y(b）)] 赞助搜索拍卖的机制设计 (22.6) 其中y：（·）是一个有效率的配置，它将不同广告位置分配给客户i之外的其他客户 （即客户i不出现时的有效率的配置）。将式（22.5）中的y*（·）代人式（22.6）并且 使用v;（y*（b)）=y（b)α;这个事实，我们可将式（22.6）写为下列形式： j=i 情形1（m<n） [-u![:(9)(1+5²+(+59g) t(b）=a;（b)= αmb(m+1) ：若j=m (22.7) ：若m<j<n 其中 ·t（b）是对于搜索引擎收到的每个搜索关键词，当客户报价组为b=（b，“，6） 时，广告被放在位置的客户的期望支付。 ·p（b）是对于互联网用户的每次点击，当客户报价组为b=（b，“，b）时， 广告被放在位置的客户的支付。 ;=αj-αj+1。 ·6的意思与以前相同，即（b，，b）中第j大的元素。

情形2（n≤m） [-u>!>[(9)(1+5²+(1+)9 t）(b）=ajp（b)= (22.8) [o ：若j=n 展开式（22.7）和式（22.8），可得到下列支付表达式： 情形1（m<n） (1+)9+（+9 p(b)=(b)={ k= α (22.9) αj 6(m+1) ：若j=m 1o ：若m<j≤n 情形2（n≤m） βb（k+1）：若1≤j≤n-1 (22.10) αj lo ：若j=n 因此，我们可以说式（22.5）描述了VCG配置规则，而式（22.9）与式（22.10）描述 了VCG机制的支付规则。 22.6最优（OPT）机制 在本节，我们的目的是计算能产生最优搜索拍卖的最优机制的配置与支付规则 f（·）。这要求我们将迈尔森最优拍卖扩展到赞助搜索拍卖情形。做此事时，我们沿着 与Myerson[4]相似的思想。回忆一下，我们将赞助搜索拍卖形式化为线性环境下的直 接显示机制の=（（O）∈N，f（·）），其中广告客户i的效用函数为 u;(f(b),θ)=(∑y(b)a;)(0;-p;(b)) =v;(y(b))(0;-p;(b)) =0;u;(y(b）)+t;(b) 其中 v;(y（b))= y;（b)a是广告客户i的评价函数，这可以解释为当搜索引擎收到 j=1 搜索关键词并且客户的报价组为6时，客户i的广告被互联网用户点击的概率。 ●t（b)=u:（y（b)）p：（b）可以解释为当搜索引擎收到搜索关键词并且客户的报价组 为6时，客户i的期望支付。 口OPT：配置规则 我们首先定义 ·t（b）=Ea[t（b;，θ-）]是当客户i报价b;且所有客户j≠i报告自己的真实类型

时，客户i的期望支付。 ●o（b:）=Ea[o（y（b;，0-:））]是当客户i报价b;且所有客户j≠i报告自已的真实 类型时，客户i的广告被互联网用户点击的概率。 ·U；（0）=0：（0:）一t（0）是当所有客户j≠i报告自己的真实类型，客户i也报告 自己的真实类型0时，客户i得到的期望效用。 现在，赞助搜索拍卖最优机制设计问题可以视为下列最优化问题：选择函数 y（·）与U（·），使得 max （0（0）-U（0））（0）dθ （y（）U;(（））ENjEMi=1 s.t. （i);（·）非递减，i∈N。 (i)y;(①) ∈ [0,1],y;(①)≤1,x(b)≤1, Vi ∈ N,Vj ∈ M,vθ ∈ 。 j=1 =1 （ii)U；（0）=U（0）+ (s)ds,iEN,0∈ (iv)U(0)≥0,i∈N,0:∈。 (22.11) 在上面的表达式中，目标函数是搜索引擎从所有广告客户身上得到的总期望支付。 注意，约束条件（iv）是客户们的事中个体理性约束，而约束条件（i）是可行性约束。 约束条件（i）和（ii）是配置和支付规则f（·）=（yg（·），t：（·））ieN,jEM成为贝叶斯 激励相容的必要充分条件（迈尔森特征定理，参见19.7节）。这些约束条件取自文献 [4]，我们已在第21章做了介绍。 赞助搜索拍卖的机制设计 在这里，我们可以做出一个重要观察。注意，在上面的最优化问题中，我们用实际 类型0：替换了报价b：。这是因为我们对配置和支付规则施加了贝叶斯激励相容约束，因 此，每个客户都将如实报价。因此，尽管我们考察的是OPT机制，但对于任何正N， 我们可以放心地互换0：与b：。 注意，如果约束条件（ii）得以满足，那么（iv）也将得以满足当且仅当U：（0：）≥ 0，ViEN。因此，我们可以将约束条件（iv）替换为 （iv’)U;(0)≥O,ViEN。 接下来，将约束条件（ii）代人目标函数，可得 (;(0,)0;—U;(@;)-;(s)ds）):;(0;)>da0; 对上式进行分部积分，可知卖者最优化问题可以视为在约束条件（i）、（i）和（iv） 下，选择函数y（·）以及效用值U（0），，U（0n），使得 。[;(y(0,0-);(0)][1(0)]a…o0 U;(0) 最大。其中：

显然，前面的最大化问题的解必定满足U（0）=0，Vi=1，，n。因此，搜索引 擎的问题简化为下列问题：在约束条件（i）和（i）下，选择函数y（·）使得 [≥(y(0,0-))J:(0)][II(0)].··d i=】 最大。 我们暂时忽略约束条件（i)。考察上面的表达式，可知，y（·）是这个放松约束 后问题的一个解当且仅当对于所有i=1，，n，我们有 (0Vj=1,2,",m：若J（0）<0 ]1Vj=1,2,,m<n:若J；（0:）=J） y（0）= (22.12) 1Vj=1,2,.·,n<m：若J;（0;)=J） (o ：其他情形 其中J是J（0）中第高的评价。 换句话说，如果我们忽略约束条件（i)，那么y（·）是这个放松约束后问题的一 个解当且仅当：任何伴随负的J：（0）的客户都得不到广告位置，而且其他客户的广告 排序与他们的J：（0）值的排序相同。也就是说，广告位置1分配给伴随最大非负J：（0） 的客户，位置2分配给伴随第二高的非负J：（0）的客户，以此类推。 现在，回顾v（·）的定义，容易写出下列表达式： ;（0）=E[u;（y（0，θ-))] (22.13) =E[> yi（00-i）aj] (22.14) =1 现在，如果我们假设J（·）关于0：为非递减的，那么容易看出式（22.12）给出的解 y（·）关于0：也为非递减的，这意味着（·）关于0为非递减的（考察式（22.14） 即可知道这一点）。因此，在J：（·）为非递减的这个假设下，这个放松约束后问题的解 事实上满足约束条件（i)。假设J：（·）为非递减的，式（22.12）给出的解似乎是赞助 搜索拍卖最优机制设计问题的解。注意，在式（22.12）中，我们将配置规则J：（·）写 为一个关于客户实际类型组9的函数，而不是写为关于报价组6的函数。这是因为在 OPT机制中，每个客户如实报价，因此我们有b=0，Vi=1，，n。 J（·）关于0为非递减的这个条件容易实现，事实上，很多常见分布函数，例如 均匀分布和指数分布，都能满足这个条件。在本章余下的内容中，我们都假设对于每个 客户i，J（·）关于0：都为非递减的。 注意，在上面的配置规则中，用于刻画客户有资格展现他的广告的条件J（·）>0， 在下列意义上，可以方便地用保留价格形式表达。对于每个客户i，我们首先计算使得 J（0:）=O的θ：值。我们将这个值称为客户i的保留价格（reserveprice）。现在，配置 规则表明，我们可以去掉报价小于自己保留价格的那些客户。对于剩下的客户，我们按 照他们的J：（0）值降序排列，然后分配相应的广告位置。另外，如果客户是对称的，

那么所有客户的保留价格都相同，而且如果J（·）关于0：非递减，那么这里的配置规 则将与广义第一价格（GFP）机制的配置规则相同。这种对配置规则的解释类似于文献 [5]对相似情形的解释。这个观察让我们得到了下列命题。 命题22.2如果广告客户有不同的分布函数①（·），那么J：（b;）值为第k大的广 告客户未必是报价为第k大的广告客户。因此，OPT机制未必有配置效率，从而未必 有事后效率。 命题22.3如果客户是对称的，即如果 =··==， ·（·)=··=n（·)=（·)， 而且如果对于每个客户i，我们都有J（·）>0以及J（·）为非递减的，那么： ·J（·)=·…·=Jn（·)=J（·）。 ·客户在降序序列J（b），，J（b）中的位置，与他在降序序列b，…，b中 的位置正好相同。 ·对于给定的报价组6，OPT机制得到的配置与GFP、GSP、VCG机制得到的配 置相同。 ·OPT机制有配置效率。 口OPT：支付规则 现在我们计算OPT的支付规则。再一次地，按照与迈尔森类似的思维，最优期望 支付规则t（·）必须满足ViEN， 第 t(0）=E[t(0，0)]=00;（0)-U;（0）=00：（0:）- （s）ds (22.15) 章 赞助 考察上式以及式（22.16）可知，如果支付规则t（·）满足式（22.16），那么它也满足 式（22.15)。 搜 索 拍 t;（0，0-）=0u;（y（0，0-）)- v(y（s,0-i）)dsθ∈ (22.16) 卖的 上式可以改写成更符合直觉的形式，我们现在做此事。首先，对于任何向量0-，我们 机 制 定义下列各个量。 设计 情形1（m<n）： zn（0-）=inf{0；1J（0）>0且J（0）≥J} 2i2（0-)=inf{01J（0)>0且J>J:（0)≥J} ：=: 2m（0-i)=inf{0:1J;(0;）>0且Jm-1>J:(0:)≥J(=m} 情形2（n<m）： z（0-)=inf{0|J:（0）>0且J（0）≥J} z2（0-;)=inf{01J（0)>0且J>J:（0)>J} =： zn（0-)=inf{0:1J;（0）>0且Jn-1>J:（0;)}

在上面这些定义中，J是下列n一1个值中第k大的值： J(θ）,··.,Ji-1(0i-1),Ji+1(0i+1）,···,Jn(0n) z（0-）是当其他客户的报价为0-时，客户i针对广告位置k的所有获胜报价的下确 界。根据上面这些定义，我们有： 情形1（m<n）： [α1：若0≥xn（0-;) α2：若z（0-:)>0:≥xi2（0-;) v;(y（0，0-;))=: αm：若im-1)(0-;)>0:≥2m（0-i) 0：若xm（0-）>0 情形2（n≤m）： [α1:若0≥za（0-:) α2:若x1(0-;)>0i≥zi2（0-;) v;(y（0,0-:))= （αn：若xi（n-1）（0-:）>0 这样我们就得到了 u（y（s，0-））ds的下列表达式。在这些式子中，r是客户i的广告 所在的位置。 博奔论与机制设计 情形1（m<n）： 0; U(y（s,0-i))ds 0; αr（0:-x（0-:））+ [u>[(-0)-(-0)(1-z) j=r+1 αm（0;—xin（0-i）) ：若r=m [o ：其他情形 情形2（n≤m）： 0: （y（s,0-））ds 0; a（0:-x(θ）)+ a;（ziG-1）（0-）-zg（0-:)）:若1≤r≤n—1 j=r+1 an（0;—xn（0-i）) ：若r=n 将上面的 u;（y（s，0-））ds的值代人式（22.16），可得 情形1（m<n）： αr

αr (22.17) (0)x ：若r=m ：其他情形 情形2（n≤m）： 1t;(0：,0-i) p;(0，0-;）= ar αr αrj=r (22.18) (0)“x ：若r=n [o ：其他情形 上面的这些关系表明，客户i仅在他的广告被点击时才必须支付，他的支付等于 p:（θ)。注意，在上面的这些关系中，我们将支付规则p（·）表达为一个关于客户实际 类型组0的函数，而不是关于报价组6的函数。这是因为在OPT机制中，每个客户如 实报告自已的类型，因此我们有b=0，Vi=1，，n。 因此，我们可以说式（22.12）描述了OPT机制的配置规则，式（22.17）和式 （22.18）描述了OPT机制的支付规则。 在下面，我们讨论OPT机制的一种重要的特殊情形，即当广告客户为对称的情形。 口OPT机制与对称客户 令广告客户在下列意义上对称： 赞助搜索拍卖的机制设计 ·O=·=O=O=[L，U]CR； （·)=···=（·)=（·)。 另外，我们假设 ·J（·）在区间[L，U]上为非递减的； ·J(x)>O，xE[L，U]。 注意，如果J（L)>O，那么我们必定有L>0。 命题22.3表明如果广告客户是对称的，那么OPT机制的配置规则与GFP、GSP、 VCG的配置规则相同。至于支付规则，容易验证如果当报价组为（0，0-）时客户i 得到了广告位置r，那么我们应该有 情形1（m<n）： {θ）：若1≤j≤r-1 zg（0-i）= (22.19) i+1：若r≤j<m 情形2（n≤m）： {）：若1≤j≤r-1 [->(1+=(-0) (22.20) L：若j=n

如果将式（22.19）代人式（22.17），将式（22.20）代人式（22.18），那么我们得到了 客户为对称情形下的OPT机制的支付规则： 情形1（m<n）： ar αmg(m+1）+1 Cβ;0+1:若1≤r≤m-1 αrj= (22.21) θ(m+1) ：若r=m ：其他情形 情形2（n≤m）： t;(0,0-i) p;(0，0）= αr L+ αr ar (22.22) L ：若r=n lo ：其他情形 将上面的这两个式子与VCG机制的支付规则[式（22.9）和式（22.10）]进行比较， 可得到下列命题： 命题22.4如果广告客户在下列意义上对称： ·=··===[L，U]； （·)=··=（·)=Φ（·)。 另外，假设对于每个客户i，在区间[L，U]上我们有J（·）>0而且J（·）为 非递减的，那么： ·情形1的支付规则与VCG机制相应的支付规则相同； ·情形2的支付规则与VCG机制相应的支付规则不同，但仅相差一个常数L。 注意，L不可能为零，因为我们假设J（L)>0。 22.7小结与参考文献 本章旨在将机制设计运用到当前流行的赞助搜索拍卖问题。这个讨论让我们思考如 何在现实世界中使用机制设计。本章讨论的主要议题有： ·我们将赞助搜索拍卖问题表达为拟线性环境下的机制设计问题。事实上，这个拟 线性环境是线性环境。 ·在上面的机制设计架构上，我们推导出了广义第一价格（GFP）机制的配置规则 和支付规则。 ·接下来，我们推导出了广义第二价格（GSP）机制的配置规则和支付规则。搜索引 擎通常使用GSP机制或它的变种。我们还推导出了克拉克机制的配置规则和支付规则。

·我们提出了一种新的机制，即OPT；它将迈尔森拍卖推广到赞助搜索拍卖情形。 OPT使用赞助搜索拍卖的内在结构来推广迈尔森定义的实际评价函数。 赞助搜索拍卖的机制设计问题是近年来的主要研究议题之一。ACM电子商务年会 （现在改名为ACM经济学与计算会议）是这一领域最前沿的信息来源。 口参考文献 [1]Dinesh Garg and Y.Narahari.“An optimal mechanism for sponsored search auctions and comparison with other mechanisms”.In:IEEE Transactions on Automa- tionScienceandEngineering6(4)(2009)，pp.641-657. [2]Y.Narahari,Dinesh Garg,Ramasuri Narayanam,and Hastagiri Prakash. GameTheoreticProblemsinNetrworkEconomicsandMechanismDesignSolutions. Springer,London,2009. [3]B.Edelman,M.Ostrovsky,and M.Schwarz.“Internet advertising and the generalized second price auction:Selling billions of dollars worth of keywords".In:A- mericanEconomicReview 97（1)(2007)，pp.242-259. [4]Roger B.Myerson.“Optimal auction design”.In:Mathematicsof Operations Research6(1)(1981)，pp.58-73. [5]JuanFeng.“Optimal mechanismforselling a set of commonly ranked objects”. In:MarketingScience 27（3)(2008)，pp.501-512. 第 22.8习题 章 赞助换 （1）某赞助搜索拍卖有3个广告位置。有5个竞标人{1，2，3，4，5），他们的评 搜 索拍卖的 价分别为u=20，U2=15，U=12，04=10，U5=6。对于这个问题，如果使用GSP、 VCG和OPT机制，这些机制的结果分别是什么？ （2）在上面的问题中，假设拍卖物不是3个广告位置，而是3件相同的商品。令智 机 能体1的需求为2单位，其他每个智能体的需求都是1单位。如果使用GSP和VCG， 制设计 这些机制的结果分别是什么？ （3）在某赞助搜索拍卖中，有3个广告位置。给定任何一个竞标人，他对这三个位 置的评价相同。另外，假设这三个广告位的点击概率相同。假设有5个竞标人（1，2， 3，4，5}，他们的评价分别为v=15，v2=14，U3=12，U4=10，v5=8。若使用GSP、 VCG以及OPT，这些机制的结果分别是什么？