博弈论算法一、博弈的战略式表述及纳什均衡的定义博弈的战略式表述及纳什均衡的定义在博弈论里，一个博弈可以用两种不同的方式来表述：一种是战略式表述（strategicformrepresentation），另一种是扩展式表述（或译为“展开式表述”（extensiveformrepresentation））。从分析的角度看，战略式表述更适合于静态博弈，而扩展式表述更适合于讨论动态博弈。1.1博弈的战略式表述战略式表述又称为标准式表述（normalformrepresentation）。在这种表述中，所参与人同时选择各自的战略，所有参与人选择的战略一起决定每个参与人的支付。战略式表述给出：1.博弈的参与人集合：i∈Γ,Γ=(1,2,L,n)。2.每个参与人的战略空间：Si,i=1,2,L,n。我们用G=(S1,L,Sn;u1,L,un)代表战略式表述博弈。3.每个参与人的支付函数：ui(s1,s2,L,sn),i=1,2,L,n。例如在两个寡头产量博弈里，企业是参与人，产量是战略空间，利润是支付;战略式表述博弈为：(1.1)G={q1≥0,q2≥0;π1(q1,q2),π2(q1,q2)}这里qi、πi别表示第i个企业的产量和利润。1.2纳什均衡的定义??有n个参与人的战略式表述博弈G=(S1,L,Sn;u1,L,un)，战略组合s=s1,L,si,L,sn是一个纳????什均衡。如果对于每一个i、si是给定其他参与人选择s?i=s1,L,si?1,si+1,L,sn的情况下第个参与人{{????}}的最优战略，即??ui(si?,s?i)≥ui(si,s?i),?si∈Si,?i(1.2)或者用另一种表述方式，si是下述最大化问题的解:?si?∈argmaxui(s1?,...,si??1,si,si?+1,...,sn),i=1,2,...,n;si∈Si?(1.3)我们用这个定义来检查一个特定的战略组合是否是一个纳什均衡。1.3囚徒困境两个嫌疑犯作案后补警察抓住，被分别关在不同的房间里审讯。警察知道两人有罪，但缺乏足够的证据定罪，除非两人当中至少有一个人坦白。警察告诉每个人：如果两个都不承认，每个人都以轻微的犯罪判刑1年；如果两人都坦白，各判刑8年；如果两人中一个人坦白另一个人抵赖，坦白的释放出去，抵赖的判刑10年。这样，每一个嫌疑犯面临四个可能的后果：获释（自己坦白同伙抵赖）；被判刑1年（自己抵赖同伙也抵赖）；被判刑8年（自己坦白同伙也坦白）；被判刑10年（自己抵赖但同伙坦白）。囚徒困境囚犯B表1坦白抵赖坦白囚犯A抵赖(-8,-8)(0,-10)(-10,0)(-1,-1)在这个博弈中，每个囚徒都有两种可选择的战略：坦白或抵赖。显然，不论同伙选择什么战略，每个囚徒的最优战略是“坦白”，比如说，如果B选择坦白，A选择坦白时支付为-8，选择抵赖时的支付为-10，因而坦白比抵赖好；如果B选择抵赖，A坦白时的支付为0，抵赖时的支付为-1，因而坦白还是比抵赖好。就是说，“坦白”是囚徒A的占优战略。类似的，“坦白”也是B的占优战略。在囚徒困境里，（坦白，坦白）是一个纳什均衡，而（抵赖，抵赖）不是一个纳什么均衡，因为给定同伙选择抵赖，自己选择抵赖时得到-1，选择坦白时得到0，因而抵赖不是自己的最优战略，类似的，（坦白，抵赖）和（抵赖，坦白）也不是纳什均衡。二、矩阵对策矩阵对策2.1纯零和对策零和对策矩阵对策也叫零和对策，是一类特殊的对策问题。在这类对策中，只有两名局中人，每个局中人都只有有限个策略可供选择。在任一纯局势下，两个局中人的赢得之和总是等于零，即双方和利益是激烈对抗的。设局中人I、II的策略集分别为：(2.1)S1={α1,L,αm},S2={β1,L,βn}当局中人I选定策略αi和局中人II选定策略βj后，就形成了一个局势(αi,βj),可见这样的局势共有mn个，对任一局势(αi,βj)，记局中人I的赢得值为aij，并称?a11?aA=?21?M??am1a12a22Mam2La1n?La2n??OM??Lamn?（或为局中人II的支付矩阵）由于假定对策为零和的，。故局中人II的赢得矩阵就是?A。为局中人I赢得矩阵S1、S2及局中人I的赢得矩阵A确定后，一个零和对策就给定了，零和对当局中人I、II和策略集策又可称为矩阵对策，并可简记成：G={S1,S2;A}双方都应考虑到对方有使自己损失最大的动机。定义1鞍点设f(x,y)为一个定义在x∈A及y∈B上的实值函数，如果存在x?∈A,y?∈B使得一切x∈A和y∈B，有f(x,y?)≤f(x?,y?)≤f(x