【广告算法工程师入门 20】机制设计-从GSP机制到VCG机制
【该文档已经整理到看云电子书：广告算法学习笔记】
机制设计
在前文【广告算法工程师入门 9】机制设计-博弈论基础中已经谈过了微观经济学与博弈论的区别，在微观经济学中市场机制是一个『看不见的手』，调整市场进入均衡状态。在博弈论中，机制设计者（委托人）设计规则，代理人参与规则，进行博弈，达到纳什均衡。可以看出机制设计是一只『可看见的手』，调整市场进入均衡状态。
微观经济学研究的完全竞争或者完全垄断市场是极端理想情况，而博弈论研究的市场进一步贴近现实市场，这也就是博弈论机制设计的吸引力所在。
机制设计本质来说就是设计分配函数和支付函数（奖惩函数），设计的目标是最大化社会效率和委托人的收益。
关键词拍卖的机制设计
关键词拍卖机制主要是为广告主购买的关键词分配广告位并确定相应非费用，涉及的内容包含：
- 定义每个广告主的效用收益函数（这个在实践中比较关键）
- 确定分配函数与支付函数
- 计算博弈的均衡状态
- 计算在均衡状态下搜索引擎的期望收益
前文主要分析了GFP，GSP和VCG机制下广告主的策略行为，在该行为下所能达到的均衡，以及在该均衡下广告主的支付和收益，搜索引擎的收益情况。这些结果是机制设计的基础。
GSP机制，克服了GFP的不稳定，在工业界得到广泛应用。GSP的不足之处如下：
- GSP机制不是一个说真话的机制
- 当点击率满足分离假设时，GSP机制存在纳什均衡，并且存在多个纳什均衡，增加了广告主的管理成本，给搜索引擎的收益带来很大的不确定性。
所以，搜索引擎作为机制的设计者，希望能够设计一种真实，激励兼容，有效的机制克服GSP机制的缺点，人们研究了以下几种机制：
VCG机制
在满足点击率分离假设的情况下，同一报价的GSP机制与VCG机制的分配结果相同，但GSP下的搜索引擎收益不小于使用VCG机制。这对于机制设计者——搜索引擎而言是不能忍的。
阶梯式拍卖
不需要满足点击率分离假设，Aggarwal,Goel,Motwani定义了阶梯式拍卖，分配规则与GSP机制相同，支付规则不同。该机制是一种说真话的机制。该机制遇到与VCG机制相同的情况，同一报价下搜索引擎的收益比GSP机制的收益少。但是在不同的支付规则驱使下，GSP机制和阶梯拍卖机制的报价可能不同，收益也难以比较大小，但是说真话的机制使得收益的可预测性更强。
对广告主在不同广告位之间获得的点击率进行分段计费，从而消除了广告主不按真实估价报价的动机。
另外还有带有保留价的双阶梯拍卖机制，不再讨论。
参考资料：
戎文晋 【关键词拍卖与理论实践】