PowerPoint 演示文稿

Transcription

1 博弈论简介 1

2 Acknowledgement John C.S. Lui Dept. of Computer Science & Engineering The Chinese University of Hong Kong Daniel R. Figueiredo School of Computer and Communication Sciences Swiss Federal Institute of Technology Lausanne (EPFL) Tamer Basar Dept. of Electrical & Computer Engineering, University of Illinois at Urbana-Champaign Vincent Conitzer Dept. of Computer Science & Department of Economics, Duke University 2

3 为什么要学点博弈论 我国自古就有运用策略思维的传统 策略思维的理论形式 现代博弈论 微观经济学的基础 广泛应用于经济生活的方方面面 建议大家掌握博弈思维方式 3

4 博弈论与信息经济学 张维迎 上海人民出版社 年中文社会科学引文索引 CSSCI 中被引用最多的五十种中文书之一, 位列 1979 年后出版的中文书第三名, 其中第一 第二名分别为 邓小平文选 和 毛泽东文集 4

5 合作博弈论 董保民, 王运通, 郭桂霞 中国市场出版社 施锡铨 北京大学出版社 5

6 Outline Basic concepts of game theory Two-person Zero-sum Games Two-person Non-zero Sum Games Game Tree and Subgame Perfect Nash Equilibrium Dynamic Games of Complete Information Dynamic Game of Complete & Perfect Information Two-Stage Dynamic Game of Complete but Imperfect Information Repeated Games Static Games of Incomplete Information Cooperative/coalitional Game theory 6

7 博弈论 博弈论 (Game Theory) 研究互动的博弈中参与者各自的选择策略 研究机智而理性的决策者之间的冲突及合作 参与者必须意识到他们的决策是相互影响的 博弈论把这些复杂关系理论化, 以便分析其中的逻辑和规律, 并对实际决策提供指导或借鉴 7

8 思考, 快与慢 丹尼尔 卡内曼 (Daniel Kahneman) 以色列裔美国心理学家 由于在展望理论的贡献, 获得 2002 年诺贝尔经济学奖 人的思考有系统性的失误, 理性人假设有固有缺陷 8

9 博弈的实例 Analysis of situations where conflict of interests are present 2 2 斗鸡博弈 Game of Chicken driver who steers away looses What should drivers do? Goal is to prescribe how conflicts can be resolved 9

10 智猪博弈 Cost to press button = 2 units When button is pressed, food given = 10 units 10

11 Decisions, decisions... 11

12 双寡头定价 - 假设石油市场上只有两个 寡头 A 和 B 它们的产量在效率最高时各生产 3000 万桶, 共 6000 万桶 生产成本为每桶 6 美元, 市场价格为 6 美元, 没有利润 如果它们勾结而限产, 假定各产 2000 万桶, 共 4000 万桶 每桶成本为 8 美元, 市场价为 9 美元, 各得 2000 万利润 如一方违约生产 3000 万桶, 另一守约生产 2000 万桶, 共 5000 万桶, 市场价为 7.5 美元 违约的一方获利 4500 万美元 (3000*1.5), 守约一方亏损 1000 万美元 (2000*(-0.5)) 12

13 决策矩阵 寡头 B 守约 违约 守约 2000, ,4500 寡头 A 违约 4500, ,0 A 决策 : 如果 B 守约, 我也守约, 则获利 2000 万, 如果我违约, 则获利 4500 万, 两相比较, 当 B 守约时, 违约更有利 如我守约,B 违约, 则我亏损 无论 B 是否守约,A 违约是优势策略,B 也同样, 最后的结果是双方都违约, 达到了和完全竞争下收支相抵没有利润的结果 13

14 欧佩克 欧佩克 ( 石油输出国组织 ) 曾在 20 世纪 70 年代大获成功, 使石油价格大幅度上升 欧佩克成立于 1960 年, 有五个国家,1973 年又有 8 个国家加入 它们控制了世界石油储藏量的四分之三 它们在 1972 年使每桶石油的价格从 2.64 美元上升到 1974 年的 美元,1981 年上升到 美元 2007 出现短期急剧飙升 14

15 中国彩电价格联盟的破产 中国彩电企业峰会于 2000 年 6 月 9 在深圳召开, 参加企业包括康佳 TCL 海信 创维 厦华 乐华 金星 熊猫 西湖 9 家业内骨干企业 会议决定实行彩电企业价格同盟, 并加强行业自律, 制定一个时期各类彩电产品的最低限价 这个同盟在踉踉跄跄地走了 44 天之后, 走到了尽头 康佳于 8 月 11 宣布康佳彩电将在全国范围内大幅降价, 最大降幅 20% 而后四川长虹又决定将其主流彩电机型降价 30% 至此 彩电价格联盟 彻底宣告破产 15

16 Applications of Game Theory Theory developed mainly by mathematicians and economists, even biologists Widely applied in many disciplines from economics to philosophy, including computer science (Systems, Theory and AI) goal is often to understand some phenomena Recently applied to computer networks Nagle, RFC 970, 1985 On Packet Switches With Infinite Storage datagram networks as a multi-player game paper in first volume of IEEE/ACM ToN (1993) Competitive Routing in Multi-User Communication Networks wider interest starting around

17 博弈论的局限 No unified solution to general conflict resolution Real-world conflicts are complex models can at best capture important aspects Players are (usually) considered rational determine what is best for them given that others are doing the same No unique prescription not clear what players should do But it can provide intuitions, suggestions and partial prescriptions best mathematical tool we currently have 17

18 什么是一个博弈? 博弈有下列要素 至少两个参与者 每个参与者的策略 ( 战略 ) 集合 博弈结果的优先关系 18

19 什么是一个博弈? 参与者 一般概念 个人, 公司, 国家, 协议实体 策略 (Strategy) 给定信息集下, 一个策略决定了在每一个时间点上参与者选择何种行动 是参与者行动计划的一个完整描述, 告诉参与者在每一种可预见的情况下选择什么行动 结果 (Outcome) 由每个参与者的策略组合确定 支付 (Payoff, 收益 ) 结果到效用的函数 优先关系 通过针对结果的效用 ( 收益 ) 函数来评价 19

20 博弈的分类 很多不同的分类方法 参与人是否合作 博弈的动态特性 博弈的信息等 非合作博弈 Non-Cooperative (Competitive) Games 博弈参与者之间没有明确的合作关系 合作博弈 又称正和博弈 Cooperative Games 博弈参与者之间存在明确的合作关系 研究人们达成合作时如何分配合作得到的收益, 即收益分配问题 静态博弈 动态博弈 重复或者演化博弈 20

21 Matrix Game (Normal form) Representation of a game Strategy set for Player 1 Player 1 Player 2 A B C Strategy set for Player 2 A (2, 2) (0, 0) (-2, -1) B (-5, 1) (3, 4) (3, -1) Payoff to Player 1 Simultaneous play 静态博弈 Payoff to Player 2 players analyze the game and write their strategy on a paper Combination of strategies determines payoff 21

22 More Formal Game Definition Normal form (strategic) game a finite set N of players a set strategies u i where s A j chosen by all players payoff function A i for each player (s) A N for each player j i N i N is the set of strategies A is the set of all possible outcomes s A is a set of strategies chosen by players defines an outcome u i : A 22

23 两人零和博弈 第一个被深入研究的博弈 参与者的利益完全对立 一方的收益就是另一方的损失 可以用一项来表示博弈矩阵 参与者 1 的收益 直观的求解思路 参与者最大化自己的收益 期望得到唯一解 23

24 Analyzing the Game Player 1 maximizes matrix entry, while player 2 minimizes Player 2 Player 1 Strictly dominated strategy (dominated by C) A B C D A B C D Strictly dominated strategy (dominated by B) 24

25 占优性 Dominance 如果选择 S 后的收益总比选择 T 后的收益更好, 称策略 S 对策略 T 严格占优, 称 T 为参与者在策略集上的严格劣策略 占优性原理 理性的参与者不会选择严格劣策略 思路 : 可以通过删除严格劣策略求解博弈 迭代删除 25

26 Solving the Game Iterated removal of strictly dominated strategies Player 2 L M R Player 1 T B Player 1 cannot remove any strategy (neither T or B dominates the other) Player 2 can remove strategy R (dominated by M) Player 1 can remove strategy T (dominated by B) Player 2 can remove strategy L (dominated by M) Solution: P 1 -> B, P 2 -> M payoff of 2 26

27 Solving the Game Removal of strictly dominates strategies does not always work Consider the game Player 2 A B D A Player 1 C D Neither player has dominated strategies Requires another solution concept 27

28 Analyzing the Game Player 2 Player 1 A B D A C D Outcome (C, B) seems stable saddle point of game 28

29 Saddle Points An outcome is a saddle point if it is both less than or equal to any value in its row and greater than or equal to any value in its column - 行中最小值 列中最大值 Saddle Point Principle Players should choose outcomes that are saddle points of the game Value of the game value of saddle point outcome if it exists 29

30 Why Play Saddle Points? Player 2 A B D A Player 1 C D If player 1 believes player 2 will play B player 1 should play best response to B (which is C) If player 2 believes player 1 will play C player 2 should play best response to C (which is B) 30

31 Why Play Saddle Points? Player 2 A B D A Player 1 C D Why should player 1 believe player 2 will play B? playing B guarantees player 2 loses at most v (which is 2) Why should player 2 believe player 1 will play C? playing C guarantees player 1 wins at least v (which is 2) Powerful arguments to play saddle point! 31

32 Solving the Game (min-max algorithm) Player 2 Player 1 A B C D A B C D choose maximum entry in each column choose the minimum among these this is the minimax value choose minimum entry in each row choose the maximum among these this is maximin value if minimax == maximin, then this is the saddle point of game 32

33 Multiple Saddle Points In general, game can have multiple saddle points Player 2 A B C D A Player 1 B C D Same payoff in every saddle point unique value of the game Strategies are interchangeable Example: strategies (A, B) and (C, C) are saddle points then (A, C) and (C, B) are also saddle points 33

34 Games With no Saddle Points Player 2 A B C Player 1 A B What should players do? resort to randomness to select strategies 34

35 Mixed Strategies Each player associates a probability distribution over its set of strategies players decide on which prob. distribution to use Payoffs are computed as expectations Player 1 1/3 2/3 C D A 4 0 B -5 3 Payoff to P1 when playing A = 1/3(4) + 2/3(0) = 4/3 Payoff to P1 when playing B = 1/3(-5) + 2/3(3) = 1/3 How should players choose prob. distribution? 35

36 Mixed Strategies Idea: use a prob. distribution that cannot be exploited by other player payoff should be equal independent of the choice of strategy of other player guarantees minimum gain (maximum loss) How should Player 2 play? Player 1 x C (1-x) D A 4 0 B -5 3 Payoff to P1 when playing A = x(4) + (1-x)(0) = 4x Payoff to P1 when playing B = x(-5) + (1-x)(3) = 3 8x 4x = 3 8x, thus x = 1/4 36

37 Mixed Strategies Player 2 mixed strategy 1/4 C, 3/4 D maximizes its loss independent of P1 choices Player 1 has same reasoning Player 2 C D x A 4 0 Player 1 (1-x) B -5 3 Payoff to P2 when playing C = x(-4) + (1-x)(5) = 5-9x Payoff to P2 when playing D = x(0) + (1-x)(-3) = x 5 9x = x, thus x = 2/3 Payoff to P2 = -1 37

38 极小极大定理 Minimax Theorem Every two-person zero-sum game has a solution in mixed (and sometimes pure) strategies solution payoff is the value of the game maximin = v = minimax v is unique multiple equilibrium in pure strategies possible but fully interchangeable Proved by John von Neumann in 1928! birth of game theory 38

39 Two-person Non-zero Sum Games Players are not strictly opposed payoff sum is non-zero Player 2 A B Player 1 A 3, 4 2, 0 B 5, 1-1, 2 Situations where interest is not directly opposed players could cooperate 39

40 What is the Solution? Ideas of zero-sum game: saddle points pure strategy equilibrium Player 1 Player 2 A B A 5, 4 2, 0 B 3, 1-1, 2 mixed strategies equilibrium Player 1 no pure strategy eq. Player 2 A B A 5, 0-1, 4 B 3, 2 2, 1 40

41 均衡 (equilibrium) 均衡 ( 博弈的解 ) 由博弈中 N 个参与者选择的最优策略所组成的一个策略组合 如 : 占优策略均衡 重复剔除严格劣策略均衡 纳什均衡 子博弈精练均衡等 存在性 唯一性 41

42 Multiple Solution Problem Games can have multiple equilibria not equivalent: payoff is different not interchangeable: playing an equilibrium strategy does not lead to equilibrium Player 1 Player 2 A B A 1, 4 1, 1 B 0, 1 2, 2 equilibria 42

43 The Good News: Nash s Theorem Every two person game has at least one equilibrium in either pure or mixed strategies Proved by Nash in 1950 using fixed point theorem 获得 1994 年诺贝尔经济学奖 ( 海萨尼, 泽尔腾 ) 在非合作博弈的均衡分析理论方面做出了开创贡献, 对博弈论和经济学产生了重大影响 Def: An outcome o* of a game is a NEP (Nash equilibrium point) if no player can unilaterally change its strategy and increase its payoff Cor: any saddle point is also a NEP 43

44 纳什均衡 一组给定对手行为前提下对各博弈方存在的最佳选择 只要其它参与者不变换策略选择, 任何 单个参与者不可能单方面通过变换策略 来提高收益 44

45 纳什均衡 与严格占优均衡区别 在纳什均衡下, 我 ( 你 ) 所做的是给定你 ( 我 ) 的选择我 ( 你 ) 所能做的最好的 严格占优均衡下, 我 ( 你 ) 所做的是不论你 ( 我 ) 的选择我 ( 你 ) 所能做的最好的 严格占优均衡必然是纳什均衡, 纳什均衡未必是严格占优均衡 45

46 信息 共同知识 (Common Knowledge) 我们说知识 M 是共同知识 每个参与者知道 M 每个参与者知道 每个参与者知道 M, 私有信息 在博弈中 ( 包括开始博弈前 ), 参与者 i 的私有信息是指他知道, 但不是所有参与者的共同知识的信息 46

47 村庄里的大屠杀 在一个偏僻的山里有 100 对夫妇 如果女人发现自己的丈夫对自己不忠, 就会毫不犹豫地将他杀死, 而且就在当天执行 某个女人发现某个男人不忠, 她不会告诉那个不忠男人的妻子 但是, 她会告诉其他人的妻子, 并且女人们会相互传递这一信息, 因此最后, 一个男人不忠, 除了其妻子不知道外, 其他女人都知道 47

48 村庄里的大屠杀 事实 : 村子里的这 100 对夫妇的男人都不忠, 但由于女人不会将她知道的事实告诉不忠男人的妻子, 每个女人都不知道自己的男人不忠 村子一直很稳定, 没有发生妻子杀死丈夫的行为 村子里有一个辈份很高的老太太, 德高望重, 每个人都向她汇报村里的情况, 她知道每个男人都不忠, 当然, 其他女人不知道她所知道的 一天, 这位老人对这 100 个女人说了一句很平常的话 : 你们的男人当中至少有一个是不忠的 于是村里发生了这样一件事情 : 前 99 天, 村里风平浪静, 但到了第 100 天, 村里发生了一场大屠杀, 所有的女人都杀死了她们的丈夫 48

49 村庄里的大屠杀 女人的策略 : 如果她的丈夫不忠的话, 她就杀死他 ; 如果没有证据证明她的丈夫不忠的话, 她便相信他, 不杀死他 在老太太作了宣布之后的第一天, 如果村里只有一个男人是不忠的话, 这个男人的妻子在老太太宣布之后就能知道 她会这样推理 : 如果其他男人不忠, 她应当事先知道, 既然不知道并且至少有一个男人不忠, 那么这个不忠的男人肯定就是她的丈夫 因此, 村里如果只有一个男人不忠的话, 老太太宣布之后, 当天这个男人就会被杀死 事实上这个村子里的 100 个男人不忠, 那么, 这样推理会继续到 99 天, 就是说, 前 99 天每个女人都没怀疑到自己的丈夫, 而当第 100 天的时候, 每个女人都确定地推理出她的丈夫不忠, 于是村子里便发生了一场大屠杀, 所有的男人都被他们的妻子杀死 49

50 信息 不完全信息博弈 自然首先行动, 而且他的行动至少对某一参与者来说是不可观察的 部分参与者不知道其他参与者的支付函数 在参与者开始计划自己的行动前, 部分参与者具有其他人不知道的私有信息 ( 初始私有信息 ) 50

51 博弈的均衡 完全信息 不完全信息 静态 动态 静态完全信息纳什均衡 代表人物 : 纳什 动态完全信息子博弈精炼纳什均衡 代表人物 : 泽尔腾 静态不完全信息博弈贝叶斯纳什均衡 代表人物 : 海萨尼 动态不完全信息博弈精炼贝叶斯纳什均衡 代表人物 : 泽尔腾克瑞普斯和威尔逊弗登伯格和泰勒尔 51

52 囚徒困境 The Prisoner s Dilemma 著名的博弈实例 1950 年提出 两名嫌疑犯因为共同犯罪被逮捕 隔离审讯, 可以选择承认罪行 ( confess ) 或者保持沉默 ( silent) Suspect 1 Suspect 2 S C S 2, 2 10, 1 C 1, 10 5, 5 payoff is years in jail (smaller is better) better outcome single NEP 52

53 Pareto Optimal Prisoner s dilemma: individual rationality Suspect 1 Suspect 2 S C S 2, 2 10, 1 C 1, 10 5, 5 Pareto Optimal Another type of solution: group rationality Pareto optimal Def: outcome o* is Pareto Optimal if no other outcome is better for all players 53

54 Game of Chicken Revisited 2 2 Game of Chicken (aka. Hawk-Dove Game) driver who swerves looses Driver 1 Driver 2 swerve stay swerve 0, 0-1, 5 stay 5, -1-10, -10 Drivers want to do opposite of one another Will prior communication help? 54

55 Example: Cournot Model of Duopoly Several firms produce exactly same product qi : quantity produced by firm i 1,, N Cost to firm i to produce quantity C i ( q i ) Market clearing price (price paid by consumers) P(Q) where Q i qi Revenue of firm i U i ( qi, Q) qip( Q) Ci ( qi ) q i How much should firm i produce? 55

56 Example: Cournot Model of Duopoly Consider two firms: i 1,2 Simple production cost C ( q ) cq i i i no fixed cost, only marginal cost with constant c Simple market (fixed demand a) P( Q) a Q where Q q 1 q 2 Revenue of firm i 1,2 U ( q, Q) q ( a Q) cq q ( a ( q q ) c) i i i i i 1 2 Firms choose quantities simultaneously Assume c < a 56

57 Example: Cournot Model of Duopoly Two player game: Firm 1 and Firm 2 Strategy space production quantity q i 0 since P( Q) 0 if Q a, q i a What is the NEP? To find NEP, firm 1 solves max q1( a ( q1 q2) c) 0 q1 a To find NEP, firm 2 solves max q2( a ( q1 q2) c) 0 q2 a value chosen by firm 2 value chosen by firm 1 57

58 Example: Cournot Model of Duopoly Solution to maximization problem b 1 first order condition is necessary and sufficient * a q2 ( q2) q1 2 c Best response functions best strategy for player 1, given choice for player 2 At NEP, strategies one another need to solve pair of equations q * 1 a q 2 * 2 c and using substitution and ( q * 1, q q * 2 * 2 b ) 2 a * a q1 ( q1) q2 2 c are best response to * q1 2 c 58

59 Example: Cournot Model of Duopoly NEP is given by * * a c q1 q2 3 Total amount produced at NEP: Price paid by consumers at NEP: Consider a monopoly (no firm 2, q 2 0 ) * Equilibrium is given by q ( a ) 2 1 c Q P( Q 1 Total amount produced: Q ( a c) 2 Price paid by consumers: a c P( Q) 2 Competition can be good! 2 3 ) ( a c) a 2c 3 less quantity produced higher price 59

60 Example: Cournot Model of Duopoly Graphical approach: best response functions Plot best response for firm 1 a q2 c b1 ( q2) 2 Plot best response for firm 2 a q1 c b2 ( q1) 2 q 2 a c ( a c) 2 b 1 ( q 2 ) b 2 ( q 1 ) NEP: strategies are mutual best responses all intersections are NEPs ( a c) 2 a c q 1 60

61 博弈树 (Extensive form) Sequential play players take turns in making choices previous choices can be available to players Game represented as a tree each non-leaf node represents a decision point for some player edges represent available choices 可以转换成博弈矩阵 (Normal form) plan of action must be chosen before hand 61

62 Game Trees Example L Player 1 Player 2 Player 2 R Payoff to Player 1 L R L R 3, 1 1, 2-2, 1 0, -1 Payoff to Player 2 Strategy set for Player 1: {L, R} Strategy for Player 2:, what to do when P1 plays L what to do when P1 plays R Strategy set for Player 2: {LL, LR, RL, RR} 62

63 More Formal Extensive Game Definition An extensive form game a finite set N of players a finite height game tree u i (s) where s is a leaf node of game tree payoff function for each player Game tree: set of nodes and edges each non-leaf node represents a decision point for some player edges represent available choices (possibly infinite) Perfect information 完美信息 i N all players have full knowledge of game history 63

64 Game Tree Example Microsoft and Mozilla are deciding on adopting new browser technology (.net or java) Microsoft moves first, then Mozilla makes its move Microsoft Mozilla.net java Mozilla.net java.net java 3, 1 1, 0 0, 0 2, 2 Non-zero sum game what are the NEP? 64

65 Converting to.net java Matrix Game.net java.net java 3, 1 1, 0 0, 0 2, 2 Microsoft.net,.net Mozilla.net, java java,.net java, java.net 3, 1 3, 1 1, 0 1, 0 java 0, 0 2, 2 0, 0 2, 2 Every game in extensive form can be converted into normal form exponential growth in number of strategies 65

66 NEP and Incredible.net java Threats.net java.net java.net,.net Mozilla.net, java java,.net 3, 1 1, 0 0, 0 2, 2 java, java Microsoft.net 3, 1 3, 1 1, 0 1, 0 java 0, 0 2, 2 0, 0 2, 2 Play java no matter what is not credible for Mozilla if Microsoft plays.net then.net is better for Mozilla than java NEP incredible threat 66

67 Solving the Game (backward induction) Starting from terminal nodes move up game tree making best choice.net java.net java.net java 3, 1 1, 0 0, 0 2, 2 Best strategy for Mozilla:.net, java (follow Microsoft) Equilibrium outcome.net java 3, 1 2, 2 Best strategy for Microsoft:.net Single NEP Microsoft ->.net, Mozilla ->.net, java 67

68 Backward Induction on Game Trees Kuhn s Thr: Backward induction always leads to saddle point (on games with perfect information) game value at equilibrium is unique (for zero-sum games) In general, multiple NEPs are possible after backward induction cases with no strict preference over payoffs Effective mechanism to remove bad NEP incredible threats 68

69 Leaders and Followers What happens if Mozilla moves first? Mozilla Microsoft.net java Microsoft.net java.net java 1, 3 0, 1 0, 0 2, 2 NEP after backward induction: Mozilla: java Microsoft:.net, java Outcome is better for Mozilla, worst for Microsoft incredible threat becomes credible! 1 st mover advantage but can also be a disadvantage 69

70 The Subgame Concept Def: a subgame is any subtree of the original game that also defines a proper game includes all descendents of non-leaf root node Microsoft Mozilla.net java Mozilla.net java.net java 3, 1 1, 0 0, 0 2, 2 3 subtrees full tree, left tree, right tree 70

71 Subgame Perfect Nash Equilibrium 子博弈精炼纳什均衡 Def: a NEP is subgame perfect if its restriction to every subgame is also a NEP of the subgame Thr: every extensive form game has at least one subgame perferct Nash equilibrium Kuhn s theorem, based on backward induction Set of NEP that survive backward induction in games with perfect information 71

72 Subgame Perfect Nash Equilibrium Mozilla.net Microsoft.net java N J java.net Mozilla java (N, NN) is not a NEP when restricted to the subgame starting at J (J, JJ) is not a NEP when restricted to the subgame starting at N MS 3, 1 1, 0 0, 0 2, 2 Mozilla NN NJ JN JJ N 3,1 3,1 1,0 1,0 J 0,0 2,2 0,0 2,2 (N, NJ) is a subgame perfect Nash equilibrium Subgame Perfect NEP Not subgame Perfect NEP 72

73 Outline Basic concepts of game theory Two-person Zero-sum Games Two-person Non-zero Sum Games Game Tree and Subgame Perfect Nash Equilibrium Dynamic Games of Complete Information Dynamic Game of Complete & Perfect Information Two-Stage Dynamic Game of Complete but Imperfect Information Repeated Games Static Games of Incomplete Information 73

74 Basic Theory: Backwards Induction Definition Dynamic Game: Game in which we have sequence of moves. Complete Information: Games in which the strategy space and player s payoff functions are common knowledge. Perfect Information: Each move in the game the players with the move knows the full history of the game thus far. Imperfect Information: At some move the player with the move doesn t know the history of the game. 74

75 Basic Theory: Backwards Induction Consider a game in which Player 1 chooses an action a1 from feasible set A1. Player 2 observes a1 and then chooses an action a2 from feasible set A2. Payoffs are u1(a1, a2) and u2(a1, a2). Example: Player 1 chooses between giving Player 2 $1000 or nothing. Player 2 observes player 1 s move, and choose to explode a grenade that will kill both players. Obviously, we can extend this game, by allowing more players, or allow players to move more than once. 75

76 Solution Technique: Backwards Induction When player 2 get the move, he needs to solve Assume that for each action a1, the above optimization problem has a unique solution, denoted by R 2 a 1 (which is the player 2 s best response.) Then, player 1 need to solve: Assume this optimization has a unique solution, the backwards-induction outcome of this game is ( a, R ( a )) * * max u ( a, R ( a )) a1 A * a 1 76

77 Extensive Form Representation 1 Playing this game [2,0] L 1 [1,1] L R 2 L" R 1 R" 2 2 [3,0] [1,0] In Round 3, player 1 chooses L. In Round 2, player 2 chooses L. In Round 1, player 1 chooses L. Thus the game ends in the first round. 77

78 Stackelberg Game Definition (Stackelberg Game) Two Players in this game: a leader and a follower. The leader moves first, choosing a strategy. Then the follower observes the leader s choice and picks a strategy. Under a Stackelberg game, the leader chooses strategy knowing that the follower will apply best response. Every Stackelberg game equilibrium is also Subgame Perfect Nash Equilibrium. 78

79 Stackelberg Model of Duopoly Example Consider two firms where: firm 1 chooses quantity q 1 0, firm 2 observes q 1, chooses quantity q 2 0, firm i profit function where P(Q)= a Q is the market clearing price and Q=q 1 +q 2, the aggregate quantity and c is a constant. 79

80 Stackelberg Duopoly and Backwards Induction firm 2 s solution is R2(q1):, where q 1 <a-c firm 1 s response: a q1 c max 1( q1, R2 ( q1 )) max q1 q1 0 q1 0 2 * a c * a c q1 R2( q1)

81 Comment on Stackelberg Duopoly Recall that Nash equilibrium in the Cournot game, each firm produces (a-c)/3. The aggregate quantity of the Stackelberg game, 3(a-c)/4, is greater than the Nash equilibrium of the Cournot game 2(a-c)/3. The market-clearing price is lower in the Stackelberg game. Firm 1 s profit in the Stackelberg game is higher than its profit in the Cournot game. Firm 1 s better off in the Stackelberg game implies Firm 2 is worse off. (Leader s advantage). If the choice is price, then Firm 2 has follower s advantage. 81

82 讨价还价 Sequential Bargaining: 3-period, 1 unit of resource 第一阶段, 参与者 1 提出自己拿走 s1 的份额, 剩余 1-s1 留给参与者 2 参与者 2 可以接受 ( 这时博弈结束, 参与者 1 获得 s1, 参与者 2 获得 1-s1), 或者拒绝 ( 这时博弈继续 ) 第二阶段, 参与者 2 提出给参与者 1 s2 的份额, 自己拿走 1-s2 参与者 1 可以接受 ( 这时博弈结束, 参与者 1 获得 s2, 参与者 2 获得 1-s2), 或者拒绝 ( 这时博弈继续 ) 第三阶段, 参与者 1 获得 s, 参与者 2 获得 1-s, 0 < s < 1 这里还存在贴现因子 δ, 0 <δ< 1 82

83 Solution Consider player 2 s optimal offer if the 2nd period is reached Player 1 is facing a choice, choose s2 or receive Player 1 will accept the offer iff s2 Player 2 s 2nd-period decision: receiving 1 - s(by offer s2 = s to player 1), or receiving (1 s) in the third period. Since 1 - s> (1 s) player 2 s optimal 2nd-round * choice is = s and player 1 will accept s 2 83

84 Solution: continue Player 1 is facing a choice in the 1st-period Player 2 will only accept the offer in the 1stperiod iff 1 - s1, or s1 1 - Player 1 s 1st-period decision: receiving 1 - = 1 - (making that bid), or receiving Since 1 - period offer is >, so player 1 s optimal 1st- The Solution of the game should end in the 1stperiod with where 84

85 Extension to infinite rounds 如果双方循环无限次会怎么样? 如果博弈到达第三阶段, 则在此轮到参与者 1 出价, 和第一阶段情况相同 假设 S H 是参与者 1 在整个博弈中能获得的最大收益 85

86 Extension to infinite rounds: continue Using SH as the 3rd period payoff to player 1. Player 1 s first-period payoff is f (SH) where 2 f (s) = 1 s But SH is also the highest possible 1st-period payoff, so f (SH) = SH The only value of s that satisfy f (s) = s is Solution is, in the first round, player 1 offers to player 2, who will accept. 86

87 纳什讨价还价 (Nash Bargaining) John F. Nash, Jr. The Bargaining Problem. Econometrica, Vol. 18, No. 2 (Apr., 1950), pp 两人讨价还价场景 : 两人合作的总收益大于各自单干的收益之和 两人需要一个规则来分配合作后获得的 蛋糕, 每人都以自己的收益最大为目标, 因此存在一个 讨价还价 的过程 如果两人达成协议, 则按照协议分配收益 ; 否则, 只能单干, 获取较少收益 87

88 纳什讨价还价 (Nash Bargaining) 公理 1: 个体理性 合作后每个人的收益都不少于单干时的收益 φ 1 F, v v 1 φ 2 F, v v 2 公理 2:Pareto 强有效性 纳什讨价还价解必定位于 Pareto 边界上 88

89 纳什讨价还价 (Nash Bargaining) 公理 3: 对称性 参与人的收益配置互换后也是可行的 地位相同的人待遇也相同 如果 x 1, x 2 F, 必有 (x 2, x 1 ) F 如果 v 1 = v 2, 那么 φ 1 F, v = φ 2 F, v 公理 4: 等价盈利描述的不变性 一个讨价还价问题通过仿射变换变为另一个讨价还价问题, 那么原讨价还价解通过仿射变换后也成为新讨价还价问题的解 公理 5: 无关选择的独立性 移除讨价还价解之外的点不会影响讨价还价解的求得 89

90 纳什讨价还价 (Nash Bargaining) 定理 1: 对于两人讨价还价问题 F, v, 存在满足公理 1-5 的唯一讨价还价解 : φ F, v = arg max x F,x v x 1 v 1 )(x 2 v 2 x 2 (x 1 v 1 )(x 2 v 2 ) = C F (v 1, v 2 x 1 90

91 纳什讨价还价 (Nash Bargaining) 现实生活中, 平均主义未必最合理 最公正 最切合实际 定理 2: 对于两人讨价还价问题 F, v, 配置 x 1, x 2 是讨价还价解, 当且仅当, 存在 λ 1 > 0, λ 2 > 0, 使得 : λ 1 x 1 v 1 = λ 2 (x 2 v 2 ) λ 1 x 1 + λ 2 x 2 = max y F (λ 1y 1 + λ 2 y 2 ) 91

92 Outline Basic concepts of game theory Two-person Zero-sum Games Two-person Non-zero Sum Games Game Tree and Subgame Perfect Nash Equilibrium Dynamic Games of Complete Information Dynamic Game of Complete & Perfect Information Two-Stage Dynamic Game of Complete but Imperfect Information Repeated Games Static Games of Incomplete Information 92

93 Framework We allow simultaneous moves (which corresponds to imperfect information ) with each stage. Consider the following two-stage game: Player 1 and 2 simultaneously choose action respectively. and Player 3 and 4 observe the outcome of the 1st stage (a1, a2), then simultaneously choose action and respectively. Payoffs are ui (a1, a2, a3, a4) for i = 1, 2, 3, 4. Various of the above game (1) players 3 and 4 are player 1 and 2 (2) player 2 or player 4 is missing 93

94 Framework: continue For each outcome of (a1, a2), the 2nd stage game has a unique Nash equilibrium, denoted by (assumption of NE). Player 1 and 2 anticipate, then both players simultaneously take action with the payoff of for i = 1, 2. Suppose is the unique Nash equilibrium, then is the subgame-perfect outcome. 94

95 Tariffs and Imperfect Competition Consider two countries, denoted by i=1,2 each setting a tariff rate t i per unit of product A firm produces output, both for home consumption and export Consumer can buy from a local firm or foreign firm The market clearing price for country i is P(Qi)=a-Qi, where Qi is the quantity on the market in country i A firm in i produces hi(ei) units for local (foreign) market,i.e., Qi=hi+ej The production cost of firm i is Ci(hi,ei)=c(hi+ei) and it pays tj*ei to country j 95

96 Tariffs and Imperfect Competition Game First, the government simultaneously choose tariff rates t1 and t2 Second, the firms observe the tariff rates, decides (h1,e1) and (h2,e2) simultaneously Third, payoffs for both firms and governments: (1)Profit for firm i: (2)Welfare for government i: 96

97 价格 消费者心中的价格曲线 实际的价格曲线 消费者剩余 ( 曲线间面积 ) 产量 97

98 Tariffs and Imperfect Competition Game:2nd stage Suppose the governments have chosen t1 and t2 * * * * If ( h1, e1, h2, e2) is a NE for firm 1 and 2,firm i * * needs to solve max ( t, t, h, e, h, e ) h, e 0 i i j i i j j After re-arrangement, it becomes two separable optimizations: i i 98

99 Tariffs and Imperfect Competition Game:2nd stage Assuming we have: Solving, we have 99

100 Tariffs and Imperfect Competition Game:1st stage In the first stage, government i payoff is: If Since is a function of is a NE, each government solves: 100

101 Tariffs and Imperfect Competition Game:1st stage Solving the optimization, we have t * i a c 3, for i 1,2. which is a dominant strategy for each government Substitute,we have 101

102 Tariffs and Imperfect Competition Game In the subgame-perfect outcome, the aggregate quantity on each market is 5(a-c)/9 But if two governments cooperate, they seek socially optimal point and they solve the following optimization problem: The solution is (no tariff) and the aggregate quantity is 2(a-c)/3 Therefore, for the above game, we have a unique NE, and it is socially inefficient 102

103 世界贸易组织 (WTO) 世贸组织是一个独立于联合国的永久性国际组织 1995 年 1 月 1 日正式开始运作, 负责管理世界经济和贸易秩序, 总部设在瑞士日内瓦莱蒙湖畔 世贸组织的主要职能 组织实施各项贸易协定 为各成员提供多边贸易谈判场所, 并为多边谈判结果提供框架 解决成员间发生的贸易争端 对各成员的贸易政策与法规进行定期审议 中国 2001 正式加入 WTO 103

104 Outline Basic concepts of game theory Two-person Zero-sum Games Two-person Non-zero Sum Games Game Tree and Subgame Perfect Nash Equilibrium Dynamic Games of Complete Information Dynamic Game of Complete & Perfect Information Two-Stage Dynamic Game of Complete but Imperfect Information Repeated Games Static Games of Incomplete Information 104

105 Theory: Two-stage Repeated Game 囚徒困境 重复两次囚徒困境 S C S 2, 2 10, 1 C 1, 10 5, 5 第二次博弈开始前可以观察到第一次博弈的结果 整个博弈的收益是两阶段收益之和 倒推法分析 : 在第二阶段时, 坦白是占优策略 105

106 Theory: Two-stage Repeated Game 囚徒困境 The players first-stage game amounts to oneshot game: S C S 7, 7 15, 6 C 6, 15 10, 10 This game also has a unique NE:(C, C) This unique subgame-perfect outcome of the 2- stage game is (C, C) in the first stage, (C, C) in the 2nd stage 106

107 Definition and Proposition Definition Given a stage game G, let G(T) denote the finitely repeated game in which G is played T times, with the outcomes of all preceding plays observed before the next play begins. The payoffs for G(T) are simply the sum of the payoffs from the T stage games Proposition If the stage game G has a unique NE then, for any finite T, the repeated game G(T) has a unique subgame-perfect outcome: the NE of G is played in every stage 107

108 Another look of the 2-stage repeated game Consider the following game will be played twice: The stage game has two pure-strategy NE: (L1, L2),(R1, R2). 108

109 Another look of the 2-stage repeated game Since more than one NE, players anticipate the different first-stage outcomes will be followed by different stage-game equilibrium in the 2nd stage Suppose players anticipate (R1,R2) will be the 2nd-stage outcome if the 1st-stage outcome is (M1,M2), but (L1, L2) will be the 2nd-stage outcome if any of the eight other first-stage outcomes occurs 109

110 Another look of the 2-stage repeated game Players 1st-stage action amounts to the oneshot game: There are three pure-strategy NE:(L1, L2), (M1,M2), (R1,R2) 110

111 Another look of the 2-stage repeated game The NE (L1, L2) corresponds to the subgameperfect outcome ((L1, L2), (L1, L2)) (concatenate 2 NE) The NE (R1,R2) corresponds to the subgameperfect outcome ((R1,R2), (L1, L2)) (concatenate 2 NE) The NE (M1,M2) corresponds to the subgame-perfect outcome ((M1,M2), (R1,R2)) 111

112 Another look of the 2-stage repeated game Observation If G = {A1,...,An; u1,..., un} is a static game of complete information with multiple NE, then there may be subgame-perfect outcomes of the repeated game G(T) in which for any t < T, the outcome in stage t is not a NE of G This implies that credible promises about the future behavior can influence current behavior Stronger Result In infinitely repeated games: even if the stage game has a unique NE, there may be subgame-perfect outcomes of the infinitely repeated games in which no stage s outcome is a NE of G 112

113 Theory of Infinitely Repeated Game 完全信息静态博弈 G, 重复无限次, 在当前阶段开始前, 所有之前阶段的结果均为已知 收益定义为所有阶段收益之和, 无法计算, 为了克服该问题, 引入现值的概念 定义 ( 现值 Present Value) Given the discount factor, the present value of the infinite sequence of payoffs is: 113

114 Example an Infinitely Repeated Game Consider the following stage game G: NE of G is (L1, L2), but it is much better to play (R1,R2) Player i s strategy is: Play Ri in the 1st stage. In the t-th stage, if the outcome of all t-1 stages has been (R1,R2), then play Ri ; otherwise, play Li This is an example of trigger strategy, player i cooperates until someone fails to cooperate, which triggers a switch to non-cooperation forever after Is (R1,R2) the NE of this infinitely repeated game? 114

115 Proof for Nash Equilibrium when 1/ 4 Assume player i has adopted the trigger strategy, and show that when is close enough to one, player j s best response is to adopt the same trigger strategy Since player i will play Li forever once the stage outcome differs from (R1,R2), player j s best response is to play Lj forever once there is a switch For strategy before the switch, playing Lj will yield a present value 2 5 *1 * Playing Rj will yield a present value of V where V 4 V, or V 4/(1 ) Player j will choose Rj This is only true if Trigger strategy is the NE 1/ 4 115

116 More Definitions Definition (Infinitely Repeated Game) Given a stage game G, let denote the infinitely repeated game in which G is repeated forever and the players share the discount factor. For each t, the outcomes of the t - 1 preceding plays of the stage game are observed before the t-th stage begins. Each player s payoff in is the present value of the player s payoffs from the infinite sequence of stage games 116

117 More Definitions Definition (Strategy) In the finitely repeated game G(T) or the infinitely repeated game a player s strategy specifies the action the player will take in each stage, for each possible history of play through the previous stage Example, previous G has four possible 1st-stage outcomes:(l1, L2), (L1,R2), (R1, L2), (R1,R2) The player s strategy consists of five instruction (v, w, x, y, z) where v is the 1st-stage action, the rest are the 2nd-stage actions to be taken following the 4 possible 1st-stage outcomes (1) (b, c, c, c, c) means play b in the 1st-stage, play c no matter what happens in the first. (2) (b, c, c, c, b) means, play b in the 1st-stage, play c in the 2nd-stage unless the 1st-stage outcome was (R1,R2), then play b 117

118 Definition on Subgame and Subgame-perfect NE Definition (Subgame) In the finitely repeated game G(T), a subgame beginning at stage t + 1 is the repeated game in which G plays T - t times, or G(T - t). There are many subgames that begin at stage t + 1, one for each of the possible histories of play through stage t. In the infinitely repeated game each subgame beginning at stage t + 1 is identical to the original game There are as many subgames beginning at stage t +1 of as there are possible histories of play through t Definition (Subgame-perfect) A NE is subgame-perfect if the players strategies constitute a NE in every subgame 118

119 The trigger-strategy is subgame-perfect NE We must show that the trigger strategies constitute a NE on every subgame of the infinitely repeated game Note that every subgame of an infinitely repeated game is identical to the game as a whole These subgames can be grouped into two classes: (i) subgames in which all the outcomes of earlier stages are (R1,R2), (ii) subgames in which the outcome of at least one earlier stage differs from (R1,R2) For (i), adopting the trigger strategy, which was shown as a NE of the game For (ii), players repeat the stage-game equilibrium (L1,L2), which is also a NE of the game 119

120 Definitions Definition (Feasible Payoff) The payoff (x1,..., xn) is feasible in the stage game G if there is a convex combination of the purestrategy payoffs of G Definition (Average Payoff) Given the discount factor, the average payoff of the infinite sequence of payoffs is The last game has a present value of 4/(1 ) but an average payoff of 4 120

121 Friedman s Theorem Friedman s Theorem (or Folk s theorem) Let G be a finite, static game of complete information. Let (e1,..., en) denote the payoffs from a NE of G, and let (x1,..., xn) denote any other feasible payoffs from G. if xi e, i i and if is sufficiently close to one, then there exits a subgame-perfect Nash equilibrium of the infinitely repeated game G(, ) that achieves (x1,..., xn) as the average payoff 在无限次重复博弈中, 如果参与人有足够的耐心 ( 即贴现因子足够大 ), 那么任何满足个人理性的可行的支付向量都可以通过一个特定的子博弈精炼均衡得到 121

122 Folk s theorem Illustration Folk s Theorem Illustration (0,5) Payoff of player 2 (4,4) (1,1) (5,0) Payoff of player 1 122

123 Outline Basic concepts of game theory Two-person Zero-sum Games Two-person Non-zero Sum Games Game Tree and Subgame Perfect Nash Equilibrium Dynamic Games of Complete Information Dynamic Game of Complete & Perfect Information Two-Stage Dynamic Game of Complete but Imperfect Information Repeated Games Static Games of Incomplete Information 123

124 An Example: Cournot Competition under Asymmetric Information Consider a Cournot duopoly model with inverse demand given by P(Q) = a Q where Q = q1 + q2 is the aggregate quantity Firm 1 s cost function is C1(q1) = cq1 Firm 2 s cost function is C2(q2) = c H q2 with probability θ and C2(q2) = c L q2 with (1 θ) where c L < c H Information is asymmetric: firm 2 knows its cost function and firm 1 s, but firm 1 knows its cost function and only that firm 2 s marginal cost c H with θ and c L with (1 θ) This is a game with incomplete and asymmetric information 124

125 Cournot game with incomplete information Let and be firm 2 s quantity choices, be firm 1 s single quantity choice * If firm 2 s cost is high, it will choose and to solve Similarly, if cost is low, will solve Firm 1 chooses to solve 125

126 Cournot game with incomplete information Solving these optimization problems we have For Cournot game with complete information: Note that under the Counot game with incomplete information: WHY? Because firm 2 not only tailors its quantity to its cost, but also anticipate the response by firm 1 126

127 Definition Definition (Bayesian Nash Equilibrium) In the static Bayesian game G = {A1,...,An; T1,..., Tn; p1,..., pn; u1,..., un}. The strategies are a (pure-strategy) Bayesian Nash equilibrium if for each player i and for each i s types ti in Ti, solves: 127

128 海萨尼转换 海萨尼转换把不完全信息博弈转换成不完美信息动态博弈 1. 引进虚拟自然博弈方, 可称为博弈方 0, 其作用是在博弈方选择 之前, 为每个实际博弈方按随机方式或者说抽取他们的类型, 构 成向量 t 同时从各自的行为空间中选择行动方案 a,, a 4. 各博弈方得益 u ( t,, t ), 其中 t 1 i n T, i 部分 ) 博弈方知道其他博弈方的类型 u ( a,, a, t ), i i i n i i 1,, n 2. 博弈方 0 让每个实际博弈方知道自己的类型, 但不让 ( 全部或 3. 在前述基础上, 在进行原来的静态博弈, 即各个实际博弈方 1 1 n 1,, n

129 Example: Consider the following game: Two NE under pure strategy, (Opera, Opera), (FG, FG). What is the mixed strategy that has the NE? 129

130 Example: Let q (r ) be the probability that Pat (Chris) will choose Opera Chris s expected payoff in choosing Opera is q 2 + (1 q) 0 = 2q, and the expected payoff in choosing FG is q 0 + (1 q) 1 = 1 q So Chris will choose opera iff q > 1/3, will choose FG iff q < 1/3 If q = 1/3, any value of r is the best response by Chris 130

131 Example: Pat s expected payoff in choosing Opera is r 1 + (1 r ) 0 = r, and the expected payoff in choosing FG is r 0 + (1 r ) 2 = 2(1 r ) So Pat will choose opera iff r > 2/3, will choose FG iff r < 2/3 If r = 2/3, any value of q is the best response by Pat Then (q, 1 q) = (1/3, 2/3) for Pat and (r, 1 r ) = (2/3, 1/3) for Chris are the mixed strategy NE 131

132 Example: Consider the following static game with incomplete information: where tc (tp) is privately known by Chris (Pat) only. Both tc and tp are independent and uniformly distributed in [0, X] 132

133 Example: The normal form What is the pure-strategy Bayesian Nash equilibrium of this game? 133

134 Solution We ll construct a pure-strategy BNE in which Chris chooses opera if tc > c and chooses FG otherwise, while Pat chooses FG if tp > p and chooses opera otherwise In such an equilibrium, Chris chooses opera with probability 1 c while Pat chooses FG x with probability 1 p x 134

135 Solution: continue Note that when the incomplete information disappears (i.e.,as x-> 0), the BNE should approach the mixed-strategy NE, or 1 c x and 1 p will approach 2/3 as x approaches x zero For a given value of x, we will determine values of c and p such that these strategies are a BNE 135

136 Solution: continue Given Pat s strategy, Chris s expected payoff of opera & FG: x Thus, Chris chooses opera iff tc 3 p c 136

137 Solution: continue Given Chris s strategy, Pat s expected payoff of opera & FG: x Thus, Pat chooses FG iff tp 3 c p 137

138 Solution: continue Equating tc and tp, we have two equations: Solving the quadratic equation shows that: Both approach 2/3 as x approaches zero 138

139 Solution: continue Thus, the incomplete information disappears, the player s behavior in this pure-strategy BNE of the incomplete-information game approaches the mixed-strategy NE of the game with complete information 海萨尼证明, 完全信息情况下的混合策略均衡可以理解为不完全信息下纯策略均衡的极限 混合策略纳什均衡的本质特征不在于参与人随机地选择行动, 而在于参与人 i 不能确定参与人 j 将选择什么纯策略, 也就是说参与人对其他参与人的获益不完全确定 139

140 Outline Basic concepts of game theory Two-person Zero-sum Games Two-person Non-zero Sum Games Game Tree and Subgame Perfect Nash Equilibrium Dynamic Games of Complete Information Dynamic Game of Complete & Perfect Information Two-Stage Dynamic Game of Complete but Imperfect Information Repeated Games Static Games of Incomplete Information 140

141 Cooperative/coalitional Game theory 141

142 Cooperative/Coalitional Games Introduction Preliminaries Concepts and examples Coalition/Characteristic Function/Imputation A solution concept: core When the core is empty/existed? How to deal with empty/multi-core?-drawbacks Alternative Solutions Stable sets of Imputations Shapley values The nucleolus 142

143 Introduction Under cooperative games, players can coordinate their strategies and share the payoff Particularly, sets of players, called coalitions, can make binding agreements about joint strategies pool their individual agreements and redistribute the total payoff in a specified way ( Cooperative game theory is the standard name (distinguishing it from non-cooperative game theory, which is what we have studied so far). However this is somewhat of a misnomer because agents still pursue their own interests. Hence some people prefer coalitional game theory. ) 143

144 Introduction Francis Ysidro Edgeworth ( ) Mathematical Psychics 通过联盟博弈描述了参与人数目有限的交换经济模型 ( 现在被称为市场博弈 ) 144

145 交换的埃奇沃思盒状图 Y X B O B Y A C D E F Y B 交易的一般均衡是指当社会生产状况既定, 收入分配状况既定条件下, 通过要素所有者之间的交易使得交易者达到效用最大化的均衡状况 用 埃奇沃思盒状图 分析 O A X A X MRS X,YA = MRS B X,Y 时, 交换停止, 实现均衡交换契约线 : 交换双方的无差异曲线相切点的轨迹 假定 : 社会上只有两个消费者 A 和 B; 只有两种商品, 数量分别为 X 和 Y 145

146 Introduction Some families of coalitional games: Market games - introduced in Shapley (1959) Cost allocation games Lucas(1981) young (1985) Airport games Littlechild and Owen(1974) Minimum cost spanning tree games Cranot and Huberman (1984), Megiddo(1978) and others 146

147 Introduction Robert Aumann 与 Thomas Schelling 分享了 2005 年诺贝尔经济学奖 合作和非合作方法不应当被看作在分析不同类型的博弈, 相反, 它们是看待同一个博弈的不同方式 147

148 Introduction-Aumann 非合作博弈关心的是策略, 它研究的是参与人在博弈中如何做出决策 合作博弈研究我们期望得到什么结果 在合作方法中我们观察得益空间, 而不考虑得到这些结果的具体细节 相比较而言, 非合作博弈是一种微观类型的理论, 它涉及准确地描述发生了什么 在合作博弈中我们关心的是参与人可行的结果, 而不管是否符合理性 例如, 在囚徒困境中我们也关心合作博弈的结果, 这可以通过两囚犯之间签订有约束力的合约, 也就是承诺, 来实现 因此我们考察联盟如何形成, 哪些联盟可以形成, 以及形成了的联盟如何分配他们的得益 总结一下, 合作博弈从宏观的角度研究博弈, 关注可以用有约束力的承诺来得到可行的结果 148

149 Introduction 存在有约束力的合作协议的博弈就是合作博弈, 反之就是非合作博弈 双寡头 Cournot 博弈 - 非合作博弈 石油输出国组织 OPEC- 合作博弈 合作博弈强调集体理性, 公平和效率 非合作博弈强调个体理性 149

150 Introduction 面对博弈, 往往首先考虑合作, 合作无法达成, 则进行非合作博弈 合作的三种情况 事先可以达成有约束力的承诺, 直接使用合作博弈方法 事先无法达成有约束力的承诺, 使用能实现合作结果的非合作方法, 如讨价还价博弈 (Nash Bargaining) 无限次重复博弈, 如无限次囚徒困境, 仍然有可能达成合作解 150

151 Introduction- 实例 三个城市 (1,2,3) 计划修建城市用水系统, 利用公共的水库资源 (Y), 城市之间和城市与水库之间的管道铺设成本如下 Y 简单计算, 从水库到城市 1, 然后再到城市 2 和 3, 成本最小为 =45 问题 : 如何在三个城市分摊成本? 151

152 Preliminaries Concepts and examples A coalition is simply a subset of the set of players which forms in order to coordinate strategies and to agree on how the total payoff is to be divided among the members Let P be the set of players and there are N players in the system A coalition is denoted by an uppercase script letters: S, T, U, etc Given a coalition S P,the counter-coalition to S is C S P S { p P : p S} 152

153 example strategy (1,1,1) (1,1,2) (1,2,1) (1,2,2) (2,1,1) (2,1,2) (2,2,1) (2,2,2) payoff vectors (-2,1,2) (1,1,-1) (0,-1,2) (-1,2,0) (1,-1,1) (0,0,1) (1,0,0) (1,2,-2) Table1: Consider a 3 player game In this game, P ={P1,P2,P3} There are eight coalitions: 3 one-player coalitions: {P1}, {P2}, {P3} 3 two-player coalitions: {P1,P2}, {P1,P3}, {P2,P3} Grand coalition: P itself and the empty coalition: Φ In general, in a game with N players, there are 2 N coalitions 153

154 Characteristic Function One simple way to view about cooperative game is a competition (non-cooperative) between two players : C coalition S and the counter coalition S Consider an N player game P { p1,.., p N } c The system has an non-empty coalition S Pand S We have a bi-matrix with rows (columns) correspond C to the pure joint strategies of players in S ( S ). An entry in the bi-matrix is a pair of number, with the first (second) being the sum of the payoffs to players C in S ( S ) 154

155 Characteristic Function Consider a coalition S={P 1, P 3 },then S c ={P 2 } Coalition S has four pure joint strategies: {(1, 1), (1, 2), (2, 1), (2, 2)}. For S c, the strategies are 1 and 2. The bi-matrix is: 1 2 (1,1) (0,1) (2,-1) (1,2) (0,1) (-1,2) (2,1) (2,-1) (1,0) (2,2) (1,0) (-1,2) The maximum value for the coalition is called the characteristic function of S and it is denoted as v(s). In other words, members of S are guaranteed to gain a total payoff of at least v(s) 155

156 example Let us consider the previous game. For S, pure joint strategy (1,2) is dominated by (1,1), pure joint strategy (2,2) is dominated by (2,1). We have 1 2 (1,1) (0,1) (2,-1) (2,1) (2,-1) (1,0) We solve the above non-cooperative game, we have c ( S) 4 / 3 and ( S ) 1/ 3 Similarly, we have ({ p, p }) 1, ({ p }) 0, ({ p, p }) 3/ 4, ({ p }) 1/ Finally, by definition, the characteristic function of empty coalition is ( ) 0 156

157 example 通过分析特征函数, 我们可以推断联盟可能的形成过程 因为 P1 自己玩的收益比 P2 和 P3 自己玩的收益大, 因此 P2 和 P3 将尽量想办法和 P1 形成联盟 作为交换,P1 将要求更多的划分联盟的收益, 至少超过他自己玩时的 1/4 但是另外一方面, 如果 P1 要的太多,P2 和 P3 可能形成联盟, 排除 P1, 从而可以获得 3/4 157

158 The following definition states that, in union, there is strength Definition ( superadditivity ): Let S and T be disjoint coalitions, then ( S T) ( S) ( T) Using the previous example, we have ({ p, p }) 4 / 3 ({ p }) ({ p }) 1/ 4 0 1/ Corollary If S,..., 1 Sk are pairwise disjoint coalitions, then k k i 1S i Si i 1 ( ) ( ) 158

159 characteristic function form Definition A game in superadditivity characteristic function form consists of a set P { p1,.., p N } of players, together with a function, defined for all subsets of P, such that ( ) 0, and such that the superadditivity holds, that is: ( S T) ( S) ( T), whenever S and T are disjoint coalitions of the players 这里增加超可加属性隐含大联盟可能形成 159

160 continue Definition An N person game in characteristic function form is said to be inessential if ( P) ({ pi}). In other words, in it is an inessential game, there is no point to form a coalition Theorem Let S be any coalition of an inessential game, then N i 1 ( S) ({ p}). p S 160

161 Imputation Suppose a coalition forms in an N person game. We want to study the final distribution of the payoffs This is important because players want to know how much they gain if they form a coalition The amount going to the players form an N tuple x of numbers The N tuple vector x must satisfy two conditions: individual rationality( 个体理性 ) and collective rationality( 集体理性 ) for coalition to occur An N tuple of payments to the players which satisfies both these conditions is call an imputation 161

162 Definition Let be an N-person game in characteristic function form with players P { p1,.., p N }. An N tuple x of real numbers is said to be an imputation if both the following conditions hold (Individual Rationality) For all players, (Collective Rationality) We have x 1 i ( P) i Remark: Individual rationality is reasonable. If then no coalition given only the amount of would ever form and p i p i would do better going on his own ({ p}) 这里的集体理性不同于经济学中的概念, 指的是有效性 N p i x i x i i x i ({ p}) i 162

163 example Consider the game in Table 1, any 3-tuple x which satisfies the conditions: x1 x2 x3 1; x1 1/ 4; x2 1/ 3; x3 0. is a valid imputation It is easy to see that there are infinite many 3-tuples which satisfy these conditions, e.g., (1/3, 1/3, 1/3) (1/4, 3/8, 3/8) (1, 0, 0) 163

164 Imputation Theorem Let If If Remark be an N person game in characteristic function form. is inessential, then it has only one imputation, namely, x p1 p N ( ({ }),..., ({ })). is essential, then it has infinitely many imputations For an essential game, the issue is to find out which imputations deserve to be called solutions For the game in Table 1, none of the three imputations listed earlier seems likely to occur Imputation (1/4, 3/8, 3/8), it is unstable because P1 and P2 could form a coalition and gain a total payoff of at least 1 164

165 Imputation Dominance of Imputations : Some imputations are more "preferable" Definition Let be a game in characteristic function form, let S be a coalition, and let x, y be imputations. We say that x dominates y through coalition S, or x > s y, if the following conditions hold: xi yi for all p i S x ( S ) p S i i Remark: the second condition of the definition says that x is feasible, that the players in S attain enough payoff so that x i can be paid to p i S. 165

166 example Consider the game in Table 1: (a) (1/3,1/3,1/3) dominates (1,0,0) through coalition { p2, p3} since ({ p, p }) 3/ 4. (b) (1/4,3/8,3/8) dominates (1/3,1/3,1/3) through { p2, p3}. (c) (1/2,1/2,0) dominates (1/3,1/3,1/3) through { p1, p2} since ({ p1, p2}) 1. Observation: 2 3 An imputation which is dominated through some coalition would never become permanently established and there is a tendency for this coalition to break up and be replaced by one which gives its members a larger share- 被占优的配置不稳定 166

167 A solution concept: core 核 Definition Let be a game in characteristic form. The core of consists of all imputations which are not dominated by any other imputations through any coalition If an imputation x is in the core, there is no group of players which has a reason to form a coalition and replace x Therefore, the core is the solution concept of N person cooperative games. As we will soon seen, this solution concept is ok as long as the core is not empty 167

168 How to determine whether x is in the core? Theorem Let v be a game in characteristic function form with N players, and x be an imputation. Then x is in the core of if and only if for every coalition S. Corollary Let be a game in characteristic function form with N players and x be an N tuple of numbers. Then x is an imputation in the core if and only if the following two conditions hold: N i 1 x i ( P). p S for every coalition S. p S i x i ( S), i x i ( S), 168

169 example A four-person game is given in characteristic function form as follows: ( P) 2, ( ) 0, ({ p }) 1, ({ p }) 0, ({ p }) 1, ({ p }) 0, ({ p, p }) 0, ({ p, p }) 1, ({ p, p }) 1, ({ p, p }) 0, ({ p, p }) 1, ({ p, p }) 0, ({ p, p, p }) 0, ({ p, p, p }) 2, ({ p, p, p }) 0, ({ p, p, p }) Verify that is a characteristic function. Is the core of this game nonempty? 博弈是超可加的是核非空的必要条件 169

170 continue To verify superadditivity, is a characteristic function, we have to check that holds whenever and are disjoint coalitions This is easily check, for example By the previous corollary, if both the following hold: S ( S T) ( S) ( T), T ({ p1, p2, p4}) ({ p1}) ({ p2, p4}) ( x, x, x, x ) is in the core if and only x x x x ({ p, p, p, p }) 2 i p S x i ( S) It is easy to check, for example (1,0,0,1) and (0,1,0,1) satisfy these conditions. Thus the core is not empty 170

171 example Let us find the core of the game in Table 1. By the corollary, (x1, x2, x3) is an imputation in the core iff: x x x 1 (1) x x x x x x / 4, (2) 1/ 3, (3) 0, (4) x 1 2 x 1 3 x 2 3 1, (5) 4 / 3, (6) 3 / 4, (7) Analysis: From Eq. (1),(4) and (5), we have x3 = 0, x1 + x2 = 1. From Eq. (6)-(7), we have x Adding these, we 1 4 / 3, x2 3/ 4. have x This is a contradiction. So the core of 1 x2 25 /12 1. this game is empty 171

172 continue Another 3-player game G whose characteristic function is given by ({ p }) 1/ 2, ({ p }) 0, ({ p }) 1/ 2, ({ p, p }) 1/ 4, ({ p, p }) 0, ({ p, p }) 1/ 2, ({ p, p, p }) Note that (a) superadditivity holds for this example 172

173 continue A 3-tuple x is an imputation in the core of this game if and only if: x x x 1 (1) x x x x x x / 2, (2) 0, (3) 1/ 2, (4) x 1 2 x / 4, (5) 0, (6) x 1/ 2, (7) The system has many solutions, For example, (1/3,1/3,1/3) is in the core 173

174 When the core is empty? Definition Let be a game in characteristic function form. We say that is constant-sum if, for every coalition S, we have Further, Definition c ( S) ( S ) ( P). is zero-sum if it is constant sum and if, in addition Let be an N person game in normal form. Then we say that is constant-sum if there is a constant c such that N i 1 ( x,..., x ) c, i for all choices of strategies x,..., 1 xn for players p,..., 1 pn respectively. If c = 0, this reduces to zero-sum 1 N ( P)

175 continue Theorem If an N person game characteristic function is also constant-sum Theorem If is constant-sum in its normal form, then its is both essential and constant-sum, then its core is empty 175

176 example The municipal government of Lake Wobegon, Minnesota, is run by a City Council and a Mayor The Council consists of six Aldermen and a Chairman A bill can become a law in two ways: A majority of the Council (with the Chairman voting only in case of a tie among the Aldermen) approves it and the Mayor signs it The Council passes it, the Mayor vetoes it, but at least six of the seven members of the Council then vote to override the veto (in this case, the Chairman always votes) The game consists of all eight people involved signing approval or disapproval of the given bill 176

177 continue The payoffs would be in units of power gained by being on the winning side Define a winning coalition if it can pass a bill into law, e.g., a coalition consisting of any three Aldermen, the Chairman and the mayor. We define ( S) 1 if S is a winning coalition Define a coalition which is not willing a losing coalition, e.g., the coalition consisting of four Aldermen is a losing since they do not have the votes to override the mayor s veto. We define ( S) 0 if S is a losing coalition Note, every one player coalition is losing, the grand coalition is winning 177

178 continue An 8 tuple ( x, x, x,..., x ) is an imputation if and only if Theorem: The Lake Wobegon game has an empty core Proof Suppose on the contrary, is in the core. Now any coalition consisting of at least six members of the Council is winning. Thus and the same inequality holds if any one of the terms in it is dropped Since all xs M C implies that all the contradiction 1 6 x, x, x,..., x 0; M C 1 6 x x x x 1. M C 1 6 ( x, x, x,..., x ) M C x x x C , are nonnegative, and the sum of all eight is 1. This xs in the inequality above are zero. This is a 178

179 Existence of core In general, it is equivalent to find the feasibility of the LP: min x, s. t. x ( S), S P. x p P i p S But it is in general a NP-complete problem There are several techniques to find the core for special games Details are omitted here i i i 179

180 Veto Players and The Core In certain types of cooperative games, it is easy to determine the core Definition A veto player is a player without whom no coalition can achieve anything. That is, p is a veto player iff for all coalitions S, if p is not a member of S, then Theorem ( S) 0 Suppose that a cooperative game (with divisible payoffs) has some veto players. Then in any allocation in the core, the nonveto players get 0 and the veto players divide the value of the game among themselves 180

181 continue Definition 平衡的集合 (Balanced collection) 由 P 的非空子集所组成的集合 (collection)b 是一个平衡的 集合 (balanced collection), 如果对于 S B, 总存在正数, 使得 S 1 1 成立 S P S S N 其中, S 称为 B 中元素 S 的权重, 1 S 为元素 0 或者 1 的向量与 S 中的元素相对应的为 1, 否则为 0 举例 : 假设 P={1,2,3,4}, 则 {{1,2},{1,3},{1,4}, {2,3,4}} 就是以 1/3,1/3,1/3,2/3 为权重的平衡集合. 更具体的表示如下 : (1,1,0,0) (1,0,1,0) (1,0,0,1) (0,1,1,1) (1,1,1,1) 不包含任何平衡子集的平衡的集合, 称为最小平衡集合 (minimal balanced collection) 181

182 continue ( P, ) 是一个平衡的博弈 (balanced game), 如果对于任意平衡的集合 B 及其权重 { }, 总有 : 定义 : 合作博弈 ( P, ) 的核非空, 当且仅当该博弈是平衡的 举例 : P {1,2,3,4}, 假设对于参与人个数是 0,1,3,4 的联盟来说, ( S) 分别为 0,0,1,2; 对于参与人个数为 2 的联盟 定理 : 合作博弈 ( P) S ( S) S B (1,2) (1,3) (2,3) 1, (1,4) (2,4) (3,4) 0. 非空, 其中一个核配置是弈 (,,, ) S S B 该博弈的核, 因此它是平衡的博 182

183 Drawbacks of core As a solution concept for cooperative game, core has problems as follows: The core could be empty When it is non-empty it is often a large set The allocations that lie in the core could be unfair Three approaches are proposed, they are: Stable sets of Imputations Shapley Values The nucleolus 183

184 Stable sets of Imputations Definition Let X be a set of imputations for a game in characteristic function form. Then we say that X is stable if the following two conditions hold: (Internal Stability): No imputation in X dominates any other imputation in X through any coalition (External Stability): In Y is any imputation outside X, then it is dominated through some coalition by imputation inside X The idea of stable sets of imputations was introduced by von Neumann and Morgenstern in 1944, and they argued that a stable set is a solution of the game 184

185 Comments on Stable Sets Note that an imputation inside a stable set may be dominated by some imputation outside. Of course, that outside imputation is, in turn, dominated by some other imputations inside (via external stability). So transitive property does not hold for imputation dominance Since all imputations inside X are equal, one which actually prevails would be chosen in some way, say, via pure chance, custom, etc. But there is a problem since there may be an imputation outside X which dominates a given imputation inside. And if a coalition is formed based on this outside imputation, X is not stable anymore Someone argue that this chaotic series of formation and dissolutions of coalitions of different stable sets is ok, since real life often looks that way 核是比稳定集更强的概念, 即核是稳定集的子集 185

186 example For the three-person game in Table 1, we have showed that it has a stable set. Let We have the following result Theorem The set X defined above is a stable set for THREE Comment X {(0,1/2,1/2), (1/2,0,1/2), (1/2,1/2, 0)}. Note that there are imputations outside X which dominate members of X Consider, for example, (2/3,1/3,0) dominates (1/2,0,1/2) through coalition { p, p }. 1 2 On the other hand, (0, 1/2, 1/2) (a member of X) dominates (2/3,1/3, 0) through { p, p }

187 Shapley value Proposed by L.S. Shapley in 1953, an interesting attempt to define, in a fair way, an imputation which embodies what the players final payoffs "should" be It takes into account a player s contribution to the success of the coalition she belongs to If the characteristic function of the game is, and if S is the coalition to which player p i belongs, then ( p, S) ( S) ( S { p }) i i Lloyd Shapley 获得 2012 年诺贝尔经济学奖 is a measure of the amount that p i has contributed to S by joining it ( 称为边际贡献 ) 187

188 Lloyd Shapley With Alvin E. Roth, Shapley won the 2012 Nobel Memorial Prize in Economic Sciences "for the theory of stable allocations and the practice of market design." Lloyd Shapley 获得 2012 年诺贝尔经济学奖 188