数学博弈论

我们问：o我加入S的概率是多少？让k- 1=|S |是S的大小，我要加到S上的序列σ的数量是|{σ| i=ik和Sσk-1=S}|=（k）-1） 哦！（n）- k） !！这是因为：（1）第一个k-1元素必须从任何（k）中的S中选择-1） 哦！可能的命令。（2） 剩下的n- k元素必须来自N\\（S）∪{i} ）。所以我们得出πShS=（k- 1） 哦！（n）- k） !！n=（|S |）！（n）-|S|-1） 哦！N并得到另一个SHAPLEY值的显式公式：110 7。合作对策（47）ΦShi（v）=XSN\\{i}iv（S）πShS=XSN\\{i}四（S）S！（n）- |S|- 1） 哦！N例7.12。考虑一个投票/阈值游戏（参见第1.6节），权重为W＝3，W＝2，W＝2，W＝1。在阈值w=4.4的情况下，计算每个玩家的Banzhafan和SHAPLEY值。Boltzmann值上一节的概率分析显示，例如，班扎夫权力指数和沙普利值的价值评估概念隐含地假设，参与者只是在合作博弈中加入——但永远不会离开——现有联盟（N，v）∈ G（N）。相比之下，本节的模型在所有联盟的集合2n上假设一个潜在的概率分布π，并分配给playeri∈ N其预期边际值ei（v，π）=XSNiv（S）πS=XSN（v（S）（一）- 我们进一步允许π依赖于所考虑的特定特征函数v。

那么功能V7→ Ei（v，π）不能保证是线性的。在这个模型中，人们应该合理地期望什么样的概率分布π？为了回答这个问题，我们考虑了相关的期望特征值Nv（S）π作为一个相关参数，并询问：o仅给出u，哪个概率分布^π将是（未知）π的最佳无偏猜测？从信息论的角度来看，最好的无偏猜测^π是那些产生期望值u的概率分布π中熵最高的一个。因此，我们寻求优化问题的解决方案。玻尔兹曼值111（48）maxxS≥0H（x）=-nXSNxSln xSs。t、 u=XSNv（S）xS1=XSNxS。定理7.4。对于每一个潜在的v:N→ R和v的可能期望值u存在唯一参数-∞ ≤ T≤ +∞使（1）u=XSNv（S）ev（S）T/ZT，其中ZT=XS内华达州（S）T；（2） 数字bTS=e-v（S）T/ZTare严格地给出了熵优化问题（48）的唯一最优解。定理7.4的证明可在附录第6.2节中找到。概率B确定了v:N的玻尔兹曼分布→ 与参数T相关。因此，我们可以得到每个yv的玻尔兹曼值Φbf和参数T：（49）ΦBi（v；T）=XSNiv（S）bTS=ZTXSNiv（S）ev（S）T（i）∈ N） 让我们看看一些极端情况。对于T=0，玻尔兹曼分布只是N上的均匀分布，bS=|N |=S N、 一个球员的波尔兹曼价值∈ N是所有边缘值的平均值：ΦBi（v；0）=nXSN四（S）。在T=+∞, B∞成为setVmax上的均匀分布 v的所有最大化子中的2n（见Ex.7.13）。因此有ΦBi（v+∞) =|Vmax | XS∈Vmax四（S）112 7。合作博弈同样，我们可以看到b-∞是v.EX.7.13集合VMINOfMinimizer上的均匀分布。让我们*∈ Vmax应该是v和S的最大化子 N武断的。

特林姆→+∞电动汽车(S)电动汽车(S)*)T=limT→+∞e（v（S）-v（S）*)T=1如果v（S）=v（S）*)否则为0。得出结论b∞是Vmax上的均匀分布（概率为0的所有其他联合体）。温度与统计热力学物理中的玻尔兹曼模型类似，我们可以将v视为一个能量势函数，并求其极小值。所以我们面对T<0的玻尔兹曼分布。当kB>0是一个标准化因子时，我们定义θ=-1kBT≥ 0，因此bTS=ZTe-v（S）/kB~θ。热力学解释为，具有势能分布bT的协同系统的温度→ 0时，系统以高概率达到最小可能的状态（联盟）。在高温情况下∧θ→ ∞, 系统变得越来越不可预测：所有状态（联盟）的可能性大致相同（即近似均匀分布）。与物理学的类比表明，在一般的博弈论环境中，非负参数θ=|T |可以作为温度的度量。特别是，如果一个经济系统被假定由一个潜在因素（如国民生产总值或类似的全球指标）控制，那么谈论该系统的“温度”似乎是合理的。结论是一样的：o如果θ→ ∞, 所有联合战略行动的可能性大致相等如果θ→ 0时，期望的势能值变为极值，即当T→ + ∞ 如果不是的话，我的尼马尔→ -∞.所谓玻尔兹曼常数kb的精确物理值与我们的博弈论目标无关！5.联盟组建1135。

联盟形成这个术语最初指的是合作博弈。联盟的形成被视为一个动态过程，在这个过程中，联盟会随着时间的推移而演变，取决于玩家的行为，玩家可能会离开暂时的联盟，加入其他玩家组成新联盟等。。当然，决策过程如何随着时间的推移而演变的问题，对于联合战略的一般有效的g ameΓ=（N，v）和系统X来说是有意义的。如果假设| X |<∞还有我的特工∈ N要想独立地贪婪，也就是说，如果一个转换提供了更好的边际价值，那么我们必须得出结论，代理人最终会达到一个行动平衡*∈ X（参见提案5.2）。另一方面，如果我们不对个体主体进行优先假设，但假设决策过程最终到达接合点x∈ 概率为πX的X产生预期的电位值u=Xvx∈Xv（x）πx，概率分布π的无偏估计得出结论（定理7.4），决策过程最终产生联合策略选择x∈ 用玻尔兹曼概率btx=ZTev（X）乘以T，使得u=Xx∈Xv（x）bTx。METROPOLIS等人建立了一个随机过程的模型，该模型收敛于具有BTT的分布≥ 0如下所示：（M1）如果进程当前处于状态x，则代理i∈ N是概率为pi>0的；（M2）我选择了一个动作y∈ 概率qy>0；（M3）如果v（x-i） （y）>v（x），然后我从xito y切换；（M4）如果v（x-i（y））≤ v（x），然后i从xito切换到y，概率α=e（v（x-i（y）-v（x））T（否则不会改变动作）。N.METROPOLIS，A.ROSENBLUTH，M.ROSENBLUTH，A.TELLER，E.TELLER：通过快速计算机计算状态方程。J.化学。物理学21（1953）114 7。

合作博弈METROPOLIS等人的算法模拟了X上所谓的马尔可夫链。其正确性的证明不是很困难，而是有点技术性。因此，我们将不在这里重复它，而是指出算法的相关特性：o如果yv（x）=v（x-i） （y）- v（x）≥ 0，探员i贪婪，将战略行动切换到y.o如果yv（x）<0，则i在s mall的概率y较大时切换：E电视（x）T→ 0作为T→ +∞.备注7.12。METROPOLIS算法很容易针对T进行调整≤ 0：一个简单地用势w代替v=-v，并以w和非负参数T′=-同上。5.1. 我个人贪婪和公益。让我们假设一个社会的共同福利是通过潜在的v来表达的。如果N的所有成员都纯粹贪婪地行动，那么最终将产生一种公平的行动，而这并不一定会导致高的共同福利水平。例如，如果在WARDROP交通情况下（参见第4节）的所有玩家都表现得非常贪婪，那么就不能保证最优的交通流量。然而，如果N的m个成员准备好可能接受暂时的边际退化（算法中的情况（M4）），则uT（v）=Xx级的公共福利∈Xv（x）BTX可以预期。此外，T越大，uT（v）越接近最大可能水平vmax。因此，为了达到较高的公共福利水平，社会必须提供激励或个人奖励，以诱导参与者采取（M4）中所述的行动。5.2. 模拟退火。如果只有一个代理，X是代理的策略集，METROPOLIS算法可用于优化函数v:X→ R、 即，找到问题Maxx的最优解∈Xv（x）通过在每次迭代后添加程序步骤s（M5），在目标T的基础上稍微增加T→ ∞.6.

合作博弈中的均衡在这种形式下，METROPOLIS算法也称为模拟退火算法。在离散优化领域，它已被证明是一种非常成功的优化技术。评论。请注意，关于模拟退火算法的实际实现，其描述不是很具体。应如何选择概率qtin（M3）？在（M5）中不应该增加多少？因此，模拟退火方法的成功也将取决于用户在实践中的技能和经验。6.合作博弈中的均衡在前面的章节中，我们讨论了METROPOLIS算法，作为马尔可夫链的一个例子，该马尔可夫链根据波尔兹曼概率对联盟形成进行建模。如果我们后退一步，把合作游戏Γ=（N，v）中的玩家想象成一个群体，他们的行为受到实现共同目标的个人利益的引导，我们必须假设每个人∈ N有一个单独的实用程序功能ui:N→ R、 其中，ui（S）是i的预期收益（或成本），以防联盟S在Γ中活动，从而实现N的值v（S）。当然，ui将自然依赖于Γ的特征函数v。但其他因素也可能发挥作用。在BOLTZMANN m模型中，玩家i的效用标准本质上是其边际收益iv（S）-如果它是非负的。如果为负，则假定提供额外的激励，以便以一定的概率进行无目标的战略切换。

通常，波尔兹曼模型不承认联盟均衡——除非博弈在极端温度T下进行。许多其他价值概念（如SHAPLEY和BANZHAF）都是基于边际收益作为球员个人效用评估的基本标准。让我们考虑一个游戏γ=（n，v），并考虑到游戏最终会分裂成一个S组。 N和互补群sc=N\\S。假设一个玩家i∈ N通过vi（S）=vi（Sc）计算N的分区（S，Sc）的效用=五(S)- v（S\\i）如果我∈ Sv（Sc）- v（Sc\\i）如果我∈ Sc，S.KIRKPATRICK，C.D.Glate，M.P.VECCHI：模拟退火优化。《科学》220（1983）116 7。合作游戏性爱。7.14. 假设（N，v）是一个超级模块游戏。然后有一个对所有玩家来说，i 6=j，vi（N）=v（N）- v（N\\i）≥ v（N\\j）- v（（N\\j）\\i）=vi（N\\j）vi（N）=v（N）- v（N\\i）≥ v（{i}）- 五() = vi（N\\i）。因此，大联盟N代表了相对于效用vi.ex7.15的增益均衡。假设（N，c）是一个零正规化的子模对策，在这里我有u效用=丙(S)- c（S\\i）i f i∈ 理学士（理学士）- c（Sc\\i）如果我∈ Sc.Show：大联盟N是相对于公用事业ci的成本均衡。第8章相互作用系统和量子模型本章研究了一个关于集合X的合作和相互作用的相当普遍的模型。使用复数，该模型的状态自然地表示为具有复系数的厄米矩阵。这种表示法使我们能够对相互作用系统进行标准的光谱分析，并与物理学中量子系统的标准数学模型建立了联系。虽然分析可以扩展到一般的希尔伯特空间，但为了使讨论更简单，假设Xis是有限的。1.

代数预备矩阵代数是分析数学的主要工具，我们回顾了线性代数中更多的基本概念。更多细节和证明可以在任何一本关于李近代数的像样的书中找到。其中X={X，…，xm}和Y={Y，…，yn}是两个完整的索引集，回想一下，RX×yde记录了所有矩阵A的实向量空间，其中行由X索引，列由Y索引，系数为Axy∈ R.A的转置∈ RX×Xis是∈ RY×X，系数为Axy=Axy。地图是A 7→ 在向量空间RX×yan和RY×X之间建立同构∈ RX×Yand B∈ y×X作为mn维参数向量，我们有通常的欧几里德内积ashA | Bi=X（X，y）∈X×YAxyBxy=BTA。在hA | Bi=0的情况下，A和B称为正交。相关欧几里德范数iskAk=phA | ATi=sX（x，y）∈X×Y | Axy |。e、 g.e.D NERING（1967），线性代数与矩阵理论，威利，纽约118 8。相互作用系统和量子模型我们想到一个向量v∈ rx通常作为列向量。所以vt是具有相同坐标vTx=vx的行向量。注意两个矩阵p乘积之间的差异：vTv=Xx∈X | vx |=kVvt=VxVxVx。VxMVxVxVxVx。VXM。。。。。。。。。。。。vxmvxvxmvx。vxmvxm.1.1. 对称分解。假设现在相同的索引集x=Y={x，…，xn}a矩阵a∈ 如果AT=A，则RX×Xis对称。如果AT=-A、 矩阵A是斜对称的。用任意矩阵A∈ RX×X，我们将矩阵A+=（A+AT）和A关联起来-=（A）- 至少- A+。注意A+是对称的，A+是对称的-是斜对称的。A的对称分解是（50）A=A++A的表示-mat ri x A al将一个分解精确地转化为对称和斜对称矩阵（见例8.1）。所以对称分解是唯一的。例8.1。让A，B，C∈ RX×Xbe，使得A=B+C。

证明这两种说法是等价的：（1）B是对称的，d C是斜对称的。（2） B=A+和C=A-.请注意，对称矩阵和斜对称矩阵必须成对正交（见Ex.8.2）。例8.2。设A是对称矩阵，B是斜对称矩阵x.S how:hA | Bi=0，kA+Bk=kAk+kBk。2.复矩阵1192。复数在物理学和工程学中，复数提供了一种表示正态结构的方便方法。将此id ea应用于对称分解，就得到了所谓的hermi-tian矩阵。回想一下，复数是形式z=a+IB的表达式，其中a和b是实数，i是一个特殊的“新”数，即所谓的数字单位。特别是，形式为a+i·0的复数z与实数a相同∈ R.我们用C表示所有复数的集合，即C=R+iR={a+ib | a，b∈ R} 。复数可以根据实数的代数规则进行加法、减法、乘法和除法，加法计算提供：i=-1.z=a- ib是复数z=a+ib的共轭，所以一个haszz=（a+ib）（a）- ib）=a+b=|z |。复矩阵C的共轭是共轭系数XY=Cxy的矩阵XC。伴随C*是C:C的共轭物的转置*=计算机断层扫描。对于两个复矩阵A=A+Ia和B=B+Ib，其矩阵为A，A，B，B∈ RX×Y，一个计算b*A=（BT）- iBT）（A+iA）=hA | Bi+hA | Bi，这意味着定义hA | Bi=B*这是一种将实矩阵的内积推广到复矩阵的自然方法。具体来说，一个人拥有毕达哥拉斯的财产：ka+iAk=hA+iA | A+iAi=kAk+kAk。2.1. 自伴性和谱分解。如果复矩阵C等于伴随矩阵C=C，则称之为自伴矩阵*=CTIf C只有实系数，那么C=C，因此，“自伴”可以归结为“sy mmetric”。

这是众所周知的实对称矩阵120 8。相互作用系统和量子模型可以对角化。用同样的参数，我们可以把这个结果推广到一般的自伴矩阵：定理8。1（谱定理）。对于矩阵C∈ CX×X这两个语句是等价的：（1）C=C*.（2） cx是一个幺正基U={Ux | x∈ 十} o f实特征值λX的特征向量uxc。酉指基U，向量ux具有单位范数且成对正交，即hUx | Uyi=U*是的=1如果x=y0如果x 6=y。标量λxis是特征向量uxc的特征值ifCUx=λxUx。从定理8.1（见Ex.8.3）可知，自伴矩阵C包含谱分解，即（51）C=Xx形式的表示∈XλxUxU*x、 其中，UX是具有eig值λx的C的成对正交特征向量∈ R.EX.8.3。设U={Ux | x∈ 十} 是cx与aset∧={λX | X的酉基∈ 十} 一组任意的复数标量。显示：（1）矩阵xc=Xx的特征值为λxo的特征向量∈XλxUxU*x、 （2）C是自伴的当且仅当所有λx都是实数。谱分解表明：矩阵的谱定义为其特征值集2。复矩阵121Cx×X中的自联合矩阵C正是C=Xx型矩阵的线性组合∈XλxUxU*x、 其中，cxare中的Uxare（列）向量和λxare实数。谱单位分解。作为一个例子，考虑一个矩阵∈ CX×X具有成对正交列向量Ujof范数kUkx=1，这意味着恒等y矩阵I具有代表性I=UU*= U*U.I的特征值都是λx=1。