西安电子科技大学：《博弈论》课程教学资源（PPT课件）Lecture 1 GAME THEORY - Static complete information pure strategy game

Outline of Static Games of Complete Information Introduction to games Normal-form (or strategic-form) representation Iterated elimination of strictly dominated strategies ■Nash equilibrium Applications of Nash equilibrium Mixed strategy Nash equilibrium

4 Outline of Static Games of Complete Information ◼ Introduction to games ◼ Normal-form (or strategic-form) representation ◼ Iterated elimination of strictly dominated strategies ◼ Nash equilibrium ◼ Applications of Nash equilibrium ◼ Mixed strategy Nash equilibrium

什么是博弈论？ ·什么是博弈？任何需要顾及到个体利益的决策过程，都是博弈 ■博弈的特点： 。分布式：一般没有中央控制单元，博弈者各自为政 ·多成员：至少包含两名或以上博弈者 ■相互联系：一名博弈者的决定，可能会影响其他博弈者 ■对完整博弈过程的一种逻辑的分析 ·博弈过程：如大国博弈（贸易出口），或个人博弈（股票投资 ) ·一种逻辑：没个博弈者(Game Player)都是理性的获取其最 大利益 ·分析： ■如何制定博弈规则，从而形成最佳的系统（如联合国机制)？ ■每个博弈者，应当如何制定对其最优的策略，从而最大化其收益？ 5

什么是博弈论？ ◼ 什么是博弈？任何需要顾及到个体利益的决策过程，都是博弈 ◼ 博弈的特点： ◼ 分布式：一般没有中央控制单元，博弈者各自为政 ◼ 多成员：至少包含两名或以上博弈者 ◼ 相互联系：一名博弈者的决定，可能会影响其他博弈者 ◼ 对完整博弈过程的一种逻辑的分析 ◼ 博弈过程：如大国博弈（贸易出口），或个人博弈（股票投资 ） ◼ 一种逻辑：没个博弈者（Game Player）都是理性的获取其最 大利益 ◼ 分析： ◼ 如何制定博弈规则，从而形成最佳的系统（如联合国机制）？ ◼ 每个博弈者，应当如何制定对其最优的策略，从而最大化其收益？ 5

稳定是关键！ ■ 什么是博弈？任何需要顾及到个体利益的决策过程， 都是博弈 ■ 博弈的特点： 。分布式：一般没有中央控制单元，博弈者各自为政 ·多成员：至少包含两名或以上博弈者 ·相互联系：一名博弈者的决定，可能会影响其他博弈者 ■基础是稳定（纳什均衡(Nash Equilibrium)) ■目标是利益最大化(Pareto Optimal)

稳定是关键！ ◼ 什么是博弈？任何需要顾及到个体利益的决策过程， 都是博弈 ◼ 博弈的特点： ◼ 分布式：一般没有中央控制单元，博弈者各自为政 ◼ 多成员：至少包含两名或以上博弈者 ◼ 相互联系：一名博弈者的决定，可能会影响其他博弈者 ◼ 基础是稳定（纳什均衡（Nash Equilibrium）） ◼ 目标是利益最大化（ Pareto Optimal ） 6

What is game theory? We focus on games where: -There are at least two rational players Each player has more than one choices The outcome depends on the strategies chosen by all players;there is strategic interaction -Strategic externality Example:Six people go to a restaurant Each person pays his/her own meal-a simple decision problem -Before the meal,every person agrees to split the bill evenly among them-a game

7 What is game theory? ◼ We focus on games where: ➢ There are at least two rational players ➢ Each player has more than one choices ➢ The outcome depends on the strategies chosen by all players; there is strategic interaction ➢ Strategic externality ◼ Example: Six people go to a restaurant. ➢ Each person pays his/her own meal – a simple decision problem ➢ Before the meal, every person agrees to split the bill evenly among them – a game

A Beautiful Mind 约翰·纳什，生于1928年6月13日。著名经济学家、博弈论创始人 ,因对博弈论和经济学产生了重大影响，而获得1994年诺贝尔经 济学奖。2015年5月23日，于美国新泽西州逝世 1950年于其仅27页的博士论文中提出重要发现，这就是后来被称 为“纳什均衡”的博弈理论 RUSSELL CROWE ED HARRIS A BEAUTIEUL mth MIND

A Beautiful Mind ◼ 约翰·纳什，生于1928年6月13日。著名经济学家、博弈论创始人 ，因对博弈论和经济学产生了重大影响，而获得1994年诺贝尔经 济学奖。2015年5月23日，于美国新泽西州逝世 ◼ 1950年于其仅27页的博士论文中提出重要发现，这就是后来被称 为“纳什均衡”的博弈理论 8

What is game theory? Game theory is a formal way to analyze strategic interaction among a group of rational players (or agents) Game theory has applications -Economics/Politics/Sociology/Law/Biology >The"double helix"and unifying tool for social scientists

9 What is game theory? ◼ Game theory is a formal way to analyze strategic interaction among a group of rational players (or agents) ◼ Game theory has applications ➢ Economics/Politics/Sociology/Law/Biology ➢ The “double helix” and unifying tool for social scientists

Classic Example:Prisoners'Dilemma Two suspects held in separate cells are charged with a major crime.However,there is not enough evidence. Both suspects are told the following policy: If neither confesses then both will be convicted of a minor offense and sentenced to one month in jail. If both confess then both will be sentenced to jail for six months. >If one confesses but the other does not,then the confessor will be released but the other will be sentenced to jail for nine months. Prisoner 2 Mum Confess Mum -1 ,-1 -9， 0 Prisoner 1 Confess 0 ,-9 -6 -6 10

10 Classic Example: Prisoners’ Dilemma ◼ Two suspects held in separate cells are charged with a major crime. However, there is not enough evidence. ◼ Both suspects are told the following policy: ➢ If neither confesses then both will be convicted of a minor offense and sentenced to one month in jail. ➢ If both confess then both will be sentenced to jail for six months. ➢ If one confesses but the other does not, then the confessor will be released but the other will be sentenced to jail for nine months. -1 , -1 -9 , 0 0 , -9 -6 , -6 Prisoner 1 Prisoner 2 Confess Mum Confess Mum

Example:The battle of the sexes At the separate workplaces,Chris and Pat must choose to attend either an opera or a prize fight in the evening. Both Chris and Pat know the following: Both would like to spend the evening together. But Chris prefers the opera. >Pat prefers the prize fight. Non-zero-sum game Pat Opera Prize Fight Opera 2 1 0 0 Chris Prize Fight 0 0 2

11 Example: The battle of the sexes ◼ At the separate workplaces, Chris and Pat must choose to attend either an opera or a prize fight in the evening. ◼ Both Chris and Pat know the following: ➢ Both would like to spend the evening together. ➢ But Chris prefers the opera. ➢ Pat prefers the prize fight. ◼ Non-zero-sum game 2 , 1 0 , 0 0 , 0 1 , 2 Chris Pat Prize Fight Opera Prize Fight Opera

Example:Matching pennies ■ Each of the two players has a penny. Two players must simultaneously choose whether to show the Head or the Tail. Both players know the following rules: >If two pennies match(both heads or both tails)then player 2 wins player 1's penny. >Otherwise,player 1 wins player 2's penny. Zero-sum game:no way for collaboration Player 2 Head Tail Head -1 1 1 -1 Player 1 Tail -1 12

12 Example: Matching pennies ◼ Each of the two players has a penny. ◼ Two players must simultaneously choose whether to show the Head or the Tail. ◼ Both players know the following rules: ➢ If two pennies match (both heads or both tails) then player 2 wins player 1’s penny. ➢ Otherwise, player 1 wins player 2’s penny. ➢ Zero-sum game: no way for collaboration -1 , 1 1 , -1 1 , -1 -1 , 1 Player 1 Player 2 Tail Head Tail Head

Static (or simultaneous-move)games of complete information A static (or simultaneous-move)game consists of: A set of players (at least Player 1,Player 2,... two players) Player n} For each player,a set of >SI S2 ...Sn strategies/actions ■Payoffs received by > each player for the ui(Sp,S2 ....)for all combinations of the S1∈S,S2∈S2,.Sn∈Sr strategies,or for each player,preferences over the combinations of the strategies 6

13 Static (or simultaneous-move) games of complete information ◼ A set of players (at least two players) ◼ For each player, a set of strategies/actions ◼ Payoffs received by each player for the combinations of the strategies, or for each player, preferences over the combinations of the strategies ➢ {Player 1, Player 2, ... Player n} ➢ S1 S2 ... Sn ➢ ui (s1 , s2 , ...sn ), for all s1S1 , s2S2 , ... snSn . A static (or simultaneous-move) game consists of: