读书笔记: 博弈论导论 - 14 - 不完整信息的静态博弈 机制设计

读书笔记: 博弈论导论 - 14 - 不完整信息的静态博弈 机制设计

机制设计(Mechanism Design)

本文是Game Theory An Introduction (by Steven Tadelis) 的学习笔记。

机制设计的概念

机制设计的目标是设计一个可以达到期望收益的博弈。 由于这是根据博弈结果来推导博弈的形式,也被称为反向博弈论(reverse game theory)。 这个理论明显在经济和政治方面有很多用途。 我们假象这样一个例子:

某个政府需要设计一个关于化工厂的环保政策。 这个政策可能涉及到:几个化工厂、政府和大众。 大概的想法是:政府有一些排放许可;化工厂需要从政府那里买排放许可;政府和大众利用获得的资金改善环境。 机制设计的核心是:制定玩家的行动和支付资金的关系。

从上面的例子可以看出一些新的元素:

  • 排放许可 在理论中称之为替代选择(alternatives),或者叫做公共物品(public good)。
  • 资金的转移(monetary transfer)

新的概念:

  • 机制设计者(mechanism designer) 也称为中央集权(central authority)。中央集权不一定是玩家。
  • 替代选择(alternatives)或者公共物品(public good) 中央集权提供的公共物品或者服务。 将成为玩家的结果(outcome)的一部分。
  • 资金的转移(monetary transfer) 每个玩家获得的资金。负数表示支付的资金, 成为收益函数的一部分。
  • 收益函数 在机制设计中,玩家的结果包含两部分:公共物品和资金的转移。 另外,我们简单地加上资金部分作为收益。 所以收益函数变为: v_i(x, m_i, \theta_i) = u(x, \theta_i) + m_i
  • 所有玩家的一个结果组合(outcomes) 这里用y来表示,以区分x。 y = (x, m_1, \cdots, m_n) : x \in X, m_i \in \mathbb{R} \ \forall i \in N, \sum_{i=1}^{n} m_i \leq 0 \\ y_i = (x_i, m_i)
  • 选择规则(choice rule) 根据类型\(\theta\)得到机制的结果\(y\)。 f(\theta) = (x(\theta), m_1(\theta), \cdots, m_n(\theta)) \\ where \\ x(\theta) \text( : decision rule) \\ (m_1(\theta), \cdots, m_n(\theta)) \text( : transfer rule) 选择条件定义了每个类型想要的结果。

机制设计者面临的问题和一个方向

机制设计者面临的问题和一个方向

在不完整信息博弈中,私有信息(机制设计者不知道的信息):

  • 每个玩家的类型\theta 公共知识:
  • 类型集合\Theta
  • 每种类型的选择规则,也就是每种类型玩家倾向的结果
  • 每种类型的策略,就是每种类型玩家的倾向策略
  • 策略行动导致的结果。

机制设计的两个方向之一,是在不知道玩家的类型(这是私有信息)的情况下, 设计出一个足够聪明的博弈,能够保证:

  • 对于每种类型的玩家组合,其选择规则的结果,和博弈的贝叶斯纳什均衡的结果一致。 也就是说,其选择规则结果和博弈的策略引起的结果一致。 满足上面条件的机制,则称之实现了选择规则。 下面是相应的数学说明。
  • 机制(mechanism) 机制规定了玩家的行动集合,以及行动结果与资金转移的关系。 \Gamma = \langle A_1, \cdots, A_n, g(\cdot) \rangle \\ where \\ g : A_1 \times \cdots A_n \to Y \\
  • 玩家i的纯策略 s_i : \Theta_i \to A_i
  • 玩家i的收益函数 v_i(g(s), \theta_i)
  • 贝叶斯纳什均衡(Bayesian Nash Equilibrium) 如果满足下面条件,一个策略组合s^*(\cdot) = (s_1^*(\cdot), \cdots, s_n^*(\cdot)) 是一个机制\Gamma = \langle A_1, \cdots, A_n, g(\cdot) \rangle的贝叶斯纳什均衡: E_{\theta_{-1}} [v_i(g(s_i^*(\theta_i), s_{-i}^*(\theta_{-i})), \theta_i) | \theta_i] \geq E_{\theta_{-1}} [v_i(g(a_i, s_{-i}^*(\theta_{-i})), \theta_i) | \theta_i], \forall a_i \in A_i, \forall i \in N, \forall \theta_i \in \Theta_i 也就是说,对于每种类型组合,每个玩家,当对手的策略是这个策略组合时,这个玩家的这个策略组合的策略是最优的(其期望收益大于等于其它的所有策略的期望收益)。
  • 机制实现选择规则 如果满足下面条件,则这个机制\Gamma实现了(implement)选择规则f(\cdot): 存在一个贝叶斯纳什均衡s^*(s_1^*(\theta_1), \cdots, s_n^*(\theta_n)),满足: g(s_1^*(\theta_1), \cdots, s_n^*(\theta_n)) = f(\theta), \forall \theta_i \in \Theta_i
  • 部分实现(partial implementation)和完全实现(full implementation) 除了期望的贝叶斯纳什均衡,如果允许存在其它的、不期望的均衡,成为部分实现; 如果不允许存在其它的、不期望的均衡,成为完全实现;

揭露原理(the revelation principle)

机制设计的另外一个方向:玩家意识到机制设计者会实现他的选择条件\(f(\cdot)\)时,玩家会透露自己的类型。

  • 直接揭露机制(direct revelation mechanism) 一个选择规则\(f(\cdot)\)的直接揭露机制\Gamma = \langle \Theta_1, \cdots, \Theta_n, f(\cdot) \rangle是: A_i = \Theta_i, \forall i \in N \\ g(\theta) = f(\theta), \forall \theta \in \Theta 解释: 对于每个玩家,其行动集合\Theta是选择规则\Theta_i对应的行动集合(想象一下,每个类型对应一个策略,一个策略对应一个行动)。 对于每个类型\theta,它的选择规则(想要的)结果f(\theta)和机制设计的结果g(\theta)一致。
  • 在贝叶斯纳什均衡中诚实地可实现的(truthfully implementable in Bayesian Nash equilibrium) 一个选择规则f(\cdot)是在贝叶斯纳什均衡中诚实地可实现的, 如果这个选择规则的直接揭露机制\Gamma = \langle \Theta_1, \cdots, \Theta_n, f(\cdot) \rangle有一个贝叶斯纳什均衡s_i^*(\theta_i) = \theta_i, 也就是说,满足: E_{\theta_{-1}} [v_i(f(\theta_i, \theta_{-i}), \theta_i) | \theta_i] \geq E_{\theta_{-1}} [v_i(g(\theta_i', \theta_{-i}), \theta_i) | \theta_i], \forall \theta_i' \in \Theta_i 解释: 当解释规则的直接揭露机制有有一个贝叶斯纳什均衡解,则其实完全可满足的。

推论 14.1 : 对于贝叶斯纳什实现的揭露原理 一个选择规则f(\cdot)在贝叶斯纳什均衡中是可实现的,当且仅当它在贝叶斯纳什均衡中诚实地可实现的(truthfully implementable in Bayesian Nash equilibrium)。

揭露原理的想法:

在均衡中,玩家知道这个机制实现了选择规则f(\cdot),所以会何其保持一致。 因此他们可能会诚实地述说他们的类型,让机制设计者直接实现选择规则f(\cdot)

优势策略和Vickrey-Clarke-Groves机制

  • 优势策略 如果满足以下条件,则策略组合s^*(\cdot) = (s_1^*(\cdot), \cdots, s_n^*(\cdot))是一个机制\Gamma = \langle A_1, \cdots, A_n, g(\cdot) \rangle的优势策略: v_i(g(s_i^*(\theta), a_{-i}), \theta_i) \geq v_i(g(a_i', a_{-i}), \theta_i), \forall a_i \in A_i, \forall a_{-i} \in A_{-i}, \forall i \in N, \forall \theta_i \in \Theta_i 同时,揭露原理意味着如果选择法则f(\cdot)如果一个选择规则可以被一个优势策略实现,我们只要检测这个选择法则是在优势策略中诚实地可实现的。 即: v_i(f(\theta_i, \theta_{-i}), \theta_i) \geq v_i(f(\theta_i', \theta_{-i}), \theta_i), \forall \theta_i \in \Theta_i, \forall \theta_{-i} \in \Theta_{-i}, \forall i \in N, \forall \theta_i \in \Theta_i

推论 14.2 在一个准线性(quasilinear)环境中,给定一个实例状态\theta \in \Theta, 一个替代物(alternative)x^* \in X是一个帕累托优化,当且仅当下面有一个解: \max_{x \in X} \sum_{i=1}^I u_i(x_i, \theta_i)

  • First-best decision rule 如果对于\forall \ \theta \in \Theta, x^*(\theta)都是帕累托优化的,则x^*(\cdot)为First-best decision rule。
  • Vickrey-Clarke-Groves机制 给定一个宣布的类型\theta' 这个选择规则f(\theta') = (x(\theta'), m_1(\theta'), \cdots, m_n(\theta') )是一个Vickrey-Clarke-Groves机制, 如果x^*(\cdot)是一个第一好决定规则(first-best decision rule),并且: m_i(\theta') = \sum_{j \neq i} u_j(x^*(\theta'_j, \theta'_{-i}), \theta'_j) + h_i(\theta'_{-i}) \\ where \\ h_i(\theta'_{-i}) \text{ is an arbitrary function of } \theta'_{-i}

解释:

没有完全看懂。大概的意思是对于First-best decision rule x^*(\cdot), 可以找到一个转移规则(m_1(\cdot), \cdots, m_n(\cdot)), 让选择规则成为一个在优势策略中可实现。

下面是一个解:

  • Pivotal Mechanism - a particular form of Vickrey-Clarke-Groves机制 h_i(\theta'_{-i}) = - \sum_{j \neq i} u_j(x_{-i}^*(\theta'_{-i}), \theta'_j) \\ where \\ x_{-i}^*(\theta'_{-i}) \in \arg \max_{x \in X} \sum_{j \neq i} u_j(x, \theta'_j) \\ Thus \\ m_i(\theta') = \sum_{j \neq i} u_j(x^*(\theta'_j, \theta'_{-i}), \theta'_j) - \sum_{j \neq i} u_j(x_{-i}^*(\theta'_{-i}), \theta'_j) \\

参照

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏高性能服务器开发

去BAT,你应该要看一看的面试经验总结

说下我的面试经验吧,都是亲身经历,不喜勿喷: 我去年12月份从上一家公司离职,一直到今年3月份,基本上都在面试中度过来的。 先交代下背景:坐标上海,做技术开发,...

42940
来自专栏ACM算法日常

悬赏题No.1 - 扑克牌

ACM算法日常推出悬赏题啦,悬赏题一般是平时日常听闻的题目,题意简单,结构稍微复杂,并且不知道算法的结果,需要解题者在理解题意的情况下给出合理的解决方案和结果...

9720
来自专栏数据小魔方

空间数据可视化与simple future模型应用

这是一篇关于关于空间地理信息数据可视化与simple feature 模型应用的笔记小结。

16730
来自专栏web前端教室

坚持学一年很难,那坚持一周怎么样?[先行者课程-时间倒数-Data对象]

时间是线性的,所以依附于时间的事情也是线性发展的。例如学js,谁能一下学成高手?谁有js学习秘籍?高手只能跟你装b,却不能带你起飞。 这世界我看只有砖与狗粮是真...

21890
来自专栏牛客网

渣硕面筋release v1.0(Google已跪)

注:凡是题目需要保密的,都没有写在这里,如有同样要求请通知我修改 校招结束,我选头条 正值十一长假,赶在了小论文截稿前一天投出去了。正好国内的互联网公司校招基本...

523130
来自专栏人工智能头条

知识图谱系列 | 知识图谱的前世今生与RDF的实践

【人工智能头条导读】本文是我们知识图谱系列的第二篇文章,希望人工智能头条为大家准备的文章对大家的学习有更多的帮助。

70220
来自专栏大数据挖掘DT机器学习

python机器学习入门资料梳理

在python基本语法入门之后,就要准备选一个研究方向了。马上就要进行春季实习招聘了,加油!总结一下python机器学习方面的资料吧。 1、数据处理 1....

30650
来自专栏java工会

为什么说 C 语言比 Java 难?

“小伙子,我看你骨骼惊奇,是万中无一的编程奇才,维护世界和平就靠你了,我这有本秘籍《Java编程思想》,见与你有缘,就50块买给你了!”

27020
来自专栏码神联盟

语音识别 | Java 实现 AI 人工智能技术 - 语音识别功能

说到语音识别、语音翻译、图像识别、人脸识别等等,现在已经非常非常非常普及了,看过‘最强大脑’的朋友,也应该对‘小度’这个机器人有所了解,战胜国际顶尖的‘大脑’-...

2.4K60
来自专栏工科狗和生物喵

【计算机本科补全计划】CCF计算机职业资格认证 2017-03 试题初试

正文之前 我在之前的文章中提到过,我的老师要求我的CCF 考试考个280分来打个底,(没错,我就是那个横跨考研、工作、保研三大领域的男人)相当于是测试下我的能力...

1K90

扫码关注云+社区

领取腾讯云代金券