博弈游戏
博弈游戏：
2个玩家，l和y,玩数字游戏，从2个自然数开始。l，第一个玩家，从大的数中减掉小数的任意正倍数，要求得到的数为非负。第二个玩家，y，以同样的方式处理the two resulting numbers，就这样一直玩下去。直到一个玩家能把其中一个数玩成0，然后他就win.例如，他们开始以这2个数：
25 7
11 7
4 3
1 3
1 0
所以l赢了。
输入数据形式为：每行就是一个游戏要处理的2个数。最后一行为0，0。输出为：谁赢了。
Sample input
34 12
15 24
0 0
Output for sample input
l wins
y wins
[解决办法]
很简单。
bool gamble(int large, int small){
if(large%small==0 || large/small> 1){
return true;//the first player win
}else{
return !gamble(small, large-small);
}
}
[解决办法]
楼上的算法有误，该算法忽略了条件：从大的数中减掉小数的任意正倍数，而这个正倍数由玩家自己确定的，因此需要提示玩家确定正倍数，例如上述博弈还可以为
sample input
25 7
18 7
11 7
4 7
4 3
1 3
1 0
如果这样，就是y win，将楼上算法该为：
t=1 //t=1表示玩家1开始决策，t=-1表示玩家y开始决策
bool gamble(int num1, int num2){
int max,min,a;
if(num1> =num2){
max=num1;
max=num2;
}
else{
max=num2;
min=num1;
}
if(max%min==0)
return ture;
else{
cont < < "请玩家输入正倍数： " < <endl;
cin> > a> > endl;
t=t*(-1);
return gamble(min,max-a*min);
}
if(t=1)
cont < < "The first player win! " < <endl;
else
cont < < "The Second player win! " < <endl;
[解决办法]
求奇异局势(+)：
+ (1,x)
- (1+x,x)
+ (1+x,1+2x)
- (2+3x,1+2x)
+ (2+3x,3+5x)
- (5+8x,3+5x)
+ (5+8x,8+13x)
....
e.g
ax+b=25
bx+c=7
->
18+c-b=(a-b)x
a=f(n),b=f(n+1),c=f(n+2) f(x)为菲伯纳切数列
[解决办法]
博弈要素
(1)局中人：在一场竞赛或博弈中，每一个有决策权的参与者成为一个局中人。只有两个局中人的博弈现象称为“两人博弈”,而多于两个局中人的博弈称为 “多人博弈”。
(2)策略：一局博弈中，每个局中人都有选择实际可行的完整的行动方案，即方案不是某阶段的行动方案，而是指导整个行动的一个方案，一个局中人的一个可行的自始至终全局筹划的一个行动方案，称为这个局中人的一个策略。如果在一个博弈中局中人都总共有有限个策略，则称为“有限博弈”，否则称为“无限博弈”。
(3)得失：一局博弈结局时的结果称为得失。每个局中人在一局博弈结束时的得失，不仅与该局中人自身所选择的策略有关，而且与全局中人所取定的一组策略有关。所以，一局博弈结束时每个局中人的“得失”是全体局中人所取定的一组策略的函数，通常称为支付（payoff）函数。
(4)对于博弈参与者来说，存在着一博弈结果
(5)博弈涉及到均衡：均衡是平衡的意思，在经济学中，均衡意即相关量处于稳定值。在供求关系中，某一商品市场如果在某一价格下，想以此价格买此商品的人均能买到，而想卖的人均能卖出，此时我们就说，该商品的供求达到了均衡。所谓纳什均衡，它是一稳定的博弈结果。
纳什均衡(Nash Equilibrium)：在一策略组合中，所有的参与者面临这样一种情况，当其他人不改变策略时，他此时的策略是最好的。也就是说，此时如果他改变策略他的支付将会降低。在纳什均衡点上，每一个理性的参与者都不会有单独改变策略的冲动。纳什均衡点存在性证明的前提是“博弈均衡偶”概念的提出。所谓“均衡偶”是在二人零和博弈中，当局中人A采取其最优策略a*,局中人B也采取其最优策略b*,如果局中人仍采取b*,而局中人A却采取另一种策略a，那么局中人A的支付不会超过他采取原来的策略a*的支付。这一结果对局中人B亦是如此。
这样，“均衡偶”的明确定义为：一对策略a*(属于策略集A)和策略b*（属于策略集B）称之为均衡偶，对任一策略a(属于策略集A)和策略b（属于策略集B），总有：偶对（a, b*）≤偶对(a*,b*)≤偶对（a*，b）。
对于非零和博弈也有如下定义：一对策略a*（属于策略集A）和策略b*（属于策略集B）称为非零和博弈的均衡偶，对任一策略a(属于策略集A）和策略b（属于策略集B），总有：对局中人A的偶对（a, b*） ≤偶对(a*,b*);对局中人B的偶对（a*，b）≤偶对(a*,b*)。
有了上述定义，就立即得到纳什定理：
任何具有有限纯策略的二人博弈至少有一个均衡偶。这一均衡偶就称为纳什均衡点。
纳什定理的严格证明要用到不动点理论，不动点理论是经济均衡研究的主要工具。通俗地说，寻找均衡点的存在性等价于找到博弈的不动点。
纳什均衡点概念提供了一种非常重要的分析手段，使博弈论研究可以在一个博弈结构里寻找比较有意义的结果。
但纳什均衡点定义只局限于任何局中人不想单方面变换策略，而忽视了其他局中人改变策略的可能性，因此，在很多情况下，纳什均衡点的结论缺乏说服力，研究者们形象地称之为“天真可爱的纳什均衡点”。
塞尔顿（R·Selten)在多个均衡中剔除一些按照一定规则不合理的均衡点，从而形成了两个均衡的精炼概念：子博弈完全均衡和颤抖的手完美均衡。
博弈的类型
(1)合作博弈——研究人们达成合作时如何分配合作得到的收益，即收益分配问题。
(2)非合作博弈——研究人们在利益相互影响的局势中如何选决策使自己的收益最大，即策略选择问题。
(3)完全信息不完全信息博弈：参与者对所有参与者的策略空间及策略组合下的支付有充了解称为完全信息；反之，则称为不完全信息。
(4)静态博弈和动态博弈
静态博弈：指参与者同时采取行动，或者尽管有先后顺序，但后行动者不知道先行动者的策略。
动态博弈：指双方的的行动有先后顺序并且后行动者可以知道先行动者的策略。
财产分配问题和夏普里值（Shapley value）
考虑这样一个合作博弈：a、b、c、投票决定如何分配100万，他们分别拥有50％、40％、10％的权力，规则规定，当超过50%的票认可了某种方案时才能通过。那么如何分配才是合理的呢?按票力分配，a50万、b40万、c10万c向a提出：a70万、b0、c30万b向a提出：a80万、b20万、c0……
权力指数：每个决策者在决策时的权力体现在他在形成的获胜联盟中的“关键加入者”的个数，这个“关键加入者”的个数就被称为权利指数。
夏普里值：在各种可能的联盟次序下，参与者对联盟的边际贡献之和除以各种可能的联盟组合。
次序 abc acb bac bca cab cba
关键加入者 a c a c a b
由此计算出a,b,c的夏普里值分别为4/6,1/6,1/6
所以a,b,c应分别获得100万的2/3,1/3,1/3。
