多 重 均 衡 与 优 化 吴 建 设
多 重 均 衡 与 优 化 1 博 弈 的 多 重 纳 什 均 衡 2 帕 累 托 最 优 均 衡 3 帕 累 托 最 优 均 衡 与 纳 什 均 衡 的 关 系 4 如 何 得 到 帕 累 托 最 优 均 衡
1 博 弈 的 多 重 纳 什 均 衡 一 个 例 子 : 选 数 博 弈 规 则 : 有 两 个 人,1~10 十 个 数 字, 每 个 人 可 以 选 择 其 中 的 任 意 五 个 ; 如 果 两 个 人 的 选 择 没 有 重 复, 每 人 得 到 50 元 ; 否 则, 各 为 0 问 题 : 有 多 少 个 纳 什 均 衡?
多 重 纳 什 均 衡 : 产 品 标 准 许 多 博 弈 可 能 有 多 个 纳 什 均 衡 3.5 5.5 这 个 博 弈 被 称 为 3.5 8, 8 3, 2 5.5 2, 3 6, 6 协 调 博 弈 : 有 两 个 纯 战 略 纳 什 均 衡, 一 个 混 合 战 略 均 衡 哪 一 个 将 出 现 呢?
交 通 博 弈 靠 左 行 靠 右 行 靠 左 行 1,1-1,-1 靠 右 行 -1,-1 1 1,1
约 会 博 弈 芭 蕾 舞 足 球 场 芭 蕾 舞 1,2 0,0 足 球 场 0,0 2,1
进 门 博 弈 先 进 后 进 先 进 -1,-1 2,1 后 进 1,2-1,-1 1
资 源 争 夺 博 弈 ( 鹰 鸽 博 弈 ) Hawk Dove Hawk -1,-1 1 10,00 Dove 0,10 5,5 在 只 有 鸽 子 一 个 苞 谷 场 里, 突 然 加 入 的 鹰 将 大 大 获 益, 并 吸 引 同 伴 加 入 但 结 果 不 是 鹰 将 鸽 逐 出 苞 谷 场, 而 是 一 定 比 例 共 存, 因 为 鹰 群 增 加 一 只 鹰 的 边 际 收 益 趋 零 时 ( 鹰 群 发 生 内 斗 ), 均 衡 将 到 来
鹰 鸽 博 弈 的 启 示 ( 应 用 ) 而 且 如 果 两 个 国 家 的 实 力 相 同 的 话, 战 争 的 可 能 性 就 会 不 大 世 间 不 同 的 国 家 他 们 的 实 力 不 可 能 总 是 势 均 力 敌 的, 他 们 之 间 的 实 力 会 不 断 的 变 化 战 国 的 时 候 会 有 不 同 的 国 家 成 为 霸 主, 也 正 是 因 为 在 六 国 之 中 有 一 个 国 家 的 实 力 超 出 了 其 他 的 五 个 国 家 有 一 个 霸 主 出 现 的 时 候, 世 间 的 战 争 就 会 停 止 然 后, 随 着 时 间 的 推 移, 六 国 之 间 的 实 力 会 因 为 各 国 国 王 的 改 变 或 是 政 策 的 改 变 产 生 了 不 同 的 变 化 后 者 居 上 的 心 理 不 会 甘 愿 受 之 前 霸 主 的 牵 制 与 管 理, 新 的 一 轮 战 争 就 又 会 出 现 直 到 下 一 个 平 衡 的 出 现
帕 累 托 最 优 均 衡 如 果 从 一 种 策 略 组 合 到 另 一 种 策 略 组 合 的 变 化 中, 在 没 有 使 任 何 人 境 况 变 坏 ( 收 益 变 少 ) 的 前 提 下, 使 得 至 少 一 个 人 变 得 更 好, 这 就 是 帕 累 托 改 善 帕 累 托 最 优 的 状 态 就 是 不 可 能 再 有 更 多 的 帕 累 托 改 善 的 策 略 组 合 ; 换 句 话 说, 不 可 能 再 改 善 某 些 人 的 境 况, 而 不 使 任 何 其 他 人 受 损
帕 累 托 最 优 均 衡 帕 累 托 最 优 是 指 优 化 问 题 ( 例 如 资 源 分 配 问 题 ) 的 一 种 理 想 状 态, 即 假 定 固 有 的 一 群 人 和 可 分 配 的 资 源, 从 一 种 分 配 状 态 到 另 一 种 状 态 的 变 化 中, 在 没 有 使 任 何 人 境 况 变 坏 的 前 提 下, 也 不 可 能 再 使 某 些 人 的 处 境 变 好 换 句 话 说, 就 是 不 可 能 在 不 损 害 一 些 人 的 利 益 的 情 况 下, 去 增 加 另 一 些 人 的 利 益
在 图 示 的 例 子 中, 假 定 较 小 的 值 优 于 较 大 的 值, f1 是 参 与 人 1 的 收 益,f2 是 参 与 人 2 的 收 益. 状 态 C 不 在 帕 累 托 前 沿 面 (Pareto Frontier) 因 为 存 在 帕 累 托 改 进 使 它 改 进 到 A 或 者 B 点
3 帕 累 托 最 优 均 衡 与 纳 什 均 衡 的 关 系 帕 累 托 最 优 均 衡 : 满 足 帕 累 托 最 优 的 均 衡 纳 什 均 衡 是 不 是 均 为 帕 累 托 最 优 单 从 逻 辑 上 来 分 析, 能 不 能 得 出 纳 什 均 衡 ( 博 弈 的 结 果 的 一 种 ) 都 是 帕 累 托 最 优 的? 事 实 是, 纳 什 均 衡 不 一 定 是 帕 累 托 最 优 产 品 标 准 博 弈 和 囚 徒 困 境 博 弈 的 结 果 就 是 例 子 ( 见 下 页 )
3 帕 累 托 最 优 均 衡 与 纳 什 均 衡 的 关 系 囚 徒 困 境 (Prisoner s Dilemma) D C D C D P P T S D -5-5 0-10 C S T R R C -10 0-1 -1 T>R>P>S, 2R>T+S
3 帕 累 托 最 优 均 衡 与 纳 什 均 衡 的 关 系 (3.5, 3.5 ) 帕 累 托 优 于 (5.5, 5.5 ) 3.5 5.5 Cheap talk 可 以 帮 助 协 调 到 一 个 帕 累 托 最 优 均 衡 3.5 8, 8 3, 2 5.5 2, 3 6, 6
帕 累 托 最 优 指 的 是 : 在 给 定 现 有 资 源 条 件 下, 不 存 在 任 何 其 他 配 置 结 果 使 某 些 人 情 况 更 好, 而 又 不 使 任 何 其 他 人 处 境 更 坏 显 然, 在 上 述 囚 徒 困 境 模 型 当 中, 甲 乙 两 个 人 都 从 理 性 的 角 度 出 发, 追 求 自 身 效 用 的 最 大, 结 果 是 双 方 不 合 作, 都 认 罪 了 也 就 是 说, 实 现 了 纳 什 均 衡 但 是, 如 果 甲 与 乙 合 作, 产 生 的 结 果 要 比 双 方 不 合 作 好 得 多 也 就 是 说, 如 果 双 方 合 作, 就 存 在 帕 累 托 改 进 ( 帕 累 托 改 进 是 指 一 种 变 化, 在 没 有 使 任 何 人 境 况 变 坏 的 前 提 下, 使 得 至 少 一 个 人 变 得 更 好 帕 累 托 改 进 是 达 到 帕 累 托 最 优 的 路 径 和 方 法 )
3 帕 累 托 最 优 均 衡 与 纳 什 均 衡 的 关 系 结 论 纳 什 均 衡 不 一 定 是 帕 累 托 最 优 均 衡 帕 累 托 最 优 均 衡 也 不 一 定 是 纳 什 均 衡 有 一 些 纳 什 均 衡 是 帕 累 托 最 优 均 衡
4 如 何 得 到 帕 累 托 最 优 均 衡 : 协 调 帕 累 托 最 优 均 衡 : 可 以 通 过 协 商 选 择 一 个 纳 什 均 衡 ;cheap p talking; 仅 仅 自 我 理 性 是 不 够 的 ; FOCAL POINT(PROMINENCE):Schelling ( O ) (1960); 文 化 与 制 度 行 业 组 织 ;
锁 定 效 应 与 路 径 依 赖 如 果 博 弈 参 与 人 很 多, 达 成 协 议 的 成 本 很 高, 最 初 的 非 帕 累 托 均 衡 可 以 被 锁 定 (lock-in) in), 导 致 路 径 依 赖 (path dependence): 每 个 人 多 偏 好 于 新 产 品 ( 或 标 准 ), 如 果 其 他 人 都 选 择 新 产 品 的 话 ; 但 由 于 每 个 人 都 预 期 其 他 人 不 会 选 择 新 产 品, 所 以 每 个 人 的 最 优 选 择 是 不 转 向 新 产 品, 结 果 是 整 个 社 会 被 锁 定 在 现 有 的 产 品 ( 标 准 )( 非 帕 累 托 最 优 )
例 子 : 教 师 招 聘 只 留 本 校 生 不 留 本 校 生 只 留 本 校 生 2,2 2,0 不 留 本 校 生 0,2 10,10 (10,10) 10) 是 帕 累 托 占 优 的 纳 什 均 衡
交 通 博 弈 与 交 通 规 则 靠 左 行 靠 右 行 靠 左 行 1,1-1,-1 靠 右 行 -1,-1 1 1,1
交 通 规 则 的 演 变 在 多 个 纳 什 均 衡 之 间 不 存 在 优 劣 之 分 时, 偶 然 事 件 对 选 择 具 有 重 要 意 义 ; 从 历 史 上 来 考 察, 许 多 交 通 规 则 一 开 始 并 不 体 现 为 法 律, 而 是 长 期 演 化 而 来 的 在 欧 洲 大 陆 的 早 期, 道 路 行 走 规 范 是 非 常 地 方 化 的, 有 些 地 方 采 用 靠 左 走 的 习 惯, 有 些 地 方 采 用 靠 右 走 的 习 惯, 是 不 统 一 的 只 是 随 着 道 路 的 增 加 和 地 区 间 交 往 的 扩 大, 地 方 性 的 习 惯 才 逐 步 演 变 为 区 域 性 的 规 范, 然 后 有 演 变 为 全 国 性 的 规 范 但 直 到 19 世 纪 前, 道 路 规 则 也 仅 仅 是 作 为 规 范 而 得 到 遵 守, 而 不 是 作 为 交 通 法 律 而 得 到 执 行 现 在 欧 洲 大 陆 的 靠 右 走 的 规 则 是 在 法 国 兴 起 的
交 通 规 则 的 演 变 在 法 国 大 革 命 以 前, 贵 族 的 马 车 习 惯 上 是 靠 左 行 的, 穷 人 在 路 上 看 到 富 人 的 马 车 来 了, 要 站 在 马 路 的 右 边 因 此, 靠 左 行 与 特 权 阶 级 相 联 系, 而 靠 右 行 被 认 为 更 为 民 主 随 着 法 国 大 革 命, 作 为 一 个 革 命 的 象 征, 规 定 所 有 的 车 都 要 靠 右 走 随 着 拿 破 仑 对 欧 洲 大 陆 的 征 服, 拿 破 仑 将 法 国 的 规 则 带 给 了 欧 洲, 也 包 括 靠 右 行 驶 的 规 则 当 然, 在 地 域 上 这 个 规 则 的 转 变 也 是 从 西 到 东 逐 步 完 成 的 比 如 说, 与 靠 右 行 的 西 班 牙 接 壤 的 葡 萄 牙 是 在 一 战 之 后 才 转 为 靠 右 行, 奥 地 利 是 从 西 到 东 一 个 省 一 个 省 逐 步 转 变 的, 匈 牙 利 捷 克 和 德 国 是 在 二 战 前 才 由 左 行 转 向 右 行 的 瑞 典, 一 直 到 1967 年, 才 通 过 法 律 宣 布 从 靠 左 行 改 为 靠 右 行
文 化 的 冲 突 与 协 调 为 什 么 欧 洲 大 陆 的 交 通 规 则 收 敛 于 一 致? 英 国 将 如 何 办? 文 化 冲 突, 无 论 是 组 织 和 组 织 之 间 的, 还 是 国 家 和 国 家 之 间 的, 大 部 分 不 过 是 游 戏 规 则 社 会 规 范 和 法 律 的 冲 突, 用 博 弈 论 的 话 来 说, 是 一 个 均 衡 的 选 择 问 题 ; 全 球 化 意 味 着 资 源 的 重 新 分 配
文 化 既 解 决 冲 突 又 协 调 预 期 尊 老 爱 幼 ; 妇 幼 保 护 ; 遵 师 重 教 ; 先 来 后 到 ; 社 会 分 层 与 非 对 称 权 力 ( 排 位 问 题 ; 黑 社 会 组 织 ); 公 平 观 念 ( 如 分 蛋 糕 博 弈 ); 抓 阄 ;
基 于 博 弈 的 优 化 算 法 优 化 算 法 的 结 果 是 得 到 帕 累 托 最 优 求 帕 累 托 最 优 方 法 求 帕 累 托 改 进 的 方 法 每 次 改 变 一 个 ( 或 两 个 三 个 ) 参 与 人 的 策 略, 不 减 少 其 它 人 的 收 益 的 条 件 下, 增 加 自 己 的 收 益 问 题 : 不 一 定 能 找 到 帕 累 托 最 优 ( 见 囚 徒 困 境 例 子 )
囚 徒 困 境 (Prisoner s Dilemma) D C D C D P P T S D -5-5 0-10 C S T R R C -10 0-1 -1 T>R>P>S, 2R>T+S 从 (C, D), (D, C) 按 上 述 方 式 到 不 了 (C, C)
基 于 博 弈 的 优 化 算 法 优 化 算 法 的 结 果 是 得 到 帕 累 托 最 优 求 纳 什 均 衡 的 方 法 每 次 改 变 一 个 参 与 人 的 策 略, 增 加 自 己 的 收 益 问 题 : 不 一 定 能 找 到 帕 累 托 最 优 ( 见 囚 徒 困 境 例 子 ) 对 策 恰 当 的 设 计 博 弈 使 优 化 问 题 的 解 成 为 博 对 策 : 恰 当 的 设 计 博 弈, 使 优 化 问 题 的 解 成 为 博 弈 的 纳 什 均 衡
基 于 博 弈 的 优 化 算 法 优 化 算 法 的 结 果 是 得 到 帕 累 托 最 优 相 互 结 合 的 方 法 : 灵 活 多 变 具 体 问 题 具 体 设 计