大家好,欢迎来到IT知识分享网。
这章似乎开始进行数学抽象了
单参数环境 在单参数环境中,有个智能体,每个智能体
都对单个物品有非负的估值,此估值为私人信息,记作
。最后,有一个可行集
。
中的每个元素
都是
维向量
,其中
表示智能体
获得的物品数量。
(单参数环境为什么叫单参数环境呢,查了些资料,感觉比较贴合语境的说法如下: 一种简化的博弈环境,其中所有参与者的策略选择只依赖于一个关键参数或变量,如这里对物品的估值。到现在为止还是没感出本书侧重是算法还是博弈论TT,再次吐槽概念的引入毫无铺垫,越发像是本讲义了)
(维向量
是某种可能的分配方案,可行集
可理解为所有可能的分配方案的集合),下面是几个例子:
- 单物品拍卖 可行集
是满足
(总分配量不超过1)的0-1向量
所组成的集合,
- k物品拍卖 有
个相同物品进行拍卖,并且每个竞拍者最多获得其中一个。那么可行集
就是满足
(总分配量不超过
)的0-1向量
所组成的集合
- 关键字搜索拍卖 一个竞拍者最多获得一个广告位,并且一个广告位最多分配给一个竞拍者,如果竞拍者
得到了广告为
,那么
的
分量就等于其获得的广告位的点击率
。(我的第一直觉这种情况下,
应该是广告位的一个排列组合,不过显然用点击率来代表
的分量给未来分析计算会带来很大的方便)
- 公共项目决策 决定是否修建一个供所有人共享的公共项目,比如一座桥。其可以被建模为可行集
(建了就是给所有人分配了,不建就所有人都不分配)
二价拍卖需要完成以下步骤:
- 收集所有智能体的出价
,称为出价向量或出价组合
- 【分配规则】选择一个可行的分配
- 【支付规则】选择一个支付
直接显示机制(direct-revelation mechanism) 机制要求智能体直接地显露其私人估值,如二价拍卖;对应的,非直接显示机制,如迭代升价拍卖
如果收益函数是拟线性的(quasilinear),则智能体的收益函数如下:
(私人估值 * 分配个数 – 支付)
其中,支付规则应满足: (显然需要保证支付不为负,不太显然的是要保证真实报价的收益不为负)
定义3.5 可实施的分配规则 对于一个单参数环境,对于一个分配规则,如果存在一个支付规则
使得直接显示机制
是DSIC的,则称这个分配规则
是可实施的。
定义3.6 单调分配规则 如果对于每个智能体和所有其他智能体的出价向量
,对智能体
的分配函数
是
的出价
的单调非减函数,那么就称分配规则
是单调的。(显然,出价越高,赢得的物品越多)
定理3.7 迈尔森引理 在一个单参数环境下:
- 一个分配规则
是可实施的,当且仅当它是单调的(说明定义3.5和3.6是等价的)
- 如果
是单调的,那么存在唯一的支付规则,使得直接显示机制
是DSIC的,且使得对于所有报价
均有
(唯一的支付规则,还是挺惊讶的)
- 支付规则有明确的表达式
迈尔森引理的证明
part1 可实施等价于单调
是可实施的
存在
使得
是DSIC的。
对于任意的
,必有(请想象两智能体,其中一个的估值是
,则有式1,另一个的估值是
则有式2:
是单调的。(注意证明过程中
的任意性和存在性的转变,理解了好久才想明白)
part2 支付规则
的唯一性和表达式
观察式(3.4),令,则有
(揭示了
在
处的变化 =
[
在
处的变化] )
(最后两步不是很严谨,不过总算强行讲书中列出的。想了两天才得到勉强能让自己接受的证明过程,原书的证明过程实在有点难理解。如果有看到严谨地数学证明过程,烦请在评论区提供出处)
支付公式的运用
根据式3.5,可以分析【二价拍卖】和【关键字搜索拍卖】(前者比较简单,不复述,后者如下,其也是对练习2.3的解答
题设:有个广告位,点击率分别为
。
表示分配规则,对于所有
,将质量第
好的广告位分配给出价第
高的竞拍者。这个分配规则是单调的。因此迈尔森支付公式(3.5)可以给出唯一的支付规则
,使得机制
是DSIC的。考虑一个报价向量
,对所有报价从高到底排序有
。考虑竞拍者
在第
个广告位上的单位点击量支付:
竞拍者的分配突变在
之间,每个diff为
,因此
(感觉不是那么显然的,经济学的书大多有这个毛病)
据此,每当一个竞拍者的链接被点击,实际上他需要支付的数额是比他低的其他报价的一个凸组合(已经忘记凸组合是个啥定义了,反正是个组合就对了)。
在做练习2.3时,凭直觉给出了错误的答案,同样是将第好的广告位分配给第
高的报价者,但是收取第
高的报价。事实上这个答案虽然不是DSIC的,但是误打误撞,是现实中搜索引擎常用的方式,被称为“广义二价”(GSP)拍卖(显然GSP的支付更高)。
GSP拍卖在某种意义上和DSIC的拍卖机制是等效的(Interesting!)
练习3.1~3.3 略(已经证明了原命题,何必费那个劲去证明逆否命题)
练习3.4 (感觉要学到第7章才能正确回答这个问题,因为对于一个竞拍者,除了有私人估值,还有一个公开的质量,这都有两个参数了,而前面都是单参数的)简单尝试一下吧:
首先假设所有人都真实报价,
不妨假设竞拍者获得广告位
,则社会福利为
在满足
最大。
因此针对任意报价,我们按
从高到低的顺序分配广告位。
显然这个分配规则是单调的,可以根据公式3.5,得到唯一使得机制为DSIC的支付规则。
假设,竞拍者
的到广告位
,
分配函数突变的位置:,分配的突变量为:
(好吧,这个结果带着一半的猜测)
问题3.1
(a)我们已经得到了相同分配方案的满足DSIC的唯一支付函数,既然这个支付函数和GSP的支付函数不同,那么GSP肯定不是DSIC的啊
(b)。。。
(做不出来了,以后的练习和问题可能会留空,等读第二遍的时候尝试完善,敬请期待)
问题3.2
问题3.3
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/157560.html