题目

一、图的同构

1、是否同构

是

2、下面哪些图是同构的？

答：a、d同构，b、c、e同构。  

3、

答案：c。

4、【题目】下面指出的哪些节点集合不对应这个6节点图的一个连通分量？

答案：只有c是连通分量。

5、

下面的圈不是连通分量，不满足独立性。上面两个不是连通图，但是是连通分量。  

6、【题目】

答案：（2*4）/（5*4）=0.4  

7、A聚集系数大7/10，嵌入性大；B结构洞。

8、介数

其实这里就是最短路径数

计算方法：

①按层次画出同构图

自上而下，每个节点到A的最短路径的条数=上面节点路径数之和。如下图：

从底向上（每个上面的节点，都会承载下面路径的流量）。

介数是边的属性，即A-B、C、D、E才有，所以这里的2、3、4、2就是四条边的介数，跟最上面的7*7=49整数不冲突。

9、综合考察同质性：社会归属网络

三元闭包、社团闭包、会员闭包可以同时显现 

10、谢林模型

约束条件：每一个代理都要和一定量的同类代理成为邻居

动态：如果一个代理发现自己同类邻居少于t个，就会搬家到符合要求的地点。t为门槛值，可以设定。

11、短视搜索

短视搜索可能没走最短路径

特征距离：0-A为6：0-F-E-D-C-B-A

短视搜索：0-C-B-A（因为0只能看到紫圈和自己的绿线）

最短路径：0-F-A

12、占优策略

（1）严格占优策略：

①

不论对方选什么，我都是选α更好（注意该看谁的收益）

②

对称：纵的列看前面，看最大的是不是在同一行（在同一行，选复习考试）

非对称：看行，选对方最优策略

③

10<25，0<3，所以会选择认罪

（2）单方占优策略

对手一定会选α，所以我只能选α。

①站在我放的角度分析没有优势策略；

②对手有优势策略；

③基于对手会选择优势策略的前提，选择我方的策略。

13、纳什均衡

①

②

直接看自己的选择，2会选右，1会选低，but：

①如果1选低，2会根据1的选择选中，然后1根据2的选择选低，“中低”；

②如果2选右，1会根据2的选择选低，然后2根据去的选择选中，然后1根据2的选择选低，“中低”；

协调博弈——有两个以上纳什均衡：

①安全博弈/猎鹿模型：

两个纳什均衡：（4,4）和（3,3）

②懦夫模型/鹰鸽模型

协调失败风险大。

每个参与人都同时有两个极端的策略：强硬和软弱

①有2个纳什均衡：（-1,1）和（1，-1）。

②每个参与人都试图影响结果从而对自己有利，但又要防止最坏的结果发生。

14、双人双策略、不含纯策略均衡的博弈中的混合策略纳什均衡求解

①

②

③

⑤

⑥

15、进化稳定策略

①称“策略T在x程度上（以x水平）入侵策略S”，指的是在总体中有x占比的生物体采用策略T，1-x占比采用策略S；其中x是一个小于1的小正数。

②若存在一个小正数y，当任何其他策略T以任何x<y水平入侵策略S时，采用策略S的个体的适应性严格高于采取策略T的个体，则称策略S是进化稳定的（evolutionarily stable）。

（1）

考察小体态是否进化稳定策略：小体态为1-x，大体态为x

–一只小甲虫的期望收益是：5(1-x)+1*x = 5-4x

–一只大甲虫的期望收益是：8(1-x)+3*x = 8-5x

可见，不存在y，使得x<y时小甲虫的期望收益超过大甲虫。因此，策略“小体态”不是进化稳定的。

察大体态是否进化稳定策略：小体态为x，大体态为1-x

–大甲虫期望收益是3 (1-x) + 8x = 3+ 5x

–小甲虫期望收益是(1-x) + 5x = 1+4x

②大甲虫的期望收益总是超过小甲虫的，所以，“大体态”是一个进化稳定策略。

（2）

判断谁是否进化稳定，就把谁的设为1-x，并且放在前面，然后看abcd关系。

均满足a>c，so猎鹿和猎鹰都是进化稳定的，且（猎鹿，猎鹿）（猎兔，猎兔）都是纳什均衡

另一种猎鹿模型

16、进化稳定混合策略

17、【题目】下面哪些结果是实验很可能看到的？

答案：d、e>a。b、c不可能

（2）判断是否是稳定结果

不稳定因素：在结果中的一条边，其两端节点的价值之和小于1；（因为他们可以一起多分点）。

a、c不稳定；b、d、e稳定

（3）判断是否是平衡结果

看结果中匹配的每条边上，两端节点是否满足纳什议价解。

C的结果是对的，计算是错的1/3+(1-1/3)÷2=2/3    

该结果是稳定结果，是平衡结果，因为纳什议价解为：

A=0+1/4=1/4；B=1/2+1/4=3/4；C=1/4+1/4=1/2；D=1/4+1/4=1/2

18、流量博弈

（1）有4000辆车，都要从A到B，怎么走？

均衡：每条路上2000辆车；对每辆车而言，对应回报为65。 

不采用该策略，则45+2001/100>65，所以没有司机会愿意换道。

增加资源的结果

19、信息级联

（1）设一个城市，出租车的颜色有两种，其中黑色占80％，黄色占20％。出现了一个交通事故，肇事出租车逃离，现场目击者说是“黄色”，但他可能看错了：

–假设出错概率0.1（即黑说成黄，或者黄说成黑）；

–换句话说，黄说成黄或黑说成黑的概率为0.9。

问，那辆车真是黄色的可能性（概率）有多大？

肇事车是黄色的概率：（0.9*0.2）/（0.9*0.2+0.1*0.8）=9/13。

（2）

①第一个人为什么报“蓝多”？–他一定是抓到了一个蓝球

②第二个人为什么报“蓝多”？–他一定也是抓到了一个蓝球

③轮到你了！抓的是红球，坛子为“红多”的概率是多少？

这说明，即使你抓了红球，但坛子为“红多”的概率小于0.5，因此应该忽略自己得到的信号，理性地选择随大流——宣布“蓝多”！

④现在看第四个人，假设她也摸到红球，但她已经不能推断出第三个人抓的什么球，只会做如下计算：

（3）某事物以两种状态之一随机出现，好（G）状态与差（B）状态，概率分别为p和1-p；

基于某种随机“探测”，得到关于事物状态的两种信号之一，高（H）信号与低（L）信号；

信号的概率取决于状态：如果G状态，则H信号出现的概率大，否则L信号出现的概率大。假设两种情况的较大概率相等，记作q（这样，对应较低概率就是1-q）。

任务：根据已知信息（信号），判断事物处于什么状态。

如果探测到一个高信号H：

也是根据贝叶斯公式，其中用到了先验概率p，信号探测独立性，q>1-q的假设。