策略型博弈 案例:艺术品拍卖的策略型 占优策略解 案例研究续：拍卖中的占优策略

Presentation on theme: "策略型博弈 案例:艺术品拍卖的策略型 占优策略解 案例研究续：拍卖中的占优策略"— Presentation transcript:

1 策略型博弈 案例:艺术品拍卖的策略型 占优策略解 案例研究续：拍卖中的占优策略
第2章 策略型博弈 策略型博弈 案例:艺术品拍卖的策略型 占优策略解 案例研究续：拍卖中的占优策略

2 策略型博弈 博弈的策略型由三项内容所确定： 1. 博弈中局中人的名单. 2. 每个局中人可使用的策略集.
博弈的策略型由三项内容所确定：  1. 博弈中局中人的名单. 2. 每个局中人可使用的策略集. 3. 与任何策略组合（每个局中人一个 策略）相对应的盈利.

3 盈利是冯诺依曼-摩根斯坦效用。最简单的 博弈类型是两个局中人有两个策略的博弈。 策略型 :
局中人2 北 南 局中人1 高 π1 , π2 π1 , π2 (高,北), (高,北) (高,南),(高,南) 低 π1 , π2 π1 , π2 (高,北), (高,北) (高,南), (高,南)

4 当局中人多于两个，以及每个局中人有两个以上的策略时，对策略型的三个分量使用下述符号：
局中人将标记为1，2，…，N。一个局中人代表将表示为第i个局中人。 局中人i的策略通常表示为si，一个特定的策略表示si*或si#。除了局中人i以外的所有其它局中人的策略选择记为s-i。 πi 将表示局中人i的盈利(或冯诺依曼-摩根斯坦效用)函数。对于策略组合，s1*，s2*，…，sN*，其中每一个局中人相应于一个策略，局中人i的盈利将表示为πi (s1*，s2*，…，sN*)。

5 囚徒困境 （c = 认罪，nc = 拒绝认罪） 性别争端（F = 足球，O = 歌剧） 卡尔文＼克雷 c nc c 0, 0 7, -2

6 抛硬币打赌（Matching pennies） ( h = 正面, t = 反面)
局中人1＼局中人2 正面 反面 正面 1，-1 -1，1 反面 -1，1 1，-1 鹰-鸽（或懦夫博弈） （t = 强硬, c = 退让） 局中人1＼局中人2 t c t -1, -1 10, 0 c 0, 10 5, 5

7 投票 对每一个投票者，在这个博弈中的策略有三个部分：在 第一轮中如何投票和第二轮中如何投票，而在第二轮 中的投票本身有两个分量。第一个分量是，如果议案 A在第一阶段通过后在第二轮中投票人如何投票，第 二分量是，如果（在第一轮中）议案B通过后，该投 票人又将如何投票。特别地，每个投票人有下述8个 策略可供选择*。 AAN; AAB; ANB; ANN; BAN; BAB; BNB; BNN; *当然，投票人知道她在第一轮中自己是怎样投票的。原则上，她的策略也可 以根据这个信息。目前我们将略去这种复杂性，因为这样的话，每一个策 略中分量的个数将增加到5——替代原来的3。（为什么？）

8 与展开型的等价性 两种表示博弈的方式是等价的：每一个展开 型博弈可以写成策略型且反之亦然。

9 案例：艺术品拍卖的策略型 艺术品拍卖：描述
假如我们被带入位于纽约洛克菲勒中心的索士比派克伯尼特的 大型拍卖场之一。拍卖商站在房间前面的讲台上。她的旁边有 一对随从举着待拍卖物件的影像。设想待拍卖的物件是雷诺伊 （Renoir, 1841—1919）的一组绘画；你很想拥有标号为 “#264”的那件可爱的咖啡吧景色。你必须开始做如下的事。 注册：如果你打算投标，必须在商品展销室的入口处注册。那 里你将得到一块写有编号的拍卖牌。（为了注册，恐怕你需要 一张信用卡。) 出价程序：一旦轮到标号#264，“你出价所必须做的就是举起你 的拍卖牌并等待拍卖商理会你，你不必叫出你出价的数——通 常由拍卖商以10%的增量自动确定高一些的出价。你不必坐的 毕恭毕敬；抓耳挠腮不能算作为一个出价（除非你与拍卖商事 先就做了安排）。如果没有人超过你的出价，就是说，没有其 他的拍卖牌举起，那么拍卖商敲下小木槌以结束拍卖。”

10 艺术品拍卖：策略型 局中人：注册的那些人 策略：考虑局中人策略的一个简单方 法是认定局中人愿意举牌的最高价。 结局：最后一个举牌的拍卖者赢得雷 诺依作品（抓耳挠腮者不能得到）。 盈利：赢者将付多少钱？

11 占优策略解 定义. 如果不管其他局中人选择什么样的 策略，局中人i的策略si的盈利严格地大 于他的所有其他策略的盈利，换言之，
πi (si, s-i) >πi (si, s-i) 对一切si和s-i成立 其中s-i是除了局中人i以外的其他局中人 选择的策略向量。那么我们称策略si强优 于局中人i的所有其他策略.

12 考虑局中人1，我们称该局中人的策略b——记作s1b——优于其他策略——s1a，意指针对局中人2的两个策略来说，s1b比s1a 更好一些；于是
π1(s1b , s2b) >π1(s1a , s2b)   第一个不等式指出了，如果局中人2采用了他的第一个策略，那么s1b比s1a 产生较高一些的盈利；第二个不等式指出了即使局中人2选择他的第二个策略，同样的事实也成立。

13 定义. 如果局中人i的策略si，对于其他局中人的 每一个策略来说，至少与他的另一个策略s#i一样 地好，而对于其他局中人的某个策略来说，si严 格地好于s#i，即
在这种情况，我们称s#i为劣策略。如果si弱占优 于其他任何一个策略si，那么si被称为弱占优策 略*。 * 同样的定义应用于强优。如果公式3.1中令si =si#，称策略 si强优于策略。于是策略si#称作强劣的。

14 占优策略解 当每一个局中人都有占优策略时，博弈就有一个 占优策略解。
一个策略的组合，如果每一个局中人的策略都是 占优策略，那称这个策略的组合为占优策略解。 例如，囚徒困境中（认罪，认罪）构成了一个占 优策略解。 左 右 顶 7, 3 5, 3 底 7, 0 3, -1

15 案例研究续：拍卖中的占优策略 竞拍人以她对雷诺依作品的真实估价作为她的最高叫价的 策略是一个占优策略。不管其他竞拍人怎样叫价，你所 能做得最好的办法是，以你认为画所值的价格作为叫价 来。从不同的方式讲，如果你认为画值3000美元，你最 好的办法是闭上你的眼睛，举着你的拍卖牌直到听到拍 卖商宣布的叫价高于3000美元为止 为什么它是个占优策略，与其他几个策略作比较。假使你 决定“节省你的出价”，并且在2500美元处放下拍卖牌。 有两种可能的情况。一种情况是，还有某些人最高叫价 超过3000美元，其次，若最高叫价——即赢得雷诺依作 品的叫价——是2700美元。现在，你感觉自己象个傻瓜！ 你失去了一幅估价为3000美元的画，而你用（稍高于 2700美元）就可以拥有它。3000美元的最高叫价比起 2500美元的叫价来决不会差些——而有时候严格地更好 一些。

16 总 结 策略型博弈由局中人的名单，每个局中人可使用的策略，和关于任何策略组合（一个策略对应于一个局中人）的盈利来描述。
策略型博弈由局中人的名单，每个局中人可使用的策略，和关于任何策略组合（一个策略对应于一个局中人）的盈利来描述。  每当博弈中有两个局中人，策略型可以很方便地表达为盈利矩阵。对于更多的局中人情况，符号表示式更方便一些。  每一个展开型博弈可以表示成策略型。每一个策略型博弈至少有一种展开型表示。 不管其他局中人如何做，占优策略比其他每一个策略给出较高的盈利。  当每一个局中人都有占优策略时，博弈存在占优策略解。  艺术品拍卖可以建模为策略型博弈，真实地叫价是该博弈的占优策略解。

17 概念 劣与非劣策略 累次剔除劣策略 案例研究：选举联合国秘书长 更正式的定义 讨论
第三章 占优可解性 概念 劣与非劣策略 累次剔除劣策略 案例研究：选举联合国秘书长 更正式的定义 讨论

18 概念 1. 劣与非劣策略 定义。 策略s#i 劣于另一个策略s-i，如果对于其他局中人的每一个策略，后者与s#i 至少一样好，而对于其他局中人的某些策略，si严格地好于s#i，以致 如果一个策略不劣于任何其他策略，则称它为非劣策略。将劣策略认为“坏”策略，而将非劣策略认为“好”策略

19 3 .更多例题 2. 累次剔除劣策略 局中人2 左 (L) 右 (R) 上 (U) 1, 1 0, 1 中 (M) 0, 2 1, 0
局中人1 局中人2 左 (L) 右 (R) 上 (U) 1, 1 0, 1 中 (M) 0, 2 1, 0 下 (D) 0, -1 0, 0 3 .更多例题

20 例1： 伯川德（价格）竞争 假设双寡垄断市场中的两个公司都可以开出三个价格中的任一个——高，中或低。
进一步假设不管哪个公司开价较低的话就可以得到整个市场。 如果两个公司开价相同，他们将平分市场。这些假设——和任何的价格对——转换成两个公司的收益水平。 例如，对于公司1，只有当它的价格不高于公司2的价格，才能有所收益。

21 假定收益由如下盈利矩阵给出 公司1＼公司2 高 中 低 高 6，6 0，10 0，8 中 10，0 5，5 0，8
公司1＼公司2 高 中 低 高 6，6 0，10 0，8 中 10，0 5，5 0，8 低 8，0 8，0 4，4 剔除“高”策略后，留给我们如下盈利矩阵  公司1＼公司2 中 低 中 5，5 0，8 低 8，0， 4，4

22 例3：投票博弈 投票博弈：采用多数规则，三个投票人挑 选两个议案A或B中的一个。通过了第Ⅰ 轮的方案再面临与维持原状N（“都 不”）进行决赛。三个投票人的真实偏 爱如下：  投票人1： 投票人2： 投票人3： 

23 每一个策略有三个分量：策略A（后面跟）AN是指 “投A的票而反对B，然后在第Ⅱ轮中投A的票（反对 N），或投N的票（反对B）。”至于盈利，让我们使 用约定，如果他最愿意的方案通过，则获盈利1，第二 喜欢的通过，盈利为0，如果第三喜欢（即，最不喜欢） 方案通过，则他的盈利为-1。 在第Ⅱ轮中真实地投票优于非真实性投票；于是，对 投票人1来说，AAN优于ANN, ANB，和AAB。类似地， BBN优于BNN, BNB, 和BAB。由同样的逻辑推理，对 于局中人2，作为第Ⅱ轮中的投票策略，AB优于NB, NN, 和AN；对局中人３，第Ⅱ轮的投票策略NN优于 其他策略。可以看到如果投票人在第Ⅱ轮中真实地投 票，那么在那个阶段，A击败N，而B输给N。

24 剔除了（第Ⅱ轮非真实的）劣策略后，策略型如下 投票人３采用ANN 投票人１＼投票人２ AAB BAB AAN 1, 0, 0 1, 0, 0
剔除了（第Ⅱ轮非真实的）劣策略后，策略型如下  投票人３采用ANN 投票人１＼投票人２ AAB BAB AAN 1, 0, 0 1, 0, 0 BAN 1, 0, 0 0, -1, 1 投票人３采用BNN AAN 1, 0, 0 1, -1, 1 BAN 0, -1, 1 0, -1, 1 现在看到，对局中人１，AAN优于BAN，对局中人２AAB优于 BAB，而对局中人３，BNN优于ANN。从而，我们得到了 IEDS结局为：投票人１取AAN，投票人２取AAB，投票人３ 取BNN，A（以２票）赢得第Ⅰ轮，而在决赛中继续击败N。

25 案例研究：选举联合国秘书长 考虑有两个投票人的选举——假如为美国与非洲。 投票人1——美国——首先投票并着手否决三个 候选人A（安南），B（加利），和H（布鲁特 莱特）中的一个。然后，投票人2——非洲—— 否决两个余下的候选人中的一位。假如美国和 非洲关于三个候选人的中意顺序如下：  美国： 非洲：

26 在一轮剔除之后，实际上的博弈成为： 美国＼非洲 HHA A -1, 1 B 0, 0 H -1, 1
非洲 HAA HHA HAB HHB BAA BHA BAB BHB 美国  A -1, 1 -1, 1 -1, 1 -1, 1 1, -1 1, -1 1, -1 1, -1 B 1, -1 0, 0 1, -1 0, 0 1, -1 0, 0 1, -1 0, 0 H -1, 1 -1, 1 0, 0 0, 0 -1, 1 -1, 1 0, 0 0, 0 在一轮剔除之后，实际上的博弈成为： 美国＼非洲 HHA A -1, 1 B 0, 0 H -1, 1

27 占优可解性的更正式的定义 考虑有N个局中人的策略型博弈；局中人i的策略用si来表示；令Si表示局中人i的策略集。
在第Ⅰ轮，局中人i的劣策略集表示为 Di(I)，换言之， Di(I) = siSi: si是劣策略 理性的局中人不会采用劣策略。就是说，不启用 Di(I)中的策略，这对i = 1, 2, …, N均成立。 进入第Ⅱ轮，局中人i可以在留给自己的策略集 Si  Di(I)中作进一步的决定，看看它们当中是否又有哪些现在成为劣策略了。一个策略si# 现在成为劣的，是指：假定每一个其他局中人也都在第Ⅰ轮中剔除了劣策略之后，在Si  Di(I)中存在另外一个，它始终至少与si#一样地好，而在某些时候严格地好于si#。

28 于是， 其中，S-i  D-i(I)是除了局中人i以外的所有局中人的非劣策略组合的集合 [1] 。记局中人i在第Ⅰ轮中或者在第Ⅱ轮中为劣的所有策略的全体为Di (Ⅱ)。一旦知道了没有一个局中人会采用属于Di (Ⅱ)中的策略，继续剔除任何这样的步骤，现在又成为劣的那些策略。通过这种做法，又建立了一个在前三轮中为劣策略的集合；称这个集合为Di (Ⅲ)。如此等等。 [1] 尤其S-i – D-i(I)包含了策略向量（s1, …, si – 1, si + 1, …, sN），其中每一个策略sj都是非劣的。

29 假如我们最终达到这样一个状态，剩给每一个局中人的只有一个策略，即，假定经过T轮剔除之后，剩下的集合Si  Di(T)，恰好包含了一个策略，并且这一事实对i = 1, 2,…, N都成立。在那种情况，这些每个人剩下的单一策略构成的向量称为累次剔除劣策略（IEDS）的结局，该博弈则称为占优可解的。假如这样的情况不发生——如果在某一轮，对某些局中人，尽管仍然留下多个策略，但是没有更多的策略可以被剔除——博弈就称为没有IEDS解。

30 理性的层次 没有人会采用劣策略是合理的假设。没有局中人会采用，那些一旦其他的劣策略被剔除之后成为了劣策略的策略，这件事看来也是合理的。没有一个局中人会采用只是在15轮剔除劣策略之后才转变成的劣策略，这件事似乎就不太合理。这是因为它假定，每个人都同意在连续（14次）高次数地剔除行动中所有的人都是理性的。如果其他局中人某一次理性的“失误”可能代价昂贵的话，这尤其成问题。考虑下述博弈：  1＼2 左 中心 右 顶 4，5 1，6 5，6 中间 3，5 2，5 5，4 底 2，5 2，0 7，0

31 剔除的顺序（和非唯一的结局） 当策略是劣的但不是强劣的，剔除的 顺序就要紧了。考虑下面的博弈。 顶 0，0 0，1 底 1，0 0，0
当策略是劣的但不是强劣的，剔除的 顺序就要紧了。考虑下面的博弈。  1＼2 左 右 顶 0，0 0，1 底 1，0 0，0

32 不存在性。 不是所有的博弈都是占优可解的。例如，在性别 争端、扔硬币打赌和布鲁特上校中，不存在劣 策略，因而，不存在IEDS结局。在以下博弈中， 每一个局中人都有一个劣策略——“差”—— 可是在剔除那个策略后留下来的是一个只有非 劣策略的2×2博弈。  1＼2 左 中 差 顶 1，-1 -1，1 0，-2 中 -1，1 1，-1 0，-2 差 -2，0 -2，0 -2，-2

33 总 结 1. 没有一个理性的局中人会采用劣策略，他宁 愿采用一个非劣的策略。而且一个理性的局 中人不认为他的对手会采用劣策略。
1. 没有一个理性的局中人会采用劣策略，他宁 愿采用一个非劣的策略。而且一个理性的局 中人不认为他的对手会采用劣策略。  2. 劣策略的剔除可以导致一系列连锁反应，逐 步缩小一组局中人采取行动的范围。如果存 在一个最终唯一预测，则称它为IEDS解。  3. 当在IEDS解中包含有许多轮次的剔除时， 有理由去关心其预测的合理性。