【广告算法工程师入门 19】机制设计-GFP和GSP下的策略行为与均衡分析

本文主要是介绍【广告算法工程师入门 19】机制设计-GFP和GSP下的策略行为与均衡分析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

关键词拍卖基本假设

广告主的策略行为

广告位资源是有限的，广告主要通过博弈获得广告位。特别注意如果只有一个广告位的时候，广告主的策略行为与之前分析不完全信息静态博弈的单物品拍卖类似。但是对于搜索引擎来说，广告位可能存在多个，这时候广告主的策略行为将会发生较大变化。

在关键词拍卖中，广告主对于广告位的争夺可以看成是垄断地位的争夺，在重复博弈中，会引发价格战，在拍卖中价格不断上升，然后直到价格下降崩溃，然后新一轮的价格战，这种报价行为与经济学中的Edgeworth循环吻合。在GFP和GSP下，这种价格战是理性经济人的最优决策。

广告主的报复性报价

在GSP中，广告主存在一种『报复性』报价行为，低报价者可以在不降低自己效用的同时，降低竞争者的效用，这种行为十分常见，对于广告主而言，因为预算等限制，通过报复性报价可以使得竞争对手的单位成本增加，预算快速消耗退出竞争，得以垄断广告位。报复性报价其实也是为了自身的效用。

如果广告主均采用报复性报价，传统的纳什均衡是不稳定的。广告主总是提高报价，直到刚好处于上一位广告主报价的下方，增加上一位广告主的支付。而上一位广告主的最优反应不再是保持原来的报价，而是把报价调到小于下一位广告主报价，广告位发生置换，这样进行多轮的交替，达到另外一个均衡。

在关键词拍卖中纯策略均衡时，广告主采用报复性报价，广告位的分配仍然有效。如果只有两个采用报复性报价的广告主，则总存在一个纯策略纳什均衡，多于两人时可能存在也可能不存在均衡。

GSP机制与VCG机制

这里简要介绍GSP机制与VCG机制的情况（注意多个广告位，之前的结论是单物品拍卖）

也就是说VCG机制下和GSP机制下，广告主会采用不同的报价策略，VCG机制下广告主说真话达到均衡状态，而GSP机制下广告主可能不说真话，那么GSP机制是否存在均衡状态呢？从两个角度研究GSP机制下的均衡。

从完全信息静态博弈角度分析GSP机制的均衡

与第二价格密封拍卖类似的具有完全信息的静态博弈，因为关键词是动态重复博弈，广告主可以通过调整报价去学习推断其他广告主的真实估价，所以说具有完全信息的静态博弈。

局部无嫉妒均衡：广告主不能通过与其相邻的广告主交换位置来增加收益时达到的均衡。局部的概念体现在相邻。即使能达到这个均衡，也并不代表着广告主的报价是问题，一方面是动态博弈，另一方面广告主可能通过调整报价与非相邻的广告主进行置换增加收益。
全局无嫉妒均衡：任一广告主不能通过改变自己的位置增加收益，这一均衡对应着稳定匹配（稳定匹配理论是2012年的诺贝尔经济学奖），也就是说GSP机制是一种稳定匹配的实现。
关键词拍卖中的任意局部无嫉妒均衡结果都是一个全局无嫉妒均衡
关键词拍卖中的局部无嫉妒均衡和全局无嫉妒均衡等价。
在关键词拍卖中存在着某种报价向量（如VCG机制下的报价），形成局部无嫉妒均衡
搜索引擎在GSP机制的局部无嫉妒均衡状态下的收益不小于VCG机制的占优均衡获得的收益。这就是VCG机制难以实施的原因之一。

从不完全信息动态博弈角度分析GSP机制的均衡

前文通过完全信息博弈的思路分析GSP机制的均衡情况，但是这个均衡情况是广告主长期博弈后的均衡状态。机制设计者需要为广告主指定一种达到这种状态的均衡路径。

广义英式拍卖：把公开叫价变成价格指示器，从低到高显示，竞买人选择合适的价位。其分配规则和支付规则与GSP是一样的，也就是说GSP机制在动态情况下等价于广义英式拍卖，在这个过程中不完全信息动态博弈逐步演化到完全信息静态博弈。在这种机制下，存在唯一的完美贝叶斯均衡，这个均衡与VCG机制下的占优均衡是一致的，收益会小于GSP静态无嫉妒均衡时的收益。
在独立私人价值假设下，英式拍卖与第二价格密封拍卖是收益等价的，但是广义英式拍卖与广义第二价格密封拍卖收益不是等价的，因为广义英式拍卖是不完全信息动态博弈，不存在占优均衡策略，广告主的报价依赖其他广告主的报价，比较的对象却是GSP在达到完全信息博弈均衡时的收益状况。
在不完全信息动态博弈中，广义英式拍卖（或者GSP）机制下，广告主的估价和报价在区间内波动。