零和游戏 一个矩阵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 , �� , � ∈ Δ-