读书笔记: 博弈论导论 - 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) \\

参照

• Game Theory An Introduction (by Steven Tadelis)
• 读书笔记: 博弈论导论 - 01 - 单人决策问题
• 读书笔记: 博弈论导论 - 02 - 引入不确定性和时间
• 读书笔记: 博弈论导论 - 03 - 完整信息的静态博弈 预备知识
• 读书笔记: 博弈论导论 - 04 - 完整信息的静态博弈 理性和公共知识
• 读书笔记: 博弈论导论 - 05 - 完整信息的静态博弈 纳什均衡
• 读书笔记: 博弈论导论 - 06 - 完整信息的静态博弈 混合的策略
• 读书笔记: 博弈论导论 - 07 - 完整信息的动态博弈 预备知识
• 读书笔记: 博弈论导论 - 08 - 完整信息的动态博弈 可信性和序贯理性
• 读书笔记: 博弈论导论 - 09 - 完整信息的动态博弈 多阶段博弈
• 读书笔记: 博弈论导论 - 10 - 完整信息的动态博弈 重复的博弈
• 读书笔记: 博弈论导论 - 11 - 完整信息的动态博弈 战略协议
• 读书笔记: 博弈论导论 - 12 - 不完整信息的静态博弈 贝叶斯博弈
• 读书笔记: 博弈论导论 - 13 - 不完整信息的静态博弈 拍卖和竞标
• 读书笔记: 博弈论导论 - 14 - 不完整信息的静态博弈 机制设计
• Nash bargaining solution
• Mechanism design