【博弈论 |
您所在的位置:网站首页 › 博弈论纳什均衡的概念 › 【博弈论 |
文章目录
占优行为囚徒困境
重复剔除劣战略行为Nash均衡的定义混合战略Nash均衡混合战略混合战略Nash均衡
混合战略Nash均衡的求解支撑求解法规划求解法零和博弈
占优行为
囚徒困境
说明: (抵赖,抵赖)Pareto优于(坦白,坦白),看似对双方来说都是不错的选择(双赢),但是不可能成为一致性预测;这是因为,对每一方来说都有更好的选择,即牺牲另一方的支付,产生坦白-抵赖的局面。在囚徒困境问题中,无论其他人选择什么战略,参与人的最优战略(坦白)总是唯一的。这样的最优战略称为“占优战略”。 下面给出他的规范化定义: 定义2.1 在 n n n人博弈中,如果对于所有的其他参与人的选择 s − i s_{-i} s−i, s i ∗ s_i^* si∗都是参与人 i i i的最优选择,即 ∀ s i ∈ S i ( s i ≠ s i ∗ ) \forall s_i\in S_i(s_i\not =s_i^*) ∀si∈Si(si=si∗), ∀ s − i ∈ ∏ j = 1 , j ≠ i n S j \forall s_{-i}\in \prod_{j=1,j\not=i}^nS_j ∀s−i∈∏j=1,j=inSj,有 u i ( s i ∗ , s − i ) > u i ( s i , s − i ) u_i(s_i^*,s_{-i})\gt u_i(s_i,s_{-i}) ui(si∗,s−i)>ui(si,s−i) 则称 s i ∗ s^*_i si∗为参与人 i i i的占优战略。 简而言之,就是不管别人怎么选,我选这个战略的效用函数都能取到最大。 而我选择这一选择战略的行为称为占优行为。 定义2.2 在 n n n人博弈中,如果对所有参与人 i i i,都存在占优战略 s i ∗ s_i^* si∗,则占优战略组合 s ∗ = ( s 1 ∗ , s 2 ∗ , . . . , s n ∗ ) s^*=(s_1^*,s_2^*,...,s_n^*) s∗=(s1∗,s2∗,...,sn∗)称为占优战略均衡。 怎么判断呢? 在每一个其他人的战略组合下,比较一下自己选择不同战略下的效用,如果存在一个战略的效用比其他情况都好,那这个就是占优战略。 重复剔除劣战略行为定义2.3 在 n n n人博弈中,如果对于参与人 i i i,存在战略 s i ′ , s ′ ′ ∈ S i s_i',s''\in S_i si′,s′′∈Si,对 ∀ s − i ∈ ∏ j = 1 , j ≠ i n S j \forall s_{-i}\in\prod_{j=1,j\not=i}^nS_j ∀s−i∈∏j=1,j=inSj,有 u i ( s i ′ ′ , s − i ) > u i ( s i ′ , s − i ) u_i(s_i'',s_{-i})\gt u_i(s_i',s_{-i}) ui(si′′,s−i)>ui(si′,s−i)则称战略 s i ′ s_i' si′为参与人 i i i的劣战略,或者说战略 s i ′ ′ s_i'' si′′相对于战略 s i ′ s_i' si′占优。 参与人的这种选择行为称为剔除劣战略行为。 重复剔除劣战略后,对战略式博弈 G G G的求解问题就可转换为对 G ′ G' G′的求解。遵循这一思路,不断剔除劣战略的行为称为重复剔除劣战略行为。 通过重复剔除劣战略得到的解称为重复剔除的占优均衡。 定义2.4 在 n n n人博弈中,如果对于参与人 i i i,存在战略 s i ′ , s i ′ ′ ∈ S i s_i',s_i''\in S_i si′,si′′∈Si,对 ∀ s − i ∈ ∏ j = 1 , j ≠ i n S j \forall s_{-i}\in\prod_{j=1,j\not=i}^nS_j ∀s−i∈∏j=1,j=inSj,有 u i ( s i ′ ′ , s − i ) ≥ u i ( s i ′ , s − i ) u_i(s_i'',s_{-i})\ge u_i(s_i',s_{-i}) ui(si′′,s−i)≥ui(si′,s−i)且 ∃ s − i ′ \exist s_{-i}' ∃s−i′,使得 u i ( s i ′ ′ , s − i ) > u i ( s i ′ , s − i ) u_i(s_i'',s_{-i})\gt u_i(s_i',s_{-i}) ui(si′′,s−i)>ui(si′,s−i)则称战略 s i ′ s_i' si′为参与人 i i i的弱劣战略,或者说战略 s i ′ ′ s_i'' si′′相对于战略 s i ′ s_i' si′弱占优。 所以劣战略可分为严格劣战略和弱劣战略。 如果重复剔除劣战略行为中包含弱劣战略的剔除,那么顺序的不同会造成解的不同。 Nash均衡的定义定义2.5 在一个给定的 n n n人战略式博弈中,战略组合 s ∗ s^* s∗是一个Nash均衡当前仅当 ∀ i ∈ Γ , ∀ s i ∈ S i \forall i\in\Gamma,\forall s_i\in S_i ∀i∈Γ,∀si∈Si,有 u i ( s i ∗ , s − 1 ∗ ) ≥ u i ( s i , s − i ∗ ) u_i(s_i^*,s_{-1}^*)\ge u_i(s_i,s_{-i}^*) ui(si∗,s−1∗)≥ui(si,s−i∗) 或者 ∀ i ∈ Γ \forall i\in\Gamma ∀i∈Γ, s i ∗ ∈ arg max s i ∈ S i u i ( s i , s − i ∗ ) s_i^*\in \argmax_{s_i\in S_i}u_i(s_i,s_{-i}^*) si∗∈si∈Siargmaxui(si,s−i∗)。 求取纯战略Nash均衡的方法: 划线法;箭头法。 混合战略Nash均衡 混合战略以一定的概率分布来选择自己战略的行为,在博弈论中称之为混合战略。 定义2.6 在一个给定的有限 n n n人战略式博弈中,对任一参与人 i i i,设 S i = { s i 1 , . . . , s i K } S_i=\{s_i^1,...,s_i^K\} Si={si1,...,siK},则参与人 i i i的一个混合战略定义为在战略集 S i S_i Si上的一个概率分布 σ i = ( σ i 1 , . . . , σ i K i ) \sigma_i=(\sigma_i^1,...,\sigma_i^{K_i}) σi=(σi1,...,σiKi)。 符号含义 Σ i \Sigma_i Σi参与人 i i i的混合战略空间 Σ \Sigma Σ混合战略组合空间 π ( s ) \pi(s) π(s)在混合战略组合 σ \sigma σ下,纯战略组合 s s s出现的概率 v i ( σ ) v_i(\sigma) vi(σ) = ∑ s ∈ S π ( s ) u i ( s ) =\sum_{s\in S}\pi(s)u_i(s) =∑s∈Sπ(s)ui(s),参与人 i i i的期望效用 σ j ( s j ) \sigma_j(s_j) σj(sj)在混合战略组合 σ \sigma σ下,参与人 j j j选择 s j s_j sj的概率 混合战略Nash均衡定义2.7 在有限 n n n人战略式博弈中,混合战略组合 σ ∗ \sigma^* σ∗为一个Nash均衡,当且仅当 ∀ i ∈ Γ , ∀ σ i ∈ Σ i \forall i\in\Gamma,\forall\sigma_i\in\Sigma_i ∀i∈Γ,∀σi∈Σi,有 v i ( σ i ∗ , σ − i ∗ ) ≥ v i ( σ i , σ − i ∗ ) v_i(\sigma_i^*,\sigma_{-i}^*)\ge v_i(\sigma_i,\sigma_{-i}^*) vi(σi∗,σ−i∗)≥vi(σi,σ−i∗)。 定义2.8 在有限 n n n人战略式博弈中,混合战略组合 σ ∗ \sigma^* σ∗为一个Nash均衡,当且仅当 ∀ i ∈ Γ , ∀ σ i ∈ Σ i \forall i\in\Gamma,\forall\sigma_i\in\Sigma_i ∀i∈Γ,∀σi∈Σi,有 v i ( σ i ∗ , σ − i ∗ ) ≥ v i ( s i , σ − i ∗ ) v_i(\sigma_i^*,\sigma_{-i}^*)\ge v_i(s_i,\sigma_{-i}^*) vi(σi∗,σ−i∗)≥vi(si,σ−i∗)。 命题2.1 在参与人 i i i的最优混合战略 σ i ∗ \sigma_i^* σi∗中,对 ∀ σ i j ∗ > 0 \forall\sigma_i^{j^*}\gt0 ∀σij∗>0,有 v i ( s j i , σ − i ) = v i ( σ i ∗ , σ − i ) v_i(s_j^i,\sigma_{-i})=v_i(\sigma_i^*,\sigma_{-i}) vi(sji,σ−i)=vi(σi∗,σ−i) 说明: 选择战略 j j j的概率一定得大于0;在战略指定的情况下,求得的期望应该是相等的。定理2.1(最优反应引理) 在有限 n n n人战略式博弈中,混合战略组合 σ ∗ \sigma^* σ∗是一个Nash均衡,当切仅当 ∀ i ∈ Γ \forall i\in\Gamma ∀i∈Γ, σ ∗ \sigma^* σ∗的支集 S i ( σ i ∗ ) S_i(\sigma^*_i) Si(σi∗)(大于0的概率出现的所有纯战略的集合)中的每一个纯战略都是给定 σ − i ∗ \sigma_{-i}^* σ−i∗下的最优反应。 混合战略Nash均衡的求解 支撑求解法什么是支撑? 对于给定的混合战略组合 σ \sigma σ, σ \sigma σ的支撑是指参与人按照 σ \sigma σ选择战略时,所有参与人的支集 S i ( σ i ) = { s i ∈ S i ∣ σ i ( s i ) > 0 } S_i(\sigma_i)=\{s_i\in S_i|\sigma_i(s_i)\gt0\} Si(σi)={si∈Si∣σi(si)>0}的直积。表示的是,当参与人按照 σ \sigma σ选择战略时,纯战略组合集 S S S中以大于0的概率出现的所有纯战略组合的集合。 于支撑求解法的思路就是: 构造出所有的混合战略均衡的支撑;对于每个给定的支撑,求解上述式子所确定的方程。等值法是支撑求解法的一种特例。 在求解方程组的过程中可能会出现下述三种情形: 方程组的解不存在。Nash均衡的解总是存在的,所以导致无解的原因在于所构造的支撑有问题,需要构造新的支撑;解不满足非负性条件,即方程组的解虽然存在,但是解中存在小于0的情形;方程的解都存在,并且解都大于0,但是对于给定的解,存在这样的情形:对于某个参与人 i i i,存在一个不属于支集 S i ( σ i ∗ ) S_i(\sigma_i^*) Si(σi∗)的战略 s i h s^h_i sih,对于给定的其他参与人的战略 σ − i ∗ \sigma_{-i}^* σ−i∗,参与人 i i i采用这个战略的期望效用更大一些。求解小tips: 不存在纯战略Nash均衡,因此不存在支撑中只包含参与人一个战略的Nash均衡;解不存在或者不满足非负性很好看出来,这时候直接就是不成立;把没考虑在内的战略带进去算算,看看这个期望是不是大一些,如果是,那么这个解也是无效的。给定战略组合,如果能剔除严格劣战略,那么说明这么选择的战略组合是有问题的,可以直接删除,以减小计算量。 规划求解法相对于支撑求解法,规划求解法对两人有限博弈问题的Nash均衡求解十分有效。 零和博弈所谓零和博弈是指在任何博弈情形下两个参与人的支付之和为0。 在零和博弈中,如果给出了支付矩阵U,就意味着给出了所有参与人的支付。 a先选,b后选对应着极小极大;b先选,a后选对应着极大极小。 定义2.9 对于给定的零和博弈的支付矩阵 U U U,如果存在某个 i ∗ , j ∗ i^*,j^* i∗,j∗,使得 a i ∗ j ∗ = max i min j a i j = min j max i a i j a_{i^*j^*}=\max_i\min_ja_{ij}=\min_j\max_i a_{ij} ai∗j∗=imaxjminaij=jminimaxaij 那么称第 i ∗ , j ∗ i^*,j^* i∗,j∗对应的点为支付矩阵U的鞍点。 定理2.2 在零和博弈中,如果支付矩阵U存在鞍点,那么鞍点对应的战略组合就是博弈的Nash均衡。 接下来,我们引入混合战略意义下的Nash均衡。 定义2.10 对于给定的零和博弈的支付矩阵U,如果存在参与人1的某个混合战略 σ 1 ∗ \sigma_1^* σ1∗和参与人2的某个混合战略 σ 2 ∗ \sigma_2^* σ2∗,使得 v 1 ( σ 1 ∗ , σ 2 ∗ ) = max σ 1 min σ 2 v 1 ( σ 1 , σ 2 ) = min σ 2 max σ 1 v 1 ( σ 1 , σ 2 ) v_1(\sigma_1^*,\sigma_2^*)=\max_{\sigma_1}\min_{\sigma_2} v_1(\sigma_1,\sigma_2)=\min_{\sigma_2}\max_{\sigma_1} v_1(\sigma_1,\sigma_2) v1(σ1∗,σ2∗)=σ1maxσ2minv1(σ1,σ2)=σ2minσ1maxv1(σ1,σ2)那么称该战略组合为支付矩阵U的鞍点。 定理2.3 同定理2.2。 定理2.4 命题2.2 如果支付矩阵U的每个元素都大于0,那么博弈的值大于0。 命题2.3 支付矩阵U’是U的每个元素都加上了一个c,那么支付矩阵对应的零和博弈的Nash均衡战略相同,博弈的值相差c。 |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |