《机制设计、维克里—克拉克—格罗夫斯(VCG)拍卖与数字社群激励相容工程》各章定量结论
一条规则怎样才能让每个参与者说真话、出力而不作弊?本书是 5D Library 第 50 本,用机制设计考察拍卖、广告竞价与线上社群的积分、徽章和声誉规则,并把能证明的、需要限定的与作者的模型分开。第 27 本已讨论的维克里二价拍卖、收益等价、迈尔森—萨特思韦特定理与克拉克枢纽机制只作回顾。本书依次讨论:显示原理的占优策略与贝叶斯两种版本及其证明,以及它依赖的承诺能力(一位卖家不能承诺不降价时,1,000 期、贴现因子 0.99 的收入只有承诺时的 18.2%);多物品 VCG 作为外部性定价(三件物品的组合拍卖中 20,000 次误报都无利可图,但收入 12 低于核心下限 13),以及假名竞价——拍卖中的女巫攻击:一个出价者分身为两个身份可把支付从 8 降到 0,在含互补与组合出价的随机市场中 206/600 个存在有利的分身,所有出价者都是替代品时为 0/600;广义二价拍卖(GSP)中说真话不是均衡,局部无嫉妒均衡的收入介于 VCG 与上界之间(示例 920 至 1,000);迈尔森最优拍卖的虚拟估值、与人数无关的最优保留价、布洛—克伦佩雷尔定理,以及非正则分布的熨平(示例中最优拍卖比最佳保留价二价拍卖多收 1.4%—3.3%);赫维茨 1972 年的交换经济不可能性、格林—拉丰的格罗夫斯唯一性与预算不平衡、罗伯茨仿射最大化定理(最大最小规则在 3,000 对类型中出现 1…
DOI 10.5281/zenodo.23836274 · 阅读本章所在专著 · English version
- 第 1 章 · 显示原理、激励相容与承诺
显示原理说:任何机制的均衡结果,都可以由一个让人如实报告的直接机制得到;占优策略版本与贝叶斯版本的证明都是把均衡策略「装进」机器。它让机制设计可以只研究激励相容的直接机制,但它不保证均衡唯一,依赖设计者的承诺能力,要求报告全部类型,也不保证参与者看得出占优策略。程序显示,由一价拍卖组合成的直接机制只是贝叶斯激励相容;不能承诺不降价的卖家,在多期、低等待成本时只能得到承诺收入的一小部分($d = 0.99$、1,000 期时为 18.2… - 第 2 章 · 多物品 VCG:外部性定价、核心与假名竞价
VCG 让每个人支付自己给别人造成的外部性,由此使说真话成为占优策略;程序中的组合拍卖确认了这一点。但它的收入可能低于核心,使卖家与落败者有绕开拍卖的动机(示例中 12 对 13),选择核心的拍卖可以修补这一点,代价是放弃占优策略激励相容。更严重的是,VCG 不防假名竞价:一个人分身为两个身份可以把支付从 8 降到 0;横尾等人的凹性条件给出了 VCG 防假名的充分条件,但它必须对允许申报的整个类型域成立,只检查真实出价者是不够的。 - 第 3 章 · 广告位拍卖:广义二价拍卖的均衡与 VCG
在广告位拍卖中,GSP 按下一名的出价收费,看起来像二价拍卖,但说真话一般不是均衡:示例中第 1 名下移到第 2 名可从 200 增到 300,随机实例中说真话为均衡的比例只有 0.0%—4.2%。局部无嫉妒均衡的收入介于 VCG 与一个上界之间(示例中 920 到 1,000),最低者恰好等于 VCG 的结果;「GSP 收入不低于 VCG」只在这类均衡中有保证;其他纳什均衡的收入可以低到 605,也可以高于 VCG(最高 1,355… - 第 4 章 · 迈尔森最优拍卖:虚拟估值、保留价与熨平
迈尔森引理把激励相容化为「分配单调 + 效用由包络公式决定」,由此得到「期望收入 = 期望虚拟剩余」。分布正则时,最优拍卖是保留价为 $\psi^{-1}(0)$ 的二价拍卖,保留价与人数无关(均匀分布 0.5、指数分布 1);保留价的增益随人数迅速变小,而布洛—克伦佩雷尔定理说多一名出价者胜过最优保留价。分布非正则时要熨平:程序中的例子里,最优拍卖比最佳保留价的二价拍卖多收 1.4%—3.3%,而按原始虚拟估值分配的规则不单调、不可… - 第 5 章 · 不可能性:赫维茨、格林—拉丰与罗伯茨
赫维茨 1972 年的不可能性是关于两人交换经济的精确结论:说真话、有效与个体理性不能兼得;程序中瓦尔拉斯机制、不交易与独裁各缺一项。格林—拉丰证明在不受限制的估值域上只有格罗夫斯机制有效且占优策略激励相容,而格罗夫斯机制不能预算平衡;克拉克税在边缘项目中约占总福利的 42%—50%,平均退还则破坏激励。罗伯茨证明在至少三个方案、估值不受限制时,可实施的规则只有仿射最大化;最大最小规则违反弱单调性,无论怎样定价都不能如实实施。 - 第 6 章 · 社群激励:积分通胀、徽章与女巫攻击
积分是一种社群货币:按作者的模型,发放随人数增长而奖励不增长时,积分按人数增长的速度贬值(示例中月通胀 4.00%),过期只降低水平、不改变增长率,固定总量会稀释每人所得,刷分使通胀加速。徽章能改变行为:观测研究显示用户在接近阈值时加速,游戏化对学习的元分析效应为小(认知结局接近中等)、严格研究中只有认知结局稳定;简化模型显示最好的阈值取决于徽章价值与留存。对称的声誉函数不能防女巫:5 个假身份即可把攻击者的 PageRank 从第… - 第 7 章 · 原典并读:壹赏、定分与信赏必罚
《商君书·赏刑》的原话是「壹赏,壹刑,壹教」:赏只出于战功一途,刑不分等级、功过不相抵,「明赏不费,明刑不戮」。《定分》与《吕氏春秋·慎势》所引慎子的「一兔走,百人逐之」字句不同,意思相同:归属未定的有价物引起争夺,作者的模型(图洛克竞赛)显示 100 人争夺时 99% 的价值被耗散,界定归属则不耗散。「信赏必罚」不见于《商君书》,较早的出处是《韩非子·外储说右上》狐偃之语,又见《汉书·宣帝纪》赞。法家的赏罚服务于君主、参与不可退出、… - 第 8 章 · 实践与预注册检验
第八章给出四步核查表与一项预注册的激励化实验室实验:随机分配到 GSP 或 VCG 广告位拍卖,唯一主要结局为如实出价轮次的比例,最小关注效应 10 个百分点,90% 把握度每组可分析 150 人、随机化 168 人,由独立研究人员实施,判定规则写成代码。书中以标注框区分已发表的证据、可运行的 Python 计算(16 段程序)、原典与作者的模型和假说;书中所有数据都是虚构或模拟的。
模型示意算例,非实时报价