单物品拍卖
单物品拍卖(single-item auctions) 这个话题是我们开始讨论机制设计――制定规则的科学――最明智的选择。回顾我们在这门课程中首要的目标。
课程目标一：理解如何在有策略性参与者的情况下，设计具有好的性能保证的系统。
考虑有一个卖家拥有一个商品，比如说一个稍微过时的智能手机。就例子而言，这是一个典型的eBay拍卖的设定。有一定数量n个（策略性的！）投标人潜在地有兴趣购买这个物品。
我们想要在各种拍卖形式下分析投标人的行为。为了实现这个目标，我们需要对投标人想要什么进行建模。第一个假设是每一个投标人拥有价值(valuation)――为了买到这个物品愿意付出的最大代价。因此在售价最多为的情况下，投标人希望用尽可能低的价格买到这个物品。另一个重要的假设是这个价值是私人的(private)，意味着卖家和其他投标人不知道这个价值。
我们建立的投标人的效用模型被称作拟线性的效用模型(quasilinear utility model)。如果一个投标人输掉了一场拍卖，他的效用是0。如果投标人赢的时候付出了代价，那么效用是。这可能是最简单自然的效用模型，也是我们在这门课程中关注的模型1。
密封投标拍卖
目前我们会关注一种特殊的简单类型的拍卖形式：密封投标拍卖(sealed-bid auctions)。它的设定如下：
(1) 每个投标人出价给拍卖人——如果你喜欢的话，可以想象出价放在密封的信封里。
(2) 拍卖人决定谁得到商品（如果有人得到的话）。
(3) 拍卖人决定售价。
有一种明显的实施步骤(2)的方法——将商品给出价最高的投标人。今天，这会是我们研究的唯一的选择规则2。
有很多实施步骤(3)的合理方法并且这些实施方法会显著地影响投标人的行为。例如，假设我们想要行善，不需要赢了的投标人付出任何代价。这个想法会严重地事与愿违，而且这个拍卖就会演变为“谁能说出最大的数字”的游戏。
首价拍卖
一种更合理的选择是让赢了的投标人支付他的报价。这被称作首价拍卖(first-price auction)，而且这样的拍卖在实践中很常见。
首价拍卖很难分析。首先，作为一个参与者，很难搞清应该如何出价。其次，作为一个卖家或拍卖设计者，很难预测会发生什么。我们会在问题集1和后面的高级材料中阐述首价拍卖的理论。现在，为了把论点讲清楚，想象你在参与如下的实验。有一个物品正在通过首价拍卖的形式出售。你心中对它的价值（以美元为单位）是你出生月份和天数之和。因此，这个价值落在2（1月1日）和43（12月31日）之间。假设刚好有另一个投标人（从世界上随机选出）的价值也是通过同样的方式决定。你会出价多少来使得你的（拟线性的）效用最大？如果你知道在这场拍卖中有两个其他投标人，而不是一个，你的答案会改变吗？
次价拍卖
现在让我们将注意力放到另一种在实践中也经常使用的更容易分析的拍卖形式。为了引出这种拍卖，回想一下当你在一个eBay拍卖中获胜后会发生什么？如果你出价100美元并且赢了，你是否一定要付100美元呢？不一定——eBay使用一种“代理投标人”机制代表你增加你的出价，直到到达你设定的最大出价或者你成为最高出价者（取决于哪种情况先到达）。举例来说，如果其他人中最高的出价只是90美元，那么你只需要付90美元（加上一点点增量），而不是你的最大出价100美元。结果是：如果你赢了一个eBay拍卖，出售价格等于其他人中的最高出价（总体而言的第二高的出价），加上一个小的增量。
次价拍卖(second-price auction)或Vickrey拍卖是一种最高的出价者获胜并支付第二高的报价的密封投标拍卖。
声明4.1 在次价拍卖中，每一个投标人都有一个占优策略(dominant strategy)：选择出价等于私人价值。也就是说，不管其他投标人怎么做，这个策略最大化投标人的效用。
这个声明暗示了次价拍卖是非常容易参与的——为了搞清楚你应该怎么出价，你完全不需要分析其他投标人（有多少投标人，他们的价值是多少，他们是否会真实出价，等等）。注意到这跟首价拍卖完全不一样了。在首价拍卖中你绝对不应该按你的价值出价（因为这保证了你的效用为0），而理想的压低报价的量取决于其他局中人的报价。
声明4.1的证明：固定一个任意的局中人，他的价值以及其他局中人的报价。（这里代表了所有报价组成的向量删去了第个元素后剩下的部分。这是一种靠不住的符号表示，但你需要习惯这种表示。）我们需要表明当时，投标人的效用最大。（回顾下是的不变的价值，然而出价可以任意选择。）
令表示其他投标人中最高的出价。次价拍卖特殊的地方在于，尽管可以选择的出价是无限多的，只有几个不同的结果可能出现。如果，那么输掉并且效用为0。如果，那么获胜并支付，从而效用为。这里我们假设当出现平局时，平局的打破结果总是对投标人有利。你应该检查下，无论平局是如何打破的，这个声明总是成立的。
我们现在考虑两种情况。首先，如果，那么投标人能够得到的最高效用是，并且通过真实报价来得到这个效用（虽然输掉了）。其次，如果，那么投标人能够得到的最高效用为，并且也是通过真实报价来实现（并且获胜）。#
第二个重要性质表明一个真实报价(truthtelling)的投标人永远都不会后悔参与一个次价拍卖。
声明4.2. 在一个次价拍卖中，每一个真实报价的投标人都保证会得到非负的效用。
证明： 失败者的效用为0。如果投标人获胜，他的效用为，其中为第二高的出价。既然是胜者（也就是最高出价者），并且出价为他的真实价值，，从而有。 #
练习题要求你进一步探索Vickrey拍卖的性质和变形。例如，真实报价是Vickrey拍卖中唯一的占优策略。
令人惊叹的拍卖
后退一步，我们可以声明如下的定理：
定理5.1. (Vickrey[1]) Vickrey拍卖是令人惊叹的(awesome)。这是指，它拥有如下三个完全不同而又理想的性质：
(1) 【强激励保证】它是占优策略激励相容的(dominant-strategy incentive-compatible, DSIC)，即声明4.1和4.2成立。
(2) 【强性能保证】如果投标人真实报价，那么这个拍卖会最大化社会剩余(social surplus) 其中如果赢的话为1，否则为0，并且需要满足明显的可行性约束（即，这里只有一个物品）。注意到销售价格不是剩余的一部分。原因是我们将拍卖人视作一个局中人，他的效用是赚得的利润；因此会抵消拍卖获胜者因为付钱而失去的效用。我们会在之后的课程中讨论最大化拍卖者利润的拍卖。
(3) 【计算高效】拍卖可以在多项式时间（其实是线性）时间内实施。
所有的这些性质都是重要的。从投标人的角度讲，DSIC性质保证了真实报价是占优策略并且永远不会导致负的效用，从而使得选择出价变得格外容易。从卖家或拍卖设计者的角度讲，DSIC性质使得分析拍卖的结果容易得多。注意到任何对拍卖结果的预测都必须是在对投标人如何行动的假设上进行预测。在DSIC拍卖中，只需要假设一个有明显占优策略的投标人会按照这个策略投标——行为假设并不会比这个弱很多。
如果能得到DSIC性质的话会很好，但我们还想要更多。例如一种将物品免费地赠送给一个随机的投标人的拍卖满足DSIC，但是这样无法辨识哪一个投标人实际上想要这个物品。剩余最大化的性质表明了一个相当惊人的结果：及时拍卖人事先不知道投标人的价值，拍卖也能够成功地找出拥有最高价值的投标人。（这里假设了真实报价。考虑到DSIC性质，这是一个合理的假设。）因此，Vickrey拍卖解决了剩余最大化的优化问题，就好像事先已经知道了这些价值一样。
第三个性质的重要性对于计算机科学家而言也是不言而喻的。为了有潜在的利用价值，一个拍卖应该在一个合理的时间内进行——对于某些应用而言甚至是实时的。拥有超越多项式时间的拍卖仅仅会在相当小的实例中有用。
接下来的几讲内容会努力地在超越单物品拍卖的应用中去寻找定理5.1中定义的令人惊叹的拍卖。有两个方向是有很好的研究动机的，一是更加复杂的分配问题，正如在竞价搜索中和组合拍卖中无可避免地出现的那些问题；二是最大化卖家利润而不是社会剩余。
案例分析：竞价搜索拍卖
背景
一个网络搜索页一般包括搜索结果的列表——由一些底层的算法，例如PageRank，算出的跟你的检索相关的网页——以及由广告主付费的链接的列表。（为了回顾这一点，现在可以去进行一次网络搜索，最好用一些有价值的关键词，例如“抵押”或“石棉”。）每一次你在搜索引擎中输入一个搜索查询，一个实时的拍卖会决定哪些广告主的链接会被展示，以什么样的顺序展示，以及它们如何被收费。现在无论说竞价搜索拍卖对于互联网经济有多重要都不过分。这里有一个令人瞠目结舌的统计：在2006年，竞价拍卖贡献了谷歌公司大约98%的收入[2]。尽管现在在线广告可以通过很多不同的方式出售，竞价搜索拍卖每年仍然贡献着数百亿美元的收入。
竞价搜索拍卖的基本模型
我们讨论一个竞价搜索拍卖的简单但有用而有影响的模型，它是由Edelman等[2]和Varian[3]独立提出的。待出售的商品是一个搜索结果页上个广告位。投标人是那些对被搜索的关键词进行投标的广告主。举例而言，沃尔沃和斯巴鲁可能会去竞拍关键词“旅行车”，而尼康和佳能可能会去竞拍关键词“相机”。这样的拍卖在两方面比单物品拍卖要更加复杂。首先，一般而言有多个商品待出售（即）。其次，这些商品并不等同——搜索页上排位更靠上的广告位会比下面的广告位更有价值，因为人们一般从上到下浏览网页。
我们通过点击率(click-through-rates, CTRs)来量化不同广告位间的差别。广告位的点击率代表了用户点击这个广告位的概率。将广告位从上到下排序，我们做出如下的合理假设。为了使问题简单，我们也会做出如下的不合理假设：一个广告位的点击率与它上面展示的内容无关。练习题会展示如何将后面的结果推广到一个更加一般和现实的模型，其中每一个广告主都有一个“质量分”（越高越好），从而广告主在广告位处的CTR为乘积。
我们假设广告主不关心广告给人带来的印象本身（即被展示在一个页面上），而是对于它的链接的每一次点击都有一个私人价值。因此，广告位带给广告主的价值是。
我们想要什么？
存在一个令人惊叹的竞价搜索拍卖吗？我们想要的性质是：
(1) 占优策略激励相容。也就是说，真实报价应该是一个占优策略，并且永远不会导致负的效用。
(2) 社会剩余最大化。也就是说，分配广告位给投标人的结果应该最大化，其中现在代表了被分配到的广告位的CTR（如果没有被分配到广告位的话为0）。每个广告位只能被分配给一个投标人，而且每个投标人只能得到一个广告位。
(3) 多项式运行时间。记住每天都有不计其数的这样的拍卖在运行。
我们的设计途径
机制设计的困难之处在于我们必须同时设计下面两件事情：谁获得什么的选择和谁付出什么的选择。即使在单物品拍卖中，对前者做出“正确”的选择（即将商品给出价最高者）也是不够的，如果支付规则不合适的话，策略性参与者会玩弄系统。
令人欣慰的是，在包括竞价搜索拍卖在内的许多应用中，我们能够一步一步地来解决这个涉及到两个方面的设计问题：
步骤1： 没有理由地假设投标人真实报价。那么我们应该如何分配广告位给投标人，使得上述性质(2)和(3)成立？
步骤2： 根据步骤1的结果，我们应该如何设计出售价格使得上述性质(1)成立？
如果我们成功地回答了上述两个问题，那么我们已经构造出了一个令人惊叹的拍卖。步骤2保证了DSIC性质，这意味着投标人会真实报价（同通常的假设一样，一个有着明显占优策略的投标人确实会遵从这个策略）。这意味着步骤1中的假设成立，因而拍卖的最终结果确实是剩余最大化的（而且可以在多项式时间内计算）。
我们通过实施竞价搜索拍卖的步骤1来结束这一讲。假设真实报价，我们应该如何分配广告位给投标者使得剩余最大化？作为一个练习，你应该能够表明贪心算法是最优的（而且运行时间接近线性）：对于，分配第高位的广告位给出价第高的投标人。
我们能够实施步骤2吗？有一种类似次价规则的价格方案能够使得对于每一个投标人而言，真实报价都是占优策略吗？下一讲我们会利用机制设计中一个强大的工具，Myerson引理来给出一个肯定的回答。
脚注：
1 更复杂的效用模型也被很好地提出和研究过了，例如对风险态度的刻画。
2 当我们在几讲之后研究利润最大化的时候，我们会看到为什么其他选择规则也很重要。
参考文献
[1] William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of finance, 16(1):8-37, 1961.
[2] Benjamin EDELMAN, Michael OSTROVSKY, and Michael SCHWARZ. Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords. The American economic review, 97(1):242-259, 2007.
[3] Hal R Varian. Position auctions. International Journal of Industrial Organization, 25(6):1163-1178, 2007.