# Games2-How to Find Optimal Strategies

Games and Strategies

? Professor Ho-Mou Wu

Games

Spring 2009

2-0

? Professor Ho-Mou Wu

Games

Spring 2009

2-1

Real World

Model

A

B

Spring 2009

? Professor Ho-Mou Wu

Games

2-2

John Nash’s Blonde Problem

Shapley 金发 Nash
? Professor Ho-Mou Wu

Spring 2009

0, 0 5, 10
Games

2-3

Simultaneous Moves and Confrontation

? Professor Ho-Mou Wu

Games

Spring 2009

2-4

Simultaneous Moves and Confrontation

? Professor Ho-Mou Wu

Games

Spring 2009

2-5

Capacity and Competitive Strategies

2-6

? Professor Ho-Mou Wu

Games

Spring 2009

Capacity and Competitive Strategies

(B)

Games

Spring 2009

? Professor Ho-Mou Wu

2-7

Capacity and Competitive Strategies

? Professor Ho-Mou Wu Games Spring 2009

2-8

Capacity and Competitive Strategies

? Professor Ho-Mou Wu Games Spring 2009

2-9

Sales Strategies

2-10

? Professor Ho-Mou Wu

Games

Spring 2009

Sales Strategies

Wal-Mart

Games

Spring 2009

Sears
? Professor Ho-Mou Wu

2-11

Sales Strategies

Sears 与对手均采稳定价格，各得50位消费者，二者 均可赚 (600－450) ×50＝7500。 任一家大减价而对手未减价可赚 (500－450) ×(50＋ 120)＝8500，未减价的一家公司仍可赚 (600 – 450) × 50 =7500。 两家都大减价：各賺 (500－450) ×(50+60) =5500。

? Professor Ho-Mou Wu Games Spring 2009

2-12

Simultaneous Moves

Games

Spring 2009

? Professor Ho-Mou Wu

2-13

SPNE

PBNE

? Professor Ho-Mou Wu

Games

Spring 2009

2-14

Noncooperative Games 不合作博弈
NE: Nash Equilibrium (Nash) SPNE: Subgame Perfect NE (Selten) 1994 Nobel Prize BNE: Bayesian NE (Harsanyi) PBNE: Perfect Bayesian NE or Sequential Equilibrium: (Kreps, Wilson, Milgrom, Fudenberg, Tirole, Maskin 等人) 1994: 不合作博弈的架构与均衡观念 2005: 重复的不合作博弈：冲突与合作导向
2-15

? Professor Ho-Mou Wu

Games

Spring 2009

Nobel Prizes
2005 Thomas C. Schelling and Robert Aumann 无名氏定理” “无名氏定理”(Folk Theorem)： ： 在一定条件下，在多次重复的不合作博弈中，经 由动态奖惩策略的使用，参赛者可能达到双赢 的“合作解”。 T.C. Schelling: Strategic Moves, Credible Threat, Brinkmanship, Focal Point, Strategic Arms Limitation Treaty (SALT). R. Aumann: Folk Theorem with Incomplete Information, Dynamic Arms Control Negotiation, Cooperative Games, Common Knowledge. (赛局高手：P.37, P.126, P.189.)
? Professor Ho-Mou Wu Games Spring 2009

2-16

Nobel Prizes

? Professor Ho-Mou Wu Games Spring 2009

2-17

? Professor Ho-Mou Wu

u1 , u 2
Games Spring 2009

2-18

The Brandenburg-Nalebuff Value Net
Supplier Supplier

Competitor

Firm

Complementor

Customer

Customer (McAfee, Ch.2)

? Professor Ho-Mou Wu

Games

Spring 2009

2-19

Industry Analysis
Six Forces (Brandenberger and Nalebuff) 1. New entrants, 2. Buyer bargaining power, 3. Supplier bargaining power, 4. Substitute products, 5. Rivalry, 6. Complements. Since each strategic decision may involve different elements, we have to reject a one-size-fits-all way of thinking about business strategy and apply the gametheoretic reasoning to each decision.
? Professor Ho-Mou Wu Games Spring 2009

2-20

? Professor Ho-Mou Wu Games

Spring 2009

2-21

Some of the Strategic Variables Chosen by Firms
Product Features and Quality Target of Customers Technological Leadership Research and Development Product Marketing and Positioning Provision of Complementary Goods Brand Identification Geographic Markets Distribution Channels Product Pricing Vertical Integration Cost Reduction Focus Government Relations (McAfee, Ch.1)
? Professor Ho-Mou Wu Games Spring 2009

2-22

1.优势策略均衡 (Dominant Strategy Equilibrium, DSE) 优势策略均衡 优势策略 (dominant strategy) ? is the best response against any action the other player might take. “承认”是囚犯的优势策略 ? 不管对手所采策略为“承认” 或“否认”，任一囚犯承认都可获得较高的报酬。 重复 优 势解法 (Iterated Dominance) ? 逐次删去 劣势策略 (dominated strategy)，但对两性战争、钱币配对和飚车问题， 就无法解出。

U D
? Professor Ho-Mou Wu

L 2, 3 1, 1
Games

M 0, 2 2, 7

R 3, 4 4, 5
Spring 2009

2-23

2. 纳什均衡(Nash Equilibrium, NE) 纳什均衡 ?达到均衡后，任一参赛者均无诱因偏离此一均衡。
(John Nash, 1950) ?另一种解释：当 S1*是对 S2*的最适反应， S2*是对 S1*的最适 反应 (best response) 时， ( S1* , S2* )即为纳什均衡 )即为纳什均衡。

DSE: I am doing the best I can no matter what you do. You are doing the best you can no matter what I do. NE: I am doing the best I can given what you are doing. You are doing the best you can given what I am doing.
? Professor Ho-Mou Wu Games Spring 2009

2-24

DSE=NE 飚车族： 对开 对开 -1 , -1

7500 , 7500 7500 , 8500 8500 , 7500 5500 , 5500

? Professor Ho-Mou Wu

Games

Spring 2009

2-25

q 正面 p 1-p 正面 反面 1 , -1 -1 , 1

1-q 反面 -1 , 1 1 , -1

? Professor Ho-Mou Wu Games Spring 2009

2-26

Sales Strategies

Wal-Mart 稳定价格 q 大减价 1-q

7500, 7500 7500, 8500 ?Sears采稳定价，对手采大减价，对手 p 成长，Sears是否会满意？双方都想 Sears 大减价 找最有利的结果 (8500) ，若Sears更 8500, 7500 5500, 5500 1-p 动策略，可否达成另一均衡？

Wal-Mart ?若Sears长久维持稳定价，待全部人 稳定价格 q 大减价 1-q (包含无信息的100人) 都知道后，这

Sears

p

7500, 7500 0, 11000 11000, 0 5500, 5500

Games Spring 2009

? Professor Ho-Mou Wu

2-27

Sales Strategies

2 q = ，双方利润均为7500 3 1 此纳什均衡中，Sears 与 Wal-Mart 都采 机会大减价 (1年中共有 3 4个月时间定价500元，其它时间600元)：“随机而且出人意料的

? Professor Ho-Mou Wu Games Spring 2009

2 ?P = ，同理 3

2-28

Sales Strategies

?pricing cycles.
? 混合策略均衡利于造成百货业对消费者的“差别取 价”(price discrimination)：不查报纸的消费者永远不知哪家 1 当时是最低价，有 机会到一家不减价的百货公司，他们 2 必须付出高价，支持了此种混合策略均衡。
(参见 H.Varian, “A Model of Sales,” American Economic Review, 1980)
? Professor Ho-Mou Wu Games Spring 2009

2-29

? Professor Ho-Mou Wu

Games

Spring 2009

2-30

? 定义：混合策略 (Mixed Strategy) 混合策略
– 策略形式博弈中，一个参赛者的混合策略 混合策略指赋在 混合策略 该参赛者所有策略行动上的一个概率分布。 – 一般地，用 σ 表示一组混合策略：σ i (ai )表示参与 者 i 的混合策略 σ i 中赋给策略行动 ai 的概率。类 似地，一个参与者的混合策略需要指明对其每个 策略行动赋加的概率 (即随机选择出该策略的概 率)。 – 记参赛者 i 可以取的所有混合策略的集合为 Σi

? 一个混合策略也可能是赋给某个特定策略行动概率1 而其他行动都为 0，此时称这个混合策略为纯策略 纯策略。 纯策略
? Professor Ho-Mou Wu Games Spring 2009

2-31

? 混合策略纳什均衡的意涵与纯策略纳什均衡相 混合策略纳什均衡 似，只是，在其他人策略下，“采用某策略的 收益”改变为“采用此混合策略下的期望收 益”。

? ? U i (σ i? , σ ? i ) ≥ U i (σ i , σ ?i ) for all σ i ∈ Σi

–任一参赛者的混合策略均是对于其他人混合策略 ? 的最优反应 σ i? ∈ Bi (σ ?i ) for all i
? Professor Ho-Mou Wu Games Spring 2009

2-32

Mixed Strategy Nash Equilibrium: Characterization

? 混合策略可以看成是纯策略行动的线性组合； 而采用策略后的收益也可以类似地考虑：

U i (σ ) =
ai ∈Ai

∑ σ (a ) ? E (a , σ
i i i i

?i

)

? Professor Ho-Mou Wu

Games

Spring 2009

2-33

Mixed Strategy Nash Equilibrium: Characterization
? 前面的考虑方法可以给我们带来判断和寻找混合策 略纳什均衡的如下方法： 一个混合策略组合 σ ? 是纳什均衡的充要条件为：
? – 给定σ ?i ，采用 σ i? 中任何的为正的概率项所对应的策略行 动，参与者 i 期望收益均相同； ? – 给定 σ ?i ，采用 σ i? 中任何的为零的概率项所对应的策略行 动，参与者 i 不能有更多的期望收益 (不多于正概率项对 应策略的期望收益)。

? Professor Ho-Mou Wu Games Spring 2009

2-34

Games2-How_to_Find_Optimal_Strategies_图文.ppt
Games2-How_to_Find_Optimal_Strategies - Games and Strategies ? Professor Ho-Mou Wu Games Sprin...
2#美赛-数学建模-写作模版(各部分)重点.doc
2#美赛-数学建模-写作模版(各部分)重点_中职中专_...b. 直接指出问题: 例 1:We find the optimal ...conclusions, strategies, (and recommendations to ...
Agenda_World Clean Coal Conference Annual Assembly 2015 - 2_....pdf
Annual Assembly 2015 - 2_英语学习_外语学习_教育...Major policy challenges and strategies for the ...Optimal design and integration of ASU ? Innovation...
...TO FIND OPTIMAL MIXED STRATEGIES IN TWO PLAYERS MATRIX GAMES.unkown
USING DIFFERENTIAL EVOLUTION TO FIND OPTIMAL MIXED STRATEGIES IN TWO PLAYERS MATRIX GAMES Boryczka Urszula, Juszczuk Przemyslaw University of Silesia Department...
Games2-How to Find Optimal Strategies_图文.ppt
Games and Strategies ? Professor Ho-Mou Wu Games Spring 2009 2-0 寻找最佳策略 How to Find Optimal Strategies? 例1:回到电影“美丽心灵”中在酒吧的情景:...
...to Find the Pareto Solutions of Multiobjective Optimal ....pdf
38, NO. 2, MARCH 2002 1013 A Tabu Method to Find the Pareto Solutions of Multiobjective Optimal Design Problems in Electromagnetics S. L. Ho, Shiyou...
Optimal navigation and object finding without geometric maps ....pdf
Optimal navigation and object finding without ...For this, the robot was equipped with two ...Path planning strategies for a point mobile ...
On Finding Primal- and Dual-Optimal Bases_图文.pdf
Analogously, given any dual-optimal solution, it is easy to find a dual-optimal basis. However, none of the two bases found in this way is ...
Optimal navigation and object finding without geometric maps ....pdf
Optimal navigation and object finding without ...For this, the robot was equipped with two ...Path planning strategies for a point mobile ...
Finding an Optimal Match Window for Spruce Top Detection ....pdf
Several possible strategies for retaining as many of the true tree top ...2; (12) which thus are the parameter values which yield the optimal ...
An ACT-R Model of Memory Applied to Finding the Optimal ....pdf
Finding the Optimal Schedule of Practice When_专业...First, it needs to describe accurately how ...The experiment took place in two sessions ...
An Efficient Parallel Algorithm for Optimum Path Finding in ....pdf
An Efficient Parallel Algorithm for Optimum Path Finding in Fixed Industry ...Hence, if at all the shortest path exists, then pk 2 P ? NP . ...
Finding Optimal Addition Chains Using a Genetic Algorithm ....pdf
Finding Optimal Addition Chains Using a Genetic ...(2) Binary strategies evaluate equation (2) by ...Fogel. How to Solve It: Modern Heuristics. ...
Finding optimal models for small gene networks.pdf
Finding optimal models for small gene networks_专业资料。Finding gene networks...Step 1: Step 2: Step 3: Step 4: Step 4a: Step 4b: Step 5: ...
Finding Optimal Paths in MREP Routing.pdf
Finding Optimal Paths in MREP Routing_专业资料。Maximum Residual Energy Path...3.2 Solving MREPP In this section we describe how to ?nd optimal MRE ...
Finding optimal paths in MREP routing.pdf
Finding optimal paths in MREP routing_专业资料。Maximum Residual Energy Path...3.2. Solving MREPP In this section we describe how to ?nd optimal MRE...
Algorithms for Finding Optimal Disjoint Paths Around a ....pdf
Algorithms for Finding Optimal Disjoint Paths Around...2 De?nition and Terminology Before dealing ...[0, n ? 1], the way how terminals are ...
1 FINDING OPTIMAL PORTFOLIOS WITH CONSTRAINTS ON VALUE AT ....pdf
How to obtain a portfolio rebalancing strategy which would keep portfolio ...Our emphasis 2 here is on algorithms because, unlike optimal mean-variance ...
...NP-Completeness of Finding an Optimal Strategy in Games ....pdf
Finding an Optimal Strategy in Games with Common ...This is true even if there are only two ...s of deterministic strategies, there can be no ...
How to find a near-optimal mapping of neural networks onto ....pdf
How to find a near-optimal mapping of neural networks onto message passing...6 Iterative Improvement with 2-opt strategy To achieve near-optimal ...