零和游戏 一个矩阵A P s R “行玩家”选一行 P 0 -1 1 “列玩家”选一列c -1 行玩家得到的回报是A,c,列玩家得到-Ar,c R 0 行玩家的目标是最大化A,c,而列玩家目标是最小化Ar,c 纳什均衡：即使一个玩家知道对方的策略之后，他/她也不能找到比 当前策略严格更优的策略。 单纯的策略(pure strategy):选一行/列 混合的策略(mixed strategy):单纯策略的一个概率分布 2
零和游戏 一个矩阵� • “行玩家”选一行r • “列玩家”选一列c 行玩家得到的回报是�!,#，列玩家得到−�!,# 行玩家的目标是最大化 �!,#，而列玩家目标是最小化�!,# 纳什均衡：即使一个玩家知道对方的策略之后，他/她也不能找到比 当前策略严格更优的策略。 单纯的策略(pure strategy)：选一行/列 混合的策略(mixed strategy)：单纯策略的一个概率分布 2
Von-Neumann Minimax Theorem 给定A∈Rmxn 假设行玩家策略的概率分布是x∈△m 列玩家策略的概率分布是y∈△” 那么它们玩下来的期望回报是xTAy Von-Neumann Minimax Theorem. max min xTAy min max xTAy x∈△mye△n y∈△nx∈△m 不管谁先宣布自己的策略，都会达到均衡解 3
Von-Neumann Minimax Theorem 给定� ∈ ℝ!×# 假设行玩家策略的概率分布是 � ∈ Δ! 列玩家策略的概率分布是� ∈ Δ# 那么它们玩下来的期望回报是�$�� Von-Neumann Minimax Theorem. max %∈'! min (∈'" �$�� = min (∈'" max %∈'! �$�� 不管谁先宣布自己的策略，都会达到均衡解 3
Von-Neumann Minimax Theorem Von-Neumann Minimax Theorem. max min xTAy min max xTAy xE△mye△n ye△nxE△抗 证明： 左边：行玩家先选定x 列玩家在给定xTA后，如何选择最优的y? xTA为一行向量，注意到y为概率分布 令(xTA)O)为xTA的第列，则有 min(xTA)0)≤xTAy≤max(xTA)0) 且等号可以取到。因此mi热xTAy=min(xTA)) VE△ 左边即可化简为思mn(A0 4
Von-Neumann Minimax Theorem Von-Neumann Minimax Theorem. max #∈%! min &∈%" �'�� = min &∈%" max #∈%! �'�� 证明： 左边: 行玩家先选定 � 列玩家在给定�'�后，如何选择最优的�？ �'�为一行向量， 注意到�为概率分布 令 �'� ()) 为�'�的第 �列，则有 min ) �'� ()) ≤ �'�� ≤ max ) �'� ()) 且等号可以取到。因此min &∈%" �'�� = min ) �'� ()) 左边即可化简为max #∈%! min & �'� (&) 4
Von-Neumann Minimax Theorem Von-Neumann Minimax Theorem. max min xTAy min max xTAy x∈△my∈△n y∈△nx∈△m 证明(cont'd): 左边可化简为盟min(cTA)0,这可以通过LP表示 max 引入辅助变量t=min(xTA)⑩ m xrA00=∑xay≥t j=1,…,n m xi=1 x∈△m i=1 x≥0 i=1,…,m 5
Von-Neumann Minimax Theorem Von-Neumann Minimax Theorem. max %∈'! min (∈'" �$�� = min (∈'" max %∈'! �$�� 证明(cont’d)： 左边可化简为max !∈#! min $ �%� ($) ，这可以通过LP表示 max � �%� ($) = + ()* + �(�($ ≥ � ∀� = 1, … , � + ()* + �( = 1 �( ≥ 0 ∀� = 1, … , � 5 引入辅助变量 � = min ) �'� ()) � ∈ Δ+
Von-Neumann Minimax Theorem Von-Neumann Minimax Theorem. max min xTAy min max xTAy x∈△mye△n ye△nx∈△m 证明(cont'd): 类似地，右边可化简为min max(Ay),进而通过LP表示 V∈△ min 引入辅助变量r=max(Ay): 4=∑ay≤r i=1,.,m yi=1 y∈△n i=1 y:≥0i=1,,n 6
Von-Neumann Minimax Theorem Von-Neumann Minimax Theorem. max %∈'! min (∈'" �$�� = min (∈'" max %∈'! �$�� 证明(cont’d)： 类似地，右边可化简为min ,∈#" max ( �� (，进而通过LP表示 min � �� ( = + $)* - �($ �$ ≤ � ∀� = 1, … , � + ()* - �( = 1 �( ≥ 0 ∀� = 1, … , � 6 引入辅助变量 � = max , �� , � ∈ Δ-
Von-Neumann Minimax Theorem Von-Neumann Minimax Theorem. 器盟xAy=热盟器xA 证明(cont'd):把它们都转化为标准形式 max t min r m t- xay≤0j=1,,n ×yj r-> ay≥0 i=1,…,m ×xi m =1 Xr 〉.y=1 ×t 台 i=1 x:≥0 i=1,.,m y≥0 i=1,…,n Equality follows directly from strong duality!
Von-Neumann Minimax Theorem Von-Neumann Minimax Theorem. max #∈%! min &∈%" �'�� = min &∈%" max #∈%! �'�� 证明(cont’d)：把它们都转化为标准形式 7 min � � − 2 )./ - �,) �) ≥ 0 ∀� = 1, … , � 2 ,./ - �, = 1 �, ≥ 0 ∀� = 1, … , � max � � − 2 ,./ + �,�,) ≤ 0 ∀� = 1, … , � 2 ,./ + �, = 1 �, ≥ 0 ∀� = 1, … , � × � × �) × � × �, Equality follows directly from strong duality!
Yao's Minimax Principle 一个随机算法的最坏运行时间，是它在所有输入实例中期望运行时间的最大值 试考虑这样的一个零和游戏： “算法”玩家需要从不同的算法中选择，目标是最小化运行时间 “攻击”玩家需要从不同的输入实例中选择，目标是最大化运行时间 “算法”的混合策略：随机算法 “攻击”的混合策略：输入实例的概率分布 要成功地“攻击”所有的随机算法，等价的问题是： 给出一个输入实例的概率分布，使得所有的确定性算法的期望运行时间都比较大 8
Yao’s Minimax Principle 一个随机算法的最坏运行时间，是它在所有输入实例中期望运行时间的最大值 试考虑这样的一个零和游戏： “算法”玩家需要从不同的算法中选择，目标是最小化运行时间 “攻击”玩家需要从不同的输入实例中选择，目标是最大化运行时间 “算法”的混合策略：随机算法 “攻击”的混合策略：输入实例的概率分布 要成功地“攻击”所有的随机算法，等价的问题是： 给出一个输入实例的概率分布，使得所有的确定性算法的期望运行时间都比较大 8
对偶LP在经济学中的解释 设想我们为自己设计一份菜单 目标：满足每天营养需求、尽量的廉价 营养需求：500卡的蛋白质，100卡的碳水和400卡的脂肪 肉类 主食 乳制品 蛋白质 500 50 300 碳水 0 300 100 脂肪 500 25 200 价格 5 2 4 假设每类食物都是无限可分的。 求解：这3类食物的一个组合，既满足每天的营养要求，同时越经济越好
对偶LP在经济学中的解释 设想我们为自己设计一份菜单 目标：满足每天营养需求、尽量的廉价 营养需求：500卡的蛋白质，100卡的碳水和400卡的脂肪 假设每类食物都是无限可分的。 求解：这3类食物的一个组合，既满足每天的营养要求，同时越经济越好。 肉类 主食 乳制品 蛋白质 500 50 300 碳水 0 300 100 脂肪 500 25 200 价格 5 2 4
对偶LP在经济学中的解释 令x:肉类，少：主食，z:乳制品，有如下的线性规划 min 5x+2y+4z (花费) s.t.500x+50y+300z≥500 (每日蛋白质要求) 0x+300y+100z≥100 (每日碳水要求) 500x+25y+200z≥400 (每日脂肪要求) x,y,z≥0. 对偶规划如下. max500a+100b+400c s.t.500a+0b+500c≤5 50a+300b+25c≤2 新产品达到肉类同样的营养的所需 300a+100b+200c≤4 花费不应该超过肉类 a,b,c≥0 否则客户只会直接购买肉类 设想一家未来的制药公司有蛋白质，碳水和脂肪三种药丸作为新产品。 应该如何为这些药丸定价？
对偶LP在经济学中的解释 设想一家未来的制药公司有蛋白质，碳水和脂肪三种药丸作为新产品。 应该如何为这些药丸定价？ 新产品达到肉类同样的营养的所需 花费不应该超过肉类 否则客户只会直接购买肉类
Optimal transport Earth mover's distance(选讲) “愚公移山”距离 考虑在直线上的一座“山”{P},希望通过搬运，变成另外的形状{q} 求最小的搬运方案 rudu subject to ∑fujsqnVj ∑i≤wn 2∑-2=∑o Kantorovich(-Rubinstein)对偶性： 在最优的（经过充分博奔的）传输方案之中，“自己搬运”的开销，与“最佳外包”的开销是一样的
Earth mover’s distance (选讲) “愚公移山”距离 考虑在直线上的一座“山” {�*}，希望通过搬运，变成另外的形状{�*} 求最小的搬运方案 ���� 6 � 6 � ��,���,� subject to 6 * �*,& ≤ �&, ∀� 6 & �*,& ≤ �*, ∀� 6 * 6 & �*,& = 6 * �* = 6 & �& Kantorovich(-Rubinstein) 对偶性： 在最优的(经过充分博弈的)传输方案之中，“自己搬运”的开销，与“最佳外包”的开销是一样的 Optimal transport