且听风吟

前两天偶然找到了《game theory》这本书的电子版，刚看了前两章感觉很有趣，我尤其喜欢这种把问题形式化再去解决的过程。第二章主要讲决策时使用的方法，比如第二价拍卖：出价最高者赢得拍卖，但只需支付第二高的价格，和以下所讨论的 The pivotal mechanism 下文把 pivotal 直译成 "关键"(感觉有点怪)。

初次接触博弈论，如有误述请一定指出。🥺

概念#

民意调查是组织进行项目决策的重要工具，但参与者报告的意愿并不总能反映出真实的情况。因为受访者可能会由于价格，税收，偏好等各种原因放大或缩小其真实的意愿。

比如社区要兑钱建设足球场：热爱足球运动的参与者 A 在调查时可能会夸大自己愿意支出的价格，因为 A 会认为在真实出价时，高出来的价格会均摊到其他参与者身上。相反对于不喜欢足球运动的参与者 B 考虑到建设足球场的支出和自己的收益，会报告出低于自己真实意愿。Everybody lies

关键机制 (pivotal mechanism) / Clarke 机制给出了一种激励受访者报告他们的真实意愿的博弈模型。

关键机制的思想在于让每个参与者认为自己是决定结果的关键，从而诱导参与者报告真实信息，以供决策。基本的流程如下:

1. 每个参与者报告自己私有信息 (比如愿意支付的价格)
2. 计算所有信息的总和，得到一个决策结果
3. 对每个参与者，考虑剔除其信息后重新决策的结果是否有改变
4. 只向改变了结果的参与者收费 (比如额外的税)

举例#

设想一个场景，政府考虑在某社区中建造一个公园，预计总共需要需要花费 $\$C$ 社区中一共有 $n$ 位市民。如果决定建造公园，则每位市民需要支出 $\$c_i (c_1+c_2+...+c_n = C)$ 由于公园对每个市民的收益不同 (比如离每个人家里的距离不一样)，所以每位市民实际的支出会有所不同。

假设每位市民 $i$ 的初始财富为 $\$m_i(m_i>0)$ 若公园建成其能够获得的收益为 $v_i$ (这里把收益量化为财富，注意收益有可能是负值) 则对于市民 $i$ 的收益函数为 (这个公式只在后续数学证明的时候有用到)

政府在进行决策时，只有满足总收益大于总支出即 $\sum_{i=1}^{n}v_i > C$ 的情况才会决定建造公园。但问题是政府无法得知每位市民的 $v_i$ 所以需要进行民调。

使用关键机制进行民意调查#

1. 第一步，每位受访市民报告一个其在公园建设过程中取得的收益 $w_i$ 在绝对诚实的情况下 $w_i$ 应该等于 $v_i$

2. 第二步，计算所有提交收益的总和，通过民调进行的决策就变成了只有在 $\sum_{i=1}^{n}w_i > C$ 的情况下才会建造公园。

3. 第三步，将参与者分成关键和不关键两类，满足以下条件即认为不关键 (剔除这个参与者的 $w_j$ 总体的决策不会发生改变)

第一行表示，算上 $i$ 和不算上 $i$ 所有人的收益总和都大于所需支出总和，决策不变 (建设公园)
第二行表示，算上 $i$ 和不算上 $i$ 所有人的收益总和都小于所需支出总和，决策不变 (不建公园)

4. 第四步，对关键市民 (非不关键市民) 征收一定的税，额度为

感性分析#

由于关键市民需要支付额外的税，每位市民相对理性的选择是使得自己的 $w_i = c_i$ 这样自己总不会是关键市民：

• 如果原本总 $W \ge C$ 则加上 $c_i$ 之后两边仍是大于关系 $W+w_i \ge C+c_i$
• 如果原本总 $W < C$ 则加上 $c_i$ 之后两边还是小于关系 $W+w_i < C+c_i$

在绝对诚实和理性的环境下，对所有参与者应该有 $w_i = v_i$ 这样政府通过统计出来的 $\sum_{i=1}^{n}w_i = \sum_{i=1}^{n}v_i$ 和 $C$ 比较，就能够得到最准确的决策。

数学证明#

数学证明主要通过计算每个参与者的收益函数来证明 $w_i = c_i$ 确实是每个参与者的最优选择 (每个 $i$ 都希望自己的最终财富最高)。这也是下面证明中所说的 our hypothesis

• $w_i$ 表示报告的收益 (量化成财富值)
• $v_i$ 表示真实收益 (量化成财富值)
• $c_i$ 表示在建造公园情况下的真实支出，如果不建设，则这一项为 $0$
• $\bar{m}_i$ 表示参与者 $i$ 的初始财富值
• $i’s utility$ 表示 $i$ 的最终财富值 $i$ 会按照最大化这个值的策略进行决策

case 1#

case2#

case3#

case4#